Counting theorem by Pólya

The Abzählsatz polyA from the enumerative combinatorics and group theory permits the counting, for example, trees , simple graph (with application to chemical compounds) and groups of finite order . Common to these enumeration problems is the symmetry with respect to the operation of a finite group on a set. The theorem was proved by George Pólya in 1937 (and, as later showed, by J. Howard Redfield ) and extends Burnside's lemma .

The counting theorem is part of a whole theory that Pólya developed and, like many approaches in enumerative combinatorics, uses the method of generating polynomials and power series.

formulation

Let be a finite group that operates as a permutation group on a set with elements (see group action ). As a permutation group, each has a clear decomposition into cycles: ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle g\in G}$

${\displaystyle n=1\cdot b_{1}+2\cdot b_{2}+3\cdot b_{3}+\cdots }$,

Thus, 1-cycles (fixed points), 2 cycles, etc. The cycle index of the polynomial (cycles index cycle index ): ${\displaystyle b_{1}}$ ${\displaystyle b_{2}}$ ${\displaystyle G}$

${\displaystyle Z_{G}(t_{1},t_{2},\dotsc )={\frac {1}{|G|}}\sum _{g\in G}t_{1}^{b_{1}(g)}\cdot t_{2}^{b_{2}(g)}\cdots }$

In the case of finite quantities, the products break off at the n-cycle and one has a polynomial.

At the same time let the elements of be colored with a finite number of colors from the set . Let it be the set of these colors (i.e. images ). induces an image in the space of the colors (above ) and then also provides equivalence classes on the colors, so-called patterns (corresponding to orbits or orbits from in ). ${\displaystyle X}$ ${\displaystyle y=|Y|}$ ${\displaystyle Y}$ ${\displaystyle F=Y^{X}}$ ${\displaystyle f\colon X\to Y}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle (g\circ f)(x)=f(g^{-1}(x))}$ ${\displaystyle G}$ ${\displaystyle F}$

The colors are assigned a weight in the general version of the theorem, with values ​​in the rational numbers:

${\displaystyle w\colon F\to \mathbb {Q} }$

${\displaystyle w(f)=\prod _{x\in X}w(f(x))}$.

The weight is constant on each sample, so you have a weight distribution on the set of samples . ${\displaystyle M}$

Pólya's theorem now says that

${\displaystyle \sum _{m\in M}w(m)=Z_{G}(\sum _{f\in F}w(f),\sum _{f\in F}w^{2}(f),\cdots )}$

The formula expresses the sum of the weights over all patterns as the value of the cycle pointer. In the simplest case of weight 1 for all samples, the number of samples is obtained on the left side:

${\displaystyle |M|=|Y^{X}/G|={\frac {1}{|G|}}\sum _{g\in G}y^{b(g)}}$

with the sum of the cycles and the number of colors. This also follows directly from Burnside's lemma and can be seen as the simplest version of Pólya's theorem (without weights). ${\displaystyle b(g)=\sum _{i}b_{i}(g)}$ ${\displaystyle y}$

Another formulation compares the coefficients in two generating functions. On the one hand you have the generating function of the colors

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

with the number of contributions to the color with weight (think, for example, of the coloring of nodes or edges in a graph). On the other hand, one has the generating function , the coefficient of which is the number of samples for the respective weight . If one now substitutes for and for , Pólya's theorem says: ${\displaystyle f_{k}}$ ${\displaystyle k}$ ${\displaystyle F}$ ${\displaystyle k}$ ${\displaystyle f(t)}$ ${\displaystyle \sum _{f\in F}w(f)}$ ${\displaystyle F(t)}$ ${\displaystyle \sum _{m\in M}w(m)}$

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

or when using several variables:

${\displaystyle F(t_{1},t_{2},\ldots )=Z_{G}(f(t_{1},t_{2},\ldots ),f(t_{1}^{2},t_{2}^{2},\ldots ),f(t_{1}^{3},t_{2}^{3},\ldots ),\ldots ,f(t_{1}^{n},t_{2}^{n},\ldots ))}$.

Example: graphs with 3 and 4 nodes

In a graph with node m, so possible edges, a staining with two colors in the space of possible X edges with two colors introduced: black (b) if the edge in the graph is available and white (w) if not so . The symmetry group G is the group of permutations of m nodes (symmetric group of order m). ${\displaystyle {\binom {m}{2}}}$ ${\displaystyle Y=\{b,w\}}$ ${\displaystyle S_{m}}$

Pólya's counting theorem gives the number of non-isomorphic graphs. An isomorphism class corresponds to an orbit of G on the set . The weight corresponds to the number of edges in the graph. With three nodes there are eight graphs which are divided into four isomorphism classes. ${\displaystyle Y^{X}}$

The pointer index is:

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

It is . The generating function is: which gives four isomorphism classes each with 0, 1, 2 and 3 edges. ${\displaystyle f(t)=1+t}$ ${\displaystyle F(t)=Z_{G}(t+1,t^{2}+1,t^{3}+1)={\frac {1}{6}}\left((t+1)^{3}+3(t+1)(t^{2}+1)+2(t^{3}+1)\right)=F(t)=t^{3}+t^{2}+t+1}$

With four nodes with six possible edges one has the symmetric group of order four and the pointer index is:

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

The generating function is

${\displaystyle F(t)=Z_{G}(t+1,t^{2}+1,t^{3}+1,t^{4}+1)={\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}}=F(t)=t^{6}+t^{5}+2t^{4}+3t^{3}+2t^{2}+t+1}$

From this you can read off the number of graphs with a certain number of edges. There are 11 isormorphism classes, one each with the number of edges k = 0,1,5,6, two each with the number of edges k = 2 and k = 4, three with k = 3.

Example: colored cube

Let the six sides of a cube be colored with t colors. The symmetry group G is here the rotation group R, the 24 elements of which are listed in the article Lemma by Burnside . The pointer index is:

${\displaystyle Z_{R}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{24}}\left(t_{1}^{6}+6t_{1}^{2}t_{4}+3t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}^{3}\right)}$

If you use the version of the counting set without weight (or in other words with weight 0 for each color) you get:

${\displaystyle F(t)=Z_{R}(t,t,t,t)={\frac {1}{24}}\left(t^{6}+3t^{4}+12t^{3}+8t^{2}\right)}$

for the number of colorations that are not equivalent with respect to R, depending on the number of colors t.

Example: Ternary root trees

Trees with excellent roots and a maximum of three edges (branches) per node are considered. It can also be viewed as consisting of nodes with exactly three branches, whereby some branches do not point to further inner nodes, but to leaves, i.e. do not continue. The subtrees that attach to a node are its children . A root tree can be built up recursively because the children are also ternary root trees. The symmetry group G is the symmetric group that the children of each node permute. ${\displaystyle S_{3}}$

The pointer index of the symmetrical group with 3 elements is:

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

The weights are the number of nodes, with the number of trees with k nodes, and Pólya's theorem gives the recursion relation: ${\displaystyle F(t)=1+F_{1}t+F_{2}t^{2}+F_{3}t^{3}+\cdots }$ ${\displaystyle F_{k}}$

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

it was set (with the number of nodes as weight), a factor t comes into play in the second term on the right-hand side because the root was not included, this is also taken into account by adding the one. ${\displaystyle t_{i}=t^{i}}$ ${\displaystyle i}$

This in turn is equivalent to the following recursion relation for the number of ternary root trees with n nodes: ${\displaystyle F_{n}}$

${\displaystyle F_{0}=1}$

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

(a, b, c, are non-negative integers).

The first values ​​of are ${\displaystyle F_{n}}$

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241

So one with n = 0,1,2 nodes, 3 with n = 2 nodes, 4 with n = 4 nodes, etc.

literature

• George Pólya: Combinatorial number determinations for groups, graphs and chemical compounds . In: Acta mathematica . tape 68 , no. 1 , 1937, p. 145–254 ( online [accessed July 13, 2019]).
  • an English edition with RC Read was published by Springer 1987: Combinatorial enumeration of groups, graphs, and chemical compounds

• Nicolaas Govert de Bruijn : Pólya's counting theory, patterns for graphs and chemical compounds . In: Konrad Jacobs (Ed.): Selecta mathematica III (=  Heidelberger Taschenbücher Volume 86 ). Springer, Berlin, Heidelberg, New York 1971, ISBN 3-540-05333-6 , pp. 1–26 ( [1] [PDF; accessed July 13, 2019]).

• Frank Harary, Edgar M. Palmer: Graphical Enumeration , Elsevier 2014

Web links

• Pólya Enumeration Theorem , Mathworld

Individual evidence

1. ↑ OEIS A000598