Pólya enumeration theorem

From Wikipedia, the free encyclopedia

"Enumeration theorem" redirects here. For its labelled counterpart, see Labelled enumeration theorem.

The Pólya enumeration theorem (also known as PET) is a theorem in combinatorics. Suppose you have a set of n slots and a set of objects being distributed into these slots and a generating function f(x, y, ...) of the objects by weight. Furthermore there is a permutation group G acting on the slots that creates equivalence classes of filled slot configurations (two configurations are equivalent if one may be obtained from the other by a permutation from G). Then the generating function of the equivalence classes by weight, where the weight of a configuration is the sum of the weights of the objects in the slots, is obtained by evaluating the cycle index Z(G) of G i.e.

$Z(G)(a_1, a_2, \ldots, a_n) = \frac{1}{|G|} \sum_{g\in G} a_1^{j_1(g)} a_2^{j_2(g)} \cdots a_n^{j_n(g)}$

$a_1 = f(x, y, \ldots), \; a_2 = f(x^2, y^2, \ldots), \; a_3 = f(x^3, y^3, \ldots), \; \ldots \; a_n = f(x^n, y^n, \ldots).$

The PET is used to create symbolic operators in the fundamental theorem of combinatorial enumeration.

1 Example computation: enumerating graphs on three and four vertices by the number of edges
2 Example computation: enumerating rooted ternary trees
3 Example computation: necklaces with double colors
4 Example computation: Knights of the Round Table
5 Example computation: colored cubes
6 Formal statement of the theorem
7 Proof of the theorem
8 References
9 External links

[edit] Example computation: enumerating graphs on three and four vertices by the number of edges

The graphs on three vertices without taking symmetries into account are shown at right. There are $2^{3 \choose 2}$ i.e. eight of them.

All graphs on three vertices.

We want to enumerate these graphs taking symmetries into account. There are only four nonisomorphic graphs, also shown at right.

Nonisomorphic graphs on three vertices.

In this problem the slots are the possible edges (vertex pairs) and the objects that go into them are 1 (size zero, edge not present) and z (size one, edge present), so the object generating function by weight is f(z) = z+1.

The computation of the cycle index of the permutation group G of the edges is shown here and it yields

$Z(G) = \frac{1}{6} \left(a_1^3 + 3 a_1 a_2 + 2 a_3 \right).$

It follows that the generating function g(z) of graphs on three vertices by the number of edges is

$\frac{1}{6} \left((z+1)^3 + 3 (z+1) (z^2+1) + 2 (z^3+1) \right)$

$z^3+z^2+z+1\,$

which says that there is one graph with three edges, one with two, one with one edge, and one with no edges.

Nonisomorphic graphs on four vertices.

An analogous computation yields the cycle index of the edge permutation group for graphs on four vertices, which has degree six (there are six edges) and order twenty-four (each vertex permutation of the four vertices induces an edge permutation):

$Z(G) = \frac{1}{24} \left( a_1^6 + 9 a_1^2 a_2^2 + 8 a_3^2 + 6 a_2 a_4 \right).$

Hence the generating function g(z) of graphs on four vertices by the number of edges is

$\frac{1}{24} \left( (z+1)^6 + 9 (z+1)^2 (z^2+1)^2 + 8 (z^3+1)^2 + 6 (z^2+1) (z^4+1) \right).$

$z^6 + z^5 + 2 z^4 + 3 z^3 + 2 z^2 + z + 1.\,$

These graphs are shown at right.

A program that computes the generating function of the nonisomorphic graphs on n vertices as well as a detailed description of the algorithm used maybe found in the GNUstep cookbook, which is here.

[edit] Example computation: enumerating rooted ternary trees

The set T3 of rooted ternary trees consists of rooted trees where every node has exactly three children. Small ternary trees are shown at right.

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

Unlike e.g. binary trees, these trees are not planar, i.e. two trees that can be obtained from one another by repeatedly permuting the children of some node are considered equivalent. In other words, the group that acts on the children of a node is the symmetric group S₃ rather than the identity group E₃. (The group that acts on the two children of a node in a binary tree is the identity group E₂, and in a planar tree of degree k, the group is E_k.)

We use the following recursive decomposition of T3: an element of T3 is either a leaf of size zero, or a node with three children, where the order of the children is not important. The slots in this problem are the three slots where the children are attached to their parent node, and the objects that go into them are the elements of T3 itself. The group that acts on the slots is the symmetric group S₃ with cycle index

$Z(S_3) = \frac{1}{6} \left( a_1^3 + 3 a_1 a_2 + 2 a_3 \right).$

It follows that the functional equation for the generating function T(z) of the set T3 of rooted ternary trees is

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

This translates into the following recurrence relation for the number t_n of rooted ternary trees on n nodes:

$t_0 = 1\,$

and

$t_n = \frac{1}{6} \left( \sum_{a + b + c = n-1} t_a t_b t_c + 3 \sum_{a + 2b = n-1} t_a t_b + 2 \sum_{3a = n-1} t_a \right) \mbox{ when } n>0$

where a, b and c are nonnegative integers.

The first few values are

$\begin{matrix} & t_0=1, \; t_1=1, \; t_2=1, \; t_3=2, \; t_4=4, \; t_5=8, \; t_6=17, \; & \\ & t_7=39, \; t_8=89, \; t_9=211, \; t_{10}=507, \; & \\ & t_{11}=1238, \; t_{12}=3057, \; t_{13}=7639, \; t_{14}=19241. & \end{matrix}$

More information about this sequence may be found in the OEIS, the link is here.

[edit] Example computation: necklaces with double colors

Suppose you have a necklace containing $2 n$ beads of $n$ different colors, where every color is present exactly twice. How many different necklaces are there where two necklaces are considered equivalent if there exists a sequence of rotations and/or reflections that transforms one into the other?

In this problem the slots are the $2 n$ locations where beads may be placed on the necklace and the objects that go into them are the $2 n$ beads. The group that acts on the slots is the dihedral group $D 2 n .$ The three types of symmetries that may occur are illustrated at right for the case $n = 4.$

Three types of dihedral symmetries on necklaces with eight beads and four colors with two beads each.

They are: rotations, reflections in an axis passing through opposite beads and reflections in an axis passing through opposite links.

The cycle index of the dihedral group is $D 2 n$ is

$Z(D_{2n}) = \frac{1}{4n} \left( \sum_{d|2n} \varphi(d) a_d^{2n/d} + n \, a_1^2 a_2^{n-1} + n \, a_2^n \right),$

where the sum represents the rotations, the second term the reflections in an axis passing through opposite beads, and the third term, the reflections in an axis passing through opposite links.

Let the variable $c 1$ represent the first color, $c 2$ the second, $c 3$ the third and so on, up to $c n$ . The number of necklaces is then given by

$[c_1^2 \, c_2^2 \, c_3^2 \, \cdots \, c_n^2] Z(D_{2n})(c_1, c_2, c_3, \ldots c_n).$

Considering the rotations first, we see that only $d = 1$ and $d = 2$ contribute, namely through

$[c_1^2 \, c_2^2 \, \cdots \, c_n^2] (c_1 + c_2 + \cdots + c_n)^{2n} = {2n \choose 2, 2, \ldots 2} = \frac{(2n)!}{2^n}$

and

$[c_1^2 \, c_2^2 \, \cdots \, c_n^2] (c_1^2 + c_2^2 + \cdots + c_n^2)^n = {n \choose 1, 1, \ldots 1} = n!.$

The reflections in an axis passing through opposite beads contribute

$n [c_1^2 \, c_2^2 \, \cdots \, c_n^2] (c_1 + c_2 + \cdots + c_n)^2 (c_1^2 + c_2^2 + \cdots + c_n^2)^{n-1}$

$n \, n \, (n-1)! = n \, n!,$

because there are $n$ ways to choose a color from the first term, and $(n - 1)!$ ways to choose the remaining colors from the second term (sum of squares raised to the $n - 1$ th power).

Finally, the reflections in an axis passing through opposite links contribute

$n [c_1^2 \, c_2^2 \, \cdots \, c_n^2] (c_1^2 + c_2^2 + \cdots + c_n^2)^n = n \, {n \choose 1, 1, \ldots 1} = n \, n!.$

This yields the closed form expression for the number of necklaces containing $n$ different colors exactly twice:

$\frac{1}{4n} \left( \frac{(2n)!}{2^n} \, + \, (2n+1) \, n! \right).$

The first few terms are

$1, \, 2, \, 11, \, 171, \, 5736, \, 312240, \, 24327000, \, 2554072920, \ldots$

This problem appeared on the newsgroup es.ciencia.matematicas and the article is here.

[edit] Example computation: Knights of the Round Table

In this problem we have ten knights seated at the round table. We consider configurations of four knights where two configurations are considered equivalent if one can be obtained from the other by a rotation. We choose one of these configurations at random (this is not the same as choosing four knights at random; there are fewer configurations here than the $\begin{matrix}{10 \choose 4}=210\end{matrix}$ possible different choices of knights) and ask what the probability is that at least two knights are seated next to each other. A configuration where no pair of knights are seated next to each other is shown at right.

Knights of the Round Table.

We first compute the complementary probability i.e. that no knights are seated next to each other. To do this we enumerate the configurations of four knights where no knights are next to each other and divide by the total number of configurations (again of four knights). In this problem the slots are the spaces between the knights and the objects that go into them are segments of one, two, three etc. knights when we count configurations where there are no adjacent knights and segments of zero, one, two etc. knights when we count all configurations. This gives the two object generating functions

$\begin{matrix} f_1(z) & = & z + z^2 + z^3 + z^4 + \ldots & = & \frac{z}{1-z} \\ & \mbox{and } & \\ f_2(z) & = & 1 + z + z^2 + z^3 + z^4 + \ldots & = & \frac{1}{1-z}. \end{matrix}$

The group that permutes the slots (i.e. the spaces between the four knights) is the cyclic group C₄ and its cycle index is

$Z(C_4) = \frac{1}{4} \left( a_1^4 + a_2^2 + 2 a_4 \right).$

It follows that the generating function g₁(z) of configurations with no adjacent knights is

$g_1(z) = \frac{1}{4} \left( \frac{z^4}{(1-z)^4} + \frac{z^4}{(1-z^2)^2} + 2 \frac{z^4}{(1-z^4)}\right)$

and

$g_1(z) = {z}^{4}+{z}^{5}+3\,{z}^{6}+5\,{z}^{7}+O \left( {z}^{8} \right)$

and the generating function g₂(z) of all configurations is

$g_2(z) = \frac{1}{4} \left( \frac{1}{(1-z)^4} + \frac{1}{(1-z^2)^2} + 2 \frac{1}{(1-z^4)}\right)$

and

$g_2(z) = 1+z+3\,{z}^{2}+5\,{z}^{3}+10\,{z}^{4}+14\,{z}^{5}+22\,{z}^{6}+30\,{z}^{7}+O \left( {z}^{8} \right).$

We are counting configurations where the total number of knights is ten and there are six knights in the slots between the four we chose at the beginning.

Hence our complementary probability is

$\frac{[z^6] g_1(z)}{[z^6] g_2(z)} = \frac{3}{22}$

and the probability that at least two knights are adjacent to each other is $19 / 22.$

This problem appeared on the newsgroup es.ciencia.matematicas in a different form; that problem asks for the probability without considering symmetries. The article is here.

[edit] Example computation: colored cubes

Suppose you have an ordinary cube in three-space whose faces may take on one of three colors and are being permuted by the automorphisms of the cube (rotations in three-space). Here the slots are the six faces and the objects that go into them are the three colors. The object generating function by weight is

$f(x, y, z) = x+y+z\,$

which indicates that there are three colors and every color has weight one.

Cube

The computation of the cycle index of the permutation group C of the faces is shown here and it yields

$Z(C) = \frac{1}{24} \left( a_1^6 + 6 a_1^2 a_4 + 3 a_1^2 a_2^2 + 8 a_3^2 + 6 a_2^3 \right) .$

It follows that the generating function of the equivalence classes i.e. colored cubes taking symmetries into account is

$\begin{matrix} g(x, y, z) & = & \frac{1}{24} (x+y+z)^6 \\ & + & \frac{1}{4} (x+y+z)^2 (x^4+y^4+z^4) \\ & + & \frac{1}{8} (x+y+z)^2 (x^2+y^2+z^2)^2 \\ & + & \frac{1}{3} (x^3+y^3+z^3)^2 \\ & + & \frac{1}{4} (x^2+y^2+z^2)^3 \end{matrix}$

$\begin{matrix} g(x, y, z) & = & z^6+y\,z^5+x\,z^5+2\,y^2\,z^4+2\,x\,y\,z^4+2\,x^2\,z^4+2\,y^3\,z^3 \\ & + & 3\,x\,y^2\,z^3+3\,x^2\,y\,z^3+2\,x^3\,z^3+2\,y^4\,z^2+3\,x\,y^3\,z^2 \\ & + & 6\,x^2\,y^2\,z^2+3\,x^3\,y\,z^2+2\,x^4\,z^2+y^5\,z\\ & + & 2\,x\,y^4\,z+3\, x^2\,y^3\,z+3\,x^3\,y^2\,z+2\,x^4\,y\,z+x^5\,z+y^6+x\,y^5 \\ & + & 2\,x^2\,y^ 4+2\,x^3\,y^3+2\,x^4\,y^2+x^5\,y+x^6. \end{matrix}$

This says e.g. that there is one cube using color x on five faces and color z on the sixth, and there are six cubes using x, y, and z twice:

the cube where opposite faces have the same color
the three cubes where two opposite faces have the same color and the remaining two pairs of opposite faces do not
the two cubes where opposite faces always have different colors.

It also says that there are three cubes using color x on three faces, color y on two faces and color z on the remaining face:

the cube where all faces of color x share a vertex
the cube where the two faces of color y are adjacent to all three faces of color x
the cube where one face of color y is adjacent to only two faces of color x.

Note that $g(1, 1, 1)=57\,$ and there are 57 distinct colored cubes in total when there are three colors.

[edit] Formal statement of the theorem

Let $G$ be a group acting on a set $A$ (the "slots") and consider the set $B A$ of all functions from a set $A$ to a weighted set $B$ (the objects) with weight function $ω$ (the "filled slot configurations"), where the weight of a function f is the sum of the weights of its range.

The Pólya enumeration theorem states that the sum of the weights of the orbits of $G$ on $B A$ (the equivalence classes of configurations induced by G) is given by

$Z(G)\left(\sum_{b\in B} \omega(b), \sum_{b\in B} \omega(b)^2, \ldots, \sum_{b\in B} \omega(b)^n\right)$ .

When $ω(b)$ is a monomial in the variables $x, y, z, \ldots$ (including constants) we have

$\sum_{b\in B} \omega(b) = f(x, y, z, \ldots)$

where

$f(x, y, z, \ldots) \,\!$

is the generating function of the set B by weight. Hence

$\sum_{b\in B} \omega(b)^k = f(x^k, y^k, z^k, \ldots)$

and we obtain the alternate form

$Z(G)( f(x, y, z, \ldots), f(x^2, y^2, z^2, \ldots), f(x^3, y^3, z^3, \ldots), \ldots f(x^n, y^n, z^n, \ldots)). \,\!$

[edit] Proof of the theorem

The Pólya enumeration theorem follows from Burnside's lemma, which says that the number of orbits (equivalence classes of filled slot configurations) is the average of the number of elements of $B A$ fixed by a permutation g of G over all permutations g.

Applying the lemma to orbits of weight $ω$ , the number of orbits of this weight is

$\frac{1}{|G|} \sum_{g\in G} |\mbox{Fix}_\omega(g)|$

where $Fix ω (g)$ is the set of functions of weight $ω$ fixed by g.

Summing over all possible weights we have

$\sum_{\omega} \omega \frac{1}{|G|} \sum_{g\in G} |\mbox{Fix}_\omega(g)| = \frac{1}{|G|} \sum_{g\in G} \sum_{\omega} \omega |\mbox{Fix}_\omega(g)|.$

Let the cycle structure of g be represented by

$a_1^{j_1(g)} a_2^{j_2(g)} \cdots a_n^{j_n(g)}.$

If g fixes an element of $B A$ then it must be constant on every cycle c of g. The generating function by weight of a cycle c of |c| identical elements from the set of objects enumerated by f(x, y, z, ...) is

$f(x^{|c|}, y^{|c|}, z^{|c|}, \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} \omega |\mbox{Fix}_\omega(g)| = \prod_{c\in g} f(x^{|c|}, y^{|c|}, z^{|c|}, \ldots)$

$f(x, y, z, \ldots)^{j_1(g)} f(x^2, y^2, z^2, \ldots)^{j_2(g)} \cdots f(x^n, y^n, z^n)^{j_n(g)}$

and the claim follows.

[edit] References

J. M. Redfield, The theory of group-reduced distributions, Amer. J. Math., 49 (1927) 433-455.
G. Pólya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math., 68 (1937) 145-254.
G. Pólya and R. C. Read, Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds, Springer, New York, 1987.

[edit] External links

Marko Riedel, Pólya's enumeration theorem and the symbolic method.
Marko Riedel, The GNUstep cookbook.
León-Sotelo, Marko Riedel, Alicia en la corte del Rey Arturo, newsgroup es.ciencia.matematicas
Marko Riedel, n-digonos, newsgroup es.ciencia.matematicas
Online Encyclopedia of Integer Sequences, sequence A000598

Not credited, Enumeration Discussion of enumeration techniques, in Spanish.
Emilio Fernandez Moral and Mercedes Sanchez Benito, Pólya's enumeration theorem, historical review, includes proofs, in Spanish.

Retrieved from "http://en.wikipedia.org../../../p/%C3%B3/l/P%C3%B3lya_enumeration_theorem.html"

Category: Combinatorics

Pólya enumeration theorem

From Wikipedia, the free encyclopedia

Contents

[edit] Example computation: enumerating graphs on three and four vertices by the number of edges

[edit] Example computation: enumerating rooted ternary trees

[edit] Example computation: necklaces with double colors

[edit] Example computation: Knights of the Round Table

[edit] Example computation: colored cubes

[edit] Formal statement of the theorem

[edit] Proof of the theorem

[edit] References

[edit] External links

Views

Navigation

Search

In other languages