User:Chas zzz brown/polya enumeration

{{Expert|date=March 2009}}

"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 John Howard 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 in 1937 by George Pólya, 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.

Preliminaries

The weight function

A frequent technique in combinatorics is to use a generating function to count the number of objects in a set S having a desired property. If T(z) is such a generating function of the form:

$T(z)=t_{0}+t_{1}z^{1}+t_{2}z^{2}+\ldots +t_{n}z^{n}+\ldots$

then the coefficient $t_{n}$ typically counts the number of elements of S characterized by the natural n. For example, $t_{n}$ might count the number of partitions of $[1,2,3...,k]$ having exactly n partitions, or the number of graphs with n vertices, or the number of 8-bit binary numbers having n "1"s, and so on. In any case, we then say that an element of S which is counted by $t_{n}$ has a weight of $z^{n}$; and more formally we say there is a weight function

$w:S\rightarrow \mathbb {Z} [z]$

which maps the elements of S to powers of z. This mapping is purely abstract: there is no numeric value to be associated with z which will be squared, cubed, etc. Instead the motivation is that we can then relate the generating function T and the weight function w as follows:

$T(z)=\sum _{s\in S}w(s)$

In some cases, a more complicated generating function over more variables is used to give a more precise ability to count diverse objects. For example, we might use a generating function $T(x,y,z)\in \mathbb {Z} [[x,y,z]]$ of the form:

$T(x,y,z)=t_{0,0,0}x^{0}y^{0}z^{0}+t_{1,0,0}x^{1}y^{0}z^{0}+t_{0,1,0}x^{0}y^{1}z^{0}+\ldots +t_{a,b,c}x^{a}y^{b}z^{c}+\ldots$

to enumerate a set S of colorings of some family of shapes, where $x^{a}y^{b}z^{c}$ represents any coloring having a elements of the shape colored red, b elements colored green and c elements colored blue; and where the corresponding coefficent $t_{a,b,c}$ is the number of colorings having that configuration.

We again say that a coloring to be counted has a weight of $x^{a}y^{b}z^{c}$; and that there is a weight function

$w:S\rightarrow \mathbb {Z} [x,y,z]$

which maps the colorings of the shapes to products of powers of x, y, and z; and we again have the equality:

$T(x,y,z)=\sum _{s\in S}w(s)$

Slots, figures, and mappings

Many combinatorial problems can be expressed as counting equivalence classes of mappings from some domain set D into some range set R; and part of the technique of applying PET is to choose D and R appropriately for the situation at hand.

A natural example of this type of mapping is a coloring of the faces of a cube where each face is either red, green or blue. We let the set F = {1,2,3,4,5,6} represent the six faces of the cube, and the set C = {red, green, blue} be the possible colors of any face. Then a particular coloring c is a function of the form:

$c:F\rightarrow C$

and the set of all such mappings is the set of functions $C^{F}$.

More abstractly, suppose we wish to characterize a graph on three vertices. We let the set $E=\{e_{1},e_{2},e_{3}\}$ be the set of possible edges in such a graph, and let P = {no, yes} represent the two possibilities "no, the edge is not present in the graph" and "yes, the edge is present in the graph". Then a particular graph G can be represented by a mapping of the form:

$f_{G}:E\rightarrow P$

and the set of all such mappings is the set of functions $P^{E}$.

In each case, we have a domain set D which can be thought of as defining a set of "slots to be filled"; and a range set R consisting "figures which can occupy a slot"; and the combinatorial objects under consideration can then be represented by a mapping of slots into figures.

Configurations as equivalence classes of mappings

Our goal is not to count all the functions from the domain set D to the range set R (this is usually a trivial task); instead, there is some symmetry in the problem which renders different mappings as corresponding to the same configuration for the purposes of our counting.

In the case of colorings of the cube, the symmetry is geometric; but in problems of counting objects such as trees, we usually want to consider the order of the children of a node as being irrelevant to whether two trees are identical.

This can be both generalized and formalized by saying that there is a group $A\,$ which acts on the elements of the domain set $D\,$ ("the slots") of our mappings. We define a relation $f\sim _{A}g\,$ for two mappings $f,g\in R^{D}$ if there is an element $a\in A$ such that:

$\forall _{d\in D}(f(d)=g(a(d)))$

Since A is a group, it follows that $\sim _{A}\,$ is an equivalence relation, and this allows us to define the equivalence class $[f]\,$ for each mapping f under the action of A.

We will then define a configuration to be an equivalence class $[f]\,$ of mappings of our domain set ("the slots to be filled") to our range set ("figures which are assigned to slots").

Associating weight functions with the figures, mappings and configurations

As noted initially, our goal is to produce a generating function T which enumerates the various configurations by weight.

In the particular case of colorings of the cube with 3 colors, we want to associate a weight of $x^{a}y^{b}z^{c}$ with any mapping having a red faces, b green faces, and c blue faces. To accomplish this, we first define a weighting function on the figures (range set) as follows:

$w(red)=x;w(green)=y;w(blue)=z\,$

and then for any coloring $c:F\rightarrow \{red,green,blue\}$, we define the weight function W as:

$W(c)=\prod _{m\in F}w(c(m))$

Then a coloring such as (red, green, green, blue, red, red) has a weight of (x y y z x x) = x³ y² z, as was desired.

In the case of graphs on three vertices using the notation above, we define the weight function on the figures as:

$w(no)=1;w(yes)=z\,$

We again define the weight of a mapping $f_{G}:E\rightarrow \{no,yes\}$ which represents a graph G as:

$W(f_{G})=\prod _{e\in E}w(f_{G}(e))$

Then a mapping such as (no, yes, yes) yields a weight of (1 z z) = z²; so a graph with two edges has a weight of z², again as desired.

Furthermore, it follows that if $g\in [f]$ then using the definition of W given in the previous section, $W(g)=W(f)\,$.

To see this, note that since each $a\in A\,$ acts bijectively on $D\,$, then if $g\in [f]$ we have that there exists $a\in A$ such that:

$W(g)=\prod _{d\in D}w\left(g(d)\right)=\prod _{d\in D}w\left(g(a(d)))\right)=\prod _{d\in D}w\left(f(d)\right)=W(f)$

Intuitively, permuting the order of the elements of a product does not change the value of the product. Therefore, we can safely extend the definition of the weight of a mapping to the weight of an equivalence class by way of $W([f])=W(f)\,$.

The question PET answers

This allows us to state the question which the PET will ultimately answer:

Given the domain set D and the range set R, let C be the set of equivalence classes under the action of the group A on D of the set of all functions $D\rightarrow R$. Given the weight function w on R, define the generating function T by:

$T=\sum _{[c]\in C}W([c])=\sum _{[c]\in C}\prod _{d\in D}w(c(d))$

Then the coefficients in the expansion of T count the number of distinct configurations by weight. So the question is: how can we determine the coefficients in the expansion of T?

Informal Statement of the PET

Suppose we have a set X of n objects, and a set Y of labels which will be applied to each of the elements of X. We will say "c is a coloring of X" to mean that c is a function of the form $c:X\rightarrow Y$.

Often there is the additional constraint: there is a group G which acts on X, where G represents some geometric symmetry which renders certain colorings of X equivalent. More formally, we consider two colorings $c_{1}$ and $c_{2}$ to be equivalent if and only if there is there is some element g of G with

$\,\!c_{1}(g(x)){=}c_{2}(x)$

If we are only interested in counting the total number of different equivalent colorings of X, then we can use Burnside's lemma. But we often want to know more specifically how many different equivalent colorings of X there are which satisfy some additional constraints. For example, we might want to count the number of different equivalent colorings of X where exactly two elements of X are assigned the color c₁ from Y.

To this end, we first posit a weighting function w : Y -> R, where R is a ring such as the integers $\mathbf {Z}$ or, more commonly, a polynomial ring over the integers such as $\mathbf {Z} [x]$, $\mathbf {Z} [x,y]$, etc. In any case, R and w are chosen so that w encodes the particular features of Y which will be of interest.

The weighting function is then extended to map colorings into the same ring R; given a coloring c, we define w(c) = sum(w(c(x)).

Z, Z[x], Z[x,y]

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)}$

at

$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 ).$

Definitions for the univariate case

We have two sets $X\,$ and $Y\,$, as well as a weight function $w:Y\rightarrow \mathbb {Z} [t]$. For reasons that will become clear, typically w is defined so that $w(y)=t^{k}$ for some natural k for each $y\in Y$.

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

$W(f)=\prod _{x\in X}w\left(f(x)\right)$.

This implies equality of the weight W for all those functions which are equivalent under the action of the group A. Note that 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. In group theoretical terms, $[f]\,$ is the orbit of $f\,$ under the action of A. Since each $a\in A\,$ acts bijectively on $X\,$, then

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

Intuitively, permuting the order of the elements of a product does not change the value of the product. Therefore, we can safely define $W([f])=W(f)\,$.

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}$

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}$.

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\,$.

Example computations

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

$Z_{A}={\frac {1}{6}}\left(t_{1}^{3}+3t_{1}t_{2}+2t_{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)$

or

$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:

$Z_{A}={\frac {1}{24}}\left(t_{1}^{6}+9t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{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).$

or

$t^{6}+t^{5}+2t^{4}+3t^{3}+2t^{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.

Enumerating rooted ternary trees

X

Ternary trees on 0, 1, 2, 3 and 4 vertices/nodes under the two definitions given in the article.

The set T3 of rooted ternary trees consists of rooted trees with outgoing degree <= 3. Examples of these trees on 0, 1, 2, 3, and 4 vertexes is shown as def. 1 in the figure at the right.

An alternative definition which is more amenable to enumeration is to define T3 as the set of trees having at least one vertex, and where every vertex has outgoing degree 0 (in which case we will call the vertex a leaf), or outgoing degree 3 (in which case we will call the vertex a node). Examples shown at right with 0, 1, 2, 3, and 4 nodes is shown as def. 2 in the figure. Note that there is a bijection between the objects in the two definitions by mapping vertices in the first definition to nodes in the second definition. The second definition will be used in the remainder of this section.

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₃; and the figures at right are actually representatives of the equivalence classes of trees under this action when it is applied to every node of the tree.

Using the PET, we will find a generating function T which enumerates the number of equivalence classes for ternary trees having 0, 1, 2, ... nodes.

We first note the following recursive definition of T3: an element of T3 is either a leaf, or a root node with three children which are elements of T3 where ordering of the children is ignored.

We can express "f is a root node with three children in T3" as saying that f is a function of the form:

$f:\{1,2,3\}\rightarrow T3$

and we want to use the PET to count only the equivalence classes $[f]$ of such functions so that the ordering of the children is ignored.

To apply the PET, our function's domain set is $D=\{1,2,3\}$, and its range set is R = T3. Alternatively we can consider that the "slots" in this problem are the three required children of the root node of the tree, and the "objects" that go into these slots are to be taken as elements of T3 itself.

The group that acts on the domain ("slots") is the symmetric group S₃ with cycle index

$Z(S_{3})={\frac {1}{6}}\left(a_{1}^{3}+3a_{1}a_{2}+2a_{3}\right).$

Define the weight of a figure in T3 as $z^{n}$, where n is the number of nodes in the figure (the range of our weighting function w is therefore the polynomial ring $\mathbb {Z} [z]$). We then have that the generating functions for both the figures and the configurations are the same:

$T(z)=t_{0}+t_{1}z^{1}+t_{2}z^{2}+\ldots +t_{n}z^{n}+\ldots$

(although at this point we only know that t₀ = 1). 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}+3T(z)T(z^{2})+2T(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 the OEIS)

Enumerating necklaces with double colors

Suppose you have a necklace containing $2n$ 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 $2n$ locations where beads may be placed on the necklace and the objects that go into them are the $2n$ beads. The group that acts on the slots is the dihedral group $D_{2n}.$ 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_{2n}$ 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}$

or

$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 the OEIS)

This problem appeared on the newsgroup es.ciencia.matematicas.

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

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

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

${\begin{aligned}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{aligned}}$

or

${\begin{aligned}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{aligned}}$

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.

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 $\omega$ (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 $\omega (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 )).\,\!$

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 $\omega$, the number of orbits of this weight is

${\frac {1}{|A|}}\sum _{g\in A}|{\mbox{Fix}}_{\omega }(g)|$

where ${\mbox{Fix}}_{\omega }(g)$ is the set of functions of weight $\omega$ 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

$f(a^{|q|},b^{|q|},c^{|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 }\omega |{\mbox{Fix}}_{\omega }(g)|=\prod _{q\in g}f(a^{|q|},b^{|q|},c^{|q|},\ldots )$

or

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

Substituting this for $\sum _{\omega }\omega |{\mbox{Fix}}_{\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. MR 1506633.
• Frank Harary (1967). "The Enumeration Methods of Redfield". American Journal of Mathematics. 89 (2): 373–384. doi:10.2307/2373127. MR 0214487. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
• G. Pólya (1937). "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen". Acta Mathematica. 68 (1): 145–254. doi:10.1007/BF02546665.
• G. Pólya (1987). Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds. New York: Springer-Verlag. ISBN 0-387-96413-4. MR 0884155. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

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.
• Frederic Chyzak Enumerating alcohols and other classes of chemical moleculs, an example of Polya theory.