Pólya enumeration theorem

From Wikipedia, the free encyclopedia

This article or section is in need of attention from an expert on the subject.
Please help recruit one or improve this article yourself. See the talk page for details.
Please consider using {{Expert-subject}} to associate this request with a WikiProject

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

The Pólya enumeration theorem (PET), also known as Redfield–Pólya's Theorem, is a theorem in combinatorics, generalizing Burnside's lemma about number of orbits. This theorem was first discovered and published by Redfield in 1927 but its importance was overlooked and Redfield's publication was not noticed by most of mathematical community. Independently the same result was proved by Pólya in 1937, who also demonstrated a number of its applications, in particular to enumeration of chemical compounds.

The PET gave rise to symbolic operators and symbolic methods in enumerative combinatorics and was generalized to the fundamental theorem of combinatorial enumeration.

1 Informal PET statement
2 Definitions for the univariate case
- 2.1 Generating function by weight of the objects being distributed into the slots
- 2.2 Generating function by weight of the filled slot configurations (orbits)
3 Theorem statement
4 Example computations
5 Formal statement of the theorem
6 Proof of theorem
7 References
8 Notes
9 External links

[edit] Informal PET statement

Suppose you have a set of n slots and a set of objects being distributed into these slots and a generating function f(a, b, ...) of the objects by weight. Furthermore there is a permutation group A 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 A). 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(A) of A i.e.

$Z(A)(t_1, t_2, \ldots, t_n) = \frac{1}{|A|} \sum_{g\in A} t_1^{j_1(g)} t_2^{j_2(g)} \cdots t_n^{j_n(g)}$

$t_1 = f(a, b, \ldots), \; t_2 = f(a^2, b^2, \ldots), \; t_3 = f(a^3, b^3, \ldots), \; \ldots \; t_n = f(a^n, b^n, \ldots).$

[edit] Definitions for the univariate case

We have two finite sets $X\,$ and $Y\,$ , as well as a weight function $w: Y\rightarrow \mathbb{N}$ . If $n=|X|\,$ , without loss of generality we can assume that $X = \{1,2,\ldots,n\}$ .

Consider the set of all mappings $F = \{ f\mid f:X\rightarrow Y \}$ . We can define the weight of a function $f\in F\,$ to be

$w(f) = \sum_{x\in X} w\left(f(x)\right)$ .

Every subgroup of the symmetric group on $n\,$ elements, $S_{n}\,$ , acts on $X\,$ through permutations. If $A\,$ is one such subgroup, an equivalence relation $\sim_{A}\,$ on $F\,$ is defined as

$f \sim_{A} g\quad\Longleftrightarrow\quad f = g\circ a$ for some $a\in A$

Denote by $[f] = \{ g \in F\mid f \sim_{A} g \}$ the equivalence class of $f\,$ with respect to this equivalence relation. $[f]\,$ is also called the orbit of $f\,$ . Since each $a \in A\,$ acts bijectively on $X\,$ , then

$w(g) = \sum_{x\in X} w\left(g(x)\right) = \sum_{x\in X} w\left(g(a\circ x))\right) = \sum_{x\in X} w\left(f(x)\right) = w(f)$

Therefore we can safely define $w([f]) = w(f)\,$ . In other words, permuting the summands of a sum does not change the value of the sum.

[edit] Generating function by weight of the objects being distributed into the slots

Let

$c_k = \left|\{ y\in Y \mid w(y)=k \}\right|$ - the number of elements of $Y\,$ of weight $k\,$ ;

The generating function by weight of the source objects is

$c(t) = \sum_k c_k\cdot t^k$

[edit] Generating function by weight of the filled slot configurations (orbits)

Let

$C_k = \left|\{ [f] \mid w([f])=k \}\right|$ - the number of orbits of weight $k\,$ ;

The generating function of the filled slot configurations is

$C(t) = \sum_k C_k\cdot t^k$ .

[edit] Theorem statement

Given all the above definitions, Pólya's enumeration theorem asserts that

$C(t) = Z(A)(c(t),c(t^2),\ldots,c(t^n))\,$

where $Z(A)\,$ is the cycle index of $A\,$ .

[edit] Example computations

[edit] 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. 8 of them ( $\tbinom{3}{2}$ gives the number of pairs of vertices, i.e. edges, chosen from among three vertices).

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 $X \,$ is the set of all edges between $m\,$ vertices and $Y\,$ is $\{0, 1 \}\,$ . Each mapping $X \rightarrow Y\,$ defines a graph on the $m\,$ vertices. If we define $w(y) = y , \forall y\in Y$ , then $w(f)\,$ is the number of edges in the graph resulting from $f\,$ . Clearly, $c(t) = t + 1\,$ - there are 2 elements in $Y\,$ , one of weight 0 and one of weight 1.

The graph preserving edge permutations are directly generated by permutations of the vertices. Therefore, the subgroup $A\,$ of $S_{m \choose 2}$ acting on the edges (the edge permutation group of the graph) is of size $m!\,$ .

The cycle index of the permutation group of the edges is^[1]

$Z_A = \frac{1}{6} \left(t_1^3 + 3 t_1 t_2 + 2 t_3 \right).$

It follows from the enumeration theorem that the generating function of the non-isomorphic graphs on 3 vertices $C(t)\,$ is

$C(t) = \frac{1}{6} \left((t+1)^3 + 3 (t+1) (t^2+1) + 2 (t^3+1) \right)$

$t^3+t^2+t+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.

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) is:^[2]

$Z_A = \frac{1}{24} \left( t_1^6 + 9 t_1^2 t_2^2 + 8 t_3^2 + 6 t_2 t_4 \right).$

Hence

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

$t^6 + t^5 + 2 t^4 + 3 t^3 + 2 t^2 + t + 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 can be found in the GNUstep cookbook.^[3]

[edit] Enumerating rooted ternary trees

The set T3 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 there is a direct bijection between ternary trees with N non-leaf vertices and arbitrary trees with N vertices and degree at most 3.

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

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₃.

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 of $t i$ are

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 (sequence A000598 in OEIS)

[edit] Enumerating 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 (sequence A120445 in OEIS)

This problem appeared on the newsgroup es.ciencia.matematicas.^[4]

[edit] Enumerating 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 cycle index of the permutation group C of the faces is^[5]

$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{align} g(x, y, z) &{} = \frac{1}{24} (x+y+z)^6 \\ &{}\quad + \frac{1}{4} (x+y+z)^2 (x^4+y^4+z^4) \\ &{}\quad + \frac{1}{8} (x+y+z)^2 (x^2+y^2+z^2)^2 \\ &{}\quad + \frac{1}{3} (x^3+y^3+z^3)^2 \\ &{}\quad + \frac{1}{4} (x^2+y^2+z^2)^3 \end{align}$

$\begin{align} 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 \\ & {}\quad + 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 \\ & {}\quad + 6\,x^2\,y^2\,z^2+3\,x^3\,y\,z^2+2\,x^4\,z^2+y^5\,z\\ &{}\quad + 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 \\ & {}\quad + 2\,x^2\,y^ 4+2\,x^3\,y^3+2\,x^4\,y^2+x^5\,y+x^6. \end{align}$

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

The following statement of the theorem is for the general multivariate case as in the example of the colored necklaces and cubes.

Let $A$ be a group acting on a set $X$ (the "slots") and consider the set $Y X$ of all functions from a set $X$ to a weighted set $Y$ (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 $A$ on $Y X$ (the equivalence classes of configurations induced by X) is given by

$Z(A)\left(\sum_{y\in Y} \omega(y), \sum_{y\in Y} \omega(y)^2, \ldots, \sum_{y\in Y} \omega(y)^n\right)$ .

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

$\sum_{y\in Y} \omega(y) = f(a, b, c, \ldots)$

where

$f(a, b, c, \ldots) \,\!$

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

$\sum_{y\in Y} \omega(y)^k = f(a^k, b^k, c^k, \ldots)$

and we obtain the alternate form

$Z(A)( f(a, b, c, \ldots), f(a^2, b^2, c^2, \ldots), f(a^3, b^3, c^3, \ldots), \ldots f(a^n, b^n, c^n, \ldots)). \,\!$

[edit] Proof of 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 $Y X$ fixed by the permutation g of A over all permutations g. This value is a number and yields the count of the orbits, whereas PET enumerates orbits by weight, a more detailed classification, from which the count may be recovered by setting all variables of the weight function to one.

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

$\frac{1}{|A|} \sum_{g\in A} |\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}{|A|} \sum_{g\in A} |\mbox{Fix}_\omega(g)| = \frac{1}{|A|} \sum_{g\in A} \sum_{\omega} \omega |\mbox{Fix}_\omega(g)|.$

Let the cycle structure of g be represented by

$t_1^{j_1(g)} t_2^{j_2(g)} \cdots t_n^{j_n(g)}.$

If g fixes an element of $Y X$ then it must be 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(a, b, c, ...) is