利用者:ARAKI Satoru/ポリアの数え上げ定理

ポリアの数え上げ定理（英: Pólya enumeration theorem）、あるいはレッドフィールド・ポリアの定理（英: Redfield–Pólya Theorem）とは組合せ論の定理で集合に作用する群の軌道の数に関するバーンサイドの補題を一般化したものである。この定理は1927年にジョン・ハワード・レッドフィールドによって発表された。1937年にジョージ・ポリアによって独立に再発見され、化学化合物の数え上げなどの多くの数え上げ問題に応用され、一般に知られるようになった。

重みのない簡易版

X を有限集合とし G を X の置換群（あるいは X に作用する群）とする。たとえばもし X が n 個のビーズを円環に並べたネックレスとすると、回転対称性は巡回群 C_n 、鏡映対称性は二面体群 D_2n である。さらに Y をビーズの色からなる |Y| = t の有限集合とすると Y^X は彩色されたビーズの並びからなる集合である。（より形式的は「彩色」とは関数 X → Y のことである。）ポリアの数え上げ定理は彩色されたビーズの並びの群 G に関する軌道の数を次の式によって与える。

$|Y^{X}/G|={\frac {1}{|G|}}\sum _{g\in G}t^{c(g)}$

ここで c(g) は群の元 g の X 上の置換としての巡回置換の数である。

The full, weighted version

In the more general and more important version of the theorem, the colors are also weighted in one or more ways, and there could be an infinite number of colors provided that the set of colors has a generating function with finite coefficients. In the univariate case, suppose that

$f(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots$

is the generating function of the set of colors, so that there are f_n colors of weight n for each n ≥ 0. In the multivariate case, the weight of each color is a vector of integers and there is a generating function f(a,b,...) that tabulates the number of colors with each given vector of weights.

The enumeration theorem employs another multivariate generating function called the cycle index:

$Z_{G}(t_{1},t_{2},\ldots ,t_{n})={\frac {1}{|G|}}\sum _{g\in G}t_{1}^{j_{1}(g)}t_{2}^{j_{2}(g)}\cdots t_{n}^{j_{n}(g)}.$

Here the kth weight j_k(g) is the number of k-cycles of g as a permutation of X. The theorem then says that the generating function F of colored arrangements is the cycle index, composed with the generating function f of the colors, composed with powers of the variables of f:

$F(x)=Z_{G}(f(x),f(x^{2}),f(x^{3}),\ldots ,f(x^{n}))$

or in the multivariate case:

$F(a,b,\ldots )=Z_{G}(f(a,b,\ldots ),f(a^{2},b^{2},\ldots ),f(a^{3},b^{3},\ldots ),\ldots ,f(a^{n},b^{n},\ldots )).$

To reduce to the simplified version, if there are t colors of weight 0, then

$|Y^{X}/G|=Z_{G}(t,t,\ldots ,t).$

In the celebrated application of counting trees (see below) and acyclic molecules, an arrangement of "colored beads" is actually an arrangement of arrangements, such as branches of a rooted tree. Thus the generating function f for the colors is derived from the generating function F for arrangements, and the Pólya enumeration theorem becomes a recursive formula.

Examples

Graphs on three and four vertices

A graph on m vertices can be interpreted as an arrangement of colored beads. The arrangement X is the set of ${\binom {m}{2}}$ possible edges, while the set of colors Y = {black,white} corresponds to edges that are present (black) or absent (white). The Pólya enumeration theorem can be used to calculate the number of graphs up to isomorphism with a fixed number of vertices, or the generating function of these graphs according to the number of edges they have. For the latter purpose, we can say that a black or present edge has weight 1, while an absent or white edge has weight 0. Thus $f(t)=1+t$ is the generating function for the set of colors. The relevant symmetry group is $G=S_{m}$, the symmetric group on m letters; an isomorphism class of graphs is equivalent to an orbit of graphs under this group. It acts as a subgroup of $S_{\binom {m}{2}}$, the group of permutations of all of the edges.

ファイル:AllGraphsOnThreeVertices.png

All graphs on three vertices.

ファイル:NonisomorphicGraphsOnThreeVertices.png

Nonisomorphic graphs on three vertices.

The 8 graphs on three vertices without quotienting by symmetry are shown at the right. There are four isomorphism class of graphs, also shown at the right.

The cycle index of the permutation group of the edges is

$Z_{G}(t_{1},t_{2},t_{3})={\frac {t_{1}^{3}+3t_{1}t_{2}+2t_{3}}{6}}.$

Thus, according to the enumeration theorem, the generating function of graphs on 3 vertices up to isomorphism is

$F(t)=Z_{G}(t+1,t^{2}+1,t^{3}+1)={\frac {(t+1)^{3}+3(t+1)(t^{2}+1)+2(t^{3}+1)}{6}},$

which simplifies to

$F(t)=t^{3}+t^{2}+t+1.$

Thus there is one graph each with 0 to 3 edges.

ファイル:NonisomorphicGraphsOnFourVertices.png

Isomorphism classes of graphs on four vertices.

The cycle index of the edge permutation group for graphs on four vertices is:

$Z_{G}(t_{1},t_{2},t_{3},t_{4})={\frac {t_{1}^{6}+9t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}t_{4}}{24}}.$

Hence

$F(t)=Z_{G}(1+t,1+t^{2},1+t^{3},1+t^{4})={\frac {(t+1)^{6}+9(t+1)^{2}(t^{2}+1)^{2}+8(t^{3}+1)^{2}+6(t^{2}+1)(t^{4}+1)}{24}}\,$

which simplifies to

$F(t)=t^{6}+t^{5}+2t^{4}+3t^{3}+2t^{2}+t+1.$

These graphs are shown at the right.

Rooted ternary trees

The set T₃ of rooted ternary trees consists of rooted trees where every node has exactly three children (leaves or subtrees). Small ternary trees are shown at right. Note that ternary trees with n vertices are equivalent to trees with n vertices of degree at most 3. In general, rooted trees are isomorphic when one can be obtained from the other by permuting the children of its nodes. In other words, the group that acts on the children of a node is the symmetric group S₃. We define the weight of such a ternary tree to be the number of nodes (or non-leaf vertices).

ファイル:TernaryTrees.png

Ternary trees on 0, 1, 2, 3 and 4 vertices. (Leaves not shown except for the tree on zero vertices (green)).

We can view a rooted, ternary tree as a recursive object which is either a leaf or three branches which are themselves rooted ternary trees. These branches are equivalent to beads; the cycle index of the symmetric group S₃ that acts on them is then

$Z_{S_{3}}(t_{1},t_{2},t_{3})={\frac {t_{1}^{3}+3t_{1}t_{2}+2t_{3}}{6}}.$

The Polya enumeration theorem then yields a functional equation for the generating function T(x) of the rooted ternary trees:

$T(x)=1+x{\frac {T(x)^{3}+3T(x)T(x^{2})+2T(x^{3})}{6}}.$

This is equivalent to the following recurrence formula for the number t_n of rooted ternary trees with n nodes:

$t_{0}=1$

and

$t_{n+1}={\frac {1}{6}}\left(\sum _{a+b+c=n}t_{a}t_{b}t_{c}+3\sum _{a+2b=n}t_{a}t_{b}+2\sum _{3a=n}t_{a}\right)$

where a, b and c are nonnegative integers.

The first few values of $t_{n}$ are

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 オンライン整数列大辞典の数列 A000598

Colored cubes

How many ways are there to color the sides of a 3-dimensional cube with t colors, up to rotation of the cube? The rotation group C of the cube acts on the six sides of the cube, which are equivalent to beads. Its cycle index is

$Z_{C}(t_{1},t_{2},t_{3},t_{4})={\frac {t_{1}^{6}+6t_{1}^{2}t_{4}+3t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}^{3}}{24}}.$

Thus there are

$Z_{C}(t,t,t,t)={\frac {t^{6}+3t^{4}+12t^{3}+8t^{2}}{24}}$

colorings.

Proof of theorem

The simplified form of the Pólya enumeration theorem follows from Burnside's lemma, which says that the number of orbits of colorings is the average of the number of elements of $Y^{X}$ fixed by the permutation g of G over all permutations g. The weighted version of the theorem has essentially the same proof, but with a refined form of Burnside's lemma for weighted enumeration. It is equivalent to apply Burnside's lemma separately to orbits of different weight.

For clearer notation, let $x_{1},x_{2},\ldots$ be the variables of the generating function f of $Y$. Given a vector of weights $\omega$, let $x^{\omega }$ denote the corresponding monomial term of f. Applying Burnside's lemma to orbits of weight $\omega$, the number of orbits of this weight is

${\frac {1}{|G|}}\sum _{g\in G}|(Y^{X})_{\omega ,g}|$

where $(Y^{X})_{\omega ,g}$ is the set of colorings of weight $\omega$ that are also fixed by g. If we then sum over all all possible weights, we obtain

$F(x_{1},x_{2},\ldots )={\frac {1}{|G|}}\sum _{g\in G,\omega }x^{\omega }|(Y^{X})_{\omega ,g}|.$

Meanwhile g has a cycle structure $j_{1},j_{2},\ldots ,j_{n}$ which contributes

$t_{1}^{j_{1}(g)}t_{2}^{j_{2}(g)}\cdots t_{n}^{j_{n}(g)}$

to the cycle index of G. The element g fixes an element of $Y^{X}$ if and only if it is constant on every cycle q of g. The generating function by weight of a cycle q of |q| identical elements from the set of objects enumerated by f is

$f(x_{1}^{|q|},x_{2}^{|q|},x_{3}^{|q|},\ldots ).$

It follows that the generating function by weight of the points fixed by g is the product of the above term over all cycles of g, i.e.

$\sum _{\omega }x^{\omega }|(Y^{X})_{\omega ,g}|=\prod _{q\in g}f(x_{1}^{|q|},x_{2}^{|q|},x_{3}^{|q|},\ldots ),$

which equals

$f(x_{1},x_{2},\ldots )^{j_{1}(g)}f(x_{1}^{2},x_{2}^{2},\ldots )^{j_{2}(g)}\cdots f(x_{1}^{n},x_{2}^{n},\ldots )^{j_{n}(g)}.$

Substituting this for $\sum _{\omega }x^{\omega }|(Y^{X})_{\omega ,g}|\,$ in the sum over all g yields the substituted cycle index as claimed.

References

• Redfield, J. Howard (1927). “The Theory of Group-Reduced Distributions”. American Journal of Mathematics 49 (3): 433–455. doi:10.2307/2370675. JSTOR 2370675. MR1506633. 
• Frank Harary; Ed Palmer (1967). “The Enumeration Methods of Redfield”. American Journal of Mathematics 89 (2): 373–384. doi:10.2307/2373127. JSTOR 2373127. MR0214487. 
• G. Pólya (1937). “Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen”. Acta Mathematica 68 (1): 145–254. doi:10.1007/BF02546665. http://www.springerlink.com/content/9021012252111875/. 
• G. Pólya; R. C. Read (1987). Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds. New York: Springer-Verlag. ISBN 0-387-96413-4. MR0884155 

External links

• Applying the Pólya-Burnside Enumeration Theorem by Hector Zenil and Oleksandr Pavlyk, The Wolfram Demonstrations Project.
• Weisstein, Eric W. "Polya Enumeration Theorem". mathworld.wolfram.com (英語).
• Frederic Chyzak Enumerating alcohols and other classes of chemical molecules, an example of Pólya theory.
• Marko Riedel, Pólya's enumeration theorem and the symbolic method.