Pólya enumeration theorem

Pólya enumeration theorem "Polya theorem" redireciona aqui. For Pólya's theorem for positive polynomials on simplex, see Positive polynomial. For the recurrence of lattice random walks, see Random walk § Higher dimensions.

The Pólya enumeration theorem, also known as the Redfield–Pólya theorem and Pólya counting, is a theorem in combinatorics that both follows from and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. The theorem was first published by J. Howard Redfield in 1927. Dentro 1937 it was independently rediscovered by George Pólya, who then greatly popularized the result by applying it to many counting problems, in particular to the enumeration of chemical compounds.

The Pólya enumeration theorem has been incorporated into symbolic combinatorics and the theory of combinatorial species.

Conteúdo 1 Simplificado, unweighted version 2 Full, weighted version 3 Exemplos 3.1 Necklaces and bracelets 3.2 Colored cubes 3.3 Graphs on three and four vertices 3.4 Rooted ternary trees 4 Prova do teorema 5 Veja também 6 Referências 7 Links externos simplificados, unweighted version Let X be a finite set and let G be a group of permutations of X (or a finite symmetry group that acts on X). The set X may represent a finite set of beads, and G may be a chosen group of permutations of the beads. Por exemplo, if X is a necklace of n beads in a circle, then rotational symmetry is relevant so G is the cyclic group Cn, while if X is a bracelet of n beads in a circle, rotations and reflections are relevant so G is the dihedral group Dn of order 2n. Suppose further that Y is a finite set of colors — the colors of the beads — so that YX is the set of colored arrangements of beads (more formally: YX is the set of functions {displaystyle Xto Y} .) Then the group G acts on YX. The Pólya enumeration theorem counts the number of orbits under G of colored arrangements of beads by the following formula: {estilo de exibição à esquerda|S^{X}/Gright|={fratura {1}{|G|}}soma _{gim G}m^{c(g)}} Onde {estilo de exibição m=|S|} is the number of colors and c(g) is the number of cycles of the group element g when considered as a permutation of X.

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, Suponha que {estilo de exibição f(t)=f_{0}+f_{1}t+f_{2}t^{2}+cdots } is the generating function of the set of colors, so that there are fw colors of weight w for each integer w ≥ 0. In the multivariate case, the weight of each color is a vector of integers and there is a generating function f(t1, t2, ...) that tabulates the number of colors with each given vector of weights.

The enumeration theorem employs another multivariate generating function called the cycle index: {estilo de exibição Z_{G}(t_{1},t_{2},ldots ,t_{n})={fratura {1}{|G|}}soma _{gim G}t_{1}^{c_{1}(g)}t_{2}^{c_{2}(g)}cdots t_{n}^{c_{n}(g)}} where n is the number of elements of X and ck(g) is the number of k-cycles of the group element g as a permutation of X.

A colored arrangement is an orbit of the action of G on the set YX (where Y is the set of colors and YX denotes the set of all functions φ: X→Y). The weight of such an arrangement is defined as the sum of the weights of φ(x) over all x in X. The theorem states that the generating function F of the number of colored arrangements by weight is given by: {estilo de exibição F(t)=Z_{G}(f(t),f(t^{2}),f(t^{3}),ldots ,f(t^{n}))} or in the multivariate case: {estilo de exibição 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 )).} To reduce to the simplified version given earlier, if there are m colors and all have weight 0, then f(t) = m and {estilo de exibição à esquerda|S^{X}/Gright|=F(0)=Z_{G}(m,m,ldots ,m)={fratura {1}{|G|}}soma _{gim G}m^{c(g)}.} In the celebrated application of counting trees (Veja abaixo) 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 Necklaces and bracelets Main article: Necklace (combinatorics) Colored cubes How many ways are there to color the sides of a three-dimensional cube with m 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 {estilo de exibição Z_{C}(t_{1},t_{2},t_{3},t_{4})={fratura {1}{24}}deixei(t_{1}^{6}+6t_{1}^{2}t_{4}+3t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}^{3}certo)} which is obtained by analyzing the action of each of the 24 elements of C on the 6 sides of the cube, see here for the details.

We take all colors to have weight 0 and find that there are {estilo de exibição F(0)=Z_{C}(m,m,m,m)={fratura {1}{24}}deixei(m^{6}+3m^{4}+12m^{3}+8m^{2}certo)} different colorings.

Graphs on three and four vertices A graph on m vertices can be interpreted as an arrangement of colored beads. The set X of "beads" is the set of {estilo de exibição {alguns deles {m}{2}}} possible edges, while the set of colors Y = {Preto, branco} corresponds to edges that are present (Preto) or absent (branco). 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. Desta forma {estilo de exibição f(t)=1+t} is the generating function for the set of colors. The relevant symmetry group is {displaystyle G=S_{m},} the symmetric group on m letters. This group acts on the set X of possible edges: a permutation φ turns the edge {uma, b} into the edge {Phi(uma), Phi(b)}. With these definitions, an isomorphism class of graphs with m vertices is the same as an orbit of the action of G on the set YX of colored arrangements; the number of edges of the graph equals the weight of the arrangement.

All graphs on three vertices Nonisomorphic graphs on three vertices The eight graphs on three vertices (before identifying isomorphic graphs) are shown at the right. There are four isomorphism classes of graphs, also shown at the right.

The cycle index of the group S3 acting on the set of three edges is {estilo de exibição Z_{G}(t_{1},t_{2},t_{3})={fratura {1}{6}}deixei(t_{1}^{3}+3t_{1}t_{2}+2t_{3}certo)} (obtained by inspecting the cycle structure of the action of the group elements; Veja aqui). Desta forma, according to the enumeration theorem, the generating function of graphs on 3 vertices up to isomorphism is {estilo de exibição F(t)=Z_{G}deixei(t+1,t^{2}+1,t^{3}+1certo)={fratura {1}{6}}deixei((t+1)^{3}+3(t+1)(t^{2}+1)+2(t^{3}+1)certo),} which simplifies to {estilo de exibição F(t)=t^{3}+t^{2}+t+1.} Thus there is one graph each with 0 para 3 arestas.

Isomorphism classes of graphs on four vertices.

The cycle index of the group S4 acting on the set of 6 edges is {estilo de exibição Z_{G}(t_{1},t_{2},t_{3},t_{4})={fratura {1}{24}}deixei(t_{1}^{6}+9t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}t_{4}certo)} (see here.) Por isso {estilo de exibição F(t)=Z_{G}deixei(t+1,t^{2}+1,t^{3}+1,t^{4}+1certo)={fratura {(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 {estilo de exibição 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 T3 of rooted ternary trees consists of rooted trees where every node (or non-leaf vertex) has exactly three children (leaves or subtrees). Small ternary trees are shown at right. Note that rooted ternary trees with n nodes are equivalent to rooted trees with n vertices of degree at most 3 (by ignoring the leaves). No geral, two rooted trees are isomorphic when one can be obtained from the other by permuting the children of its nodes. Em outras palavras, the group that acts on the children of a node is the symmetric group S3. We define the weight of such a ternary tree to be the number of nodes (or non-leaf vertices).

Rooted ternary trees on 0, 1, 2, 3 e 4 nós (=non-leaf vertices). The root is shown in blue, the leaves are not shown. Every node has as many leaves as to make the number of its children equal to 3.

One can view a rooted, ternary tree as a recursive object which is either a leaf or a node with three children which are themselves rooted ternary trees. These children are equivalent to beads; the cycle index of the symmetric group S3 that acts on them is {estilo de exibição Z_{S_{3}}(t_{1},t_{2},t_{3})={fratura {t_{1}^{3}+3t_{1}t_{2}+2t_{3}}{6}}.} The Polya enumeration theorem translates the recursive structure of rooted ternary trees into a functional equation for the generating function F(t) of rooted ternary trees by number of nodes. This is achieved by "coloring" the three children with rooted ternary trees, weighted by node number, so that the color generating function is given by {estilo de exibição f(t)=F(t)} which by the enumeration theorem gives {estilo de exibição {fratura {F(t)^{3}+3F(t)F(t^{2})+2F(t^{3})}{6}}} as the generating function for rooted ternary trees, weighted by one less than the node number (since the sum of the children weights does not take the root into account), de modo a {estilo de exibição F(t)=1+tcdot {fratura {F(t)^{3}+3F(t)F(t^{2})+2F(t^{3})}{6}}.} This is equivalent to the following recurrence formula for the number tn of rooted ternary trees with n nodes: {estilo de exibição {começar{alinhado}t_{0}&=1\t_{n+1}&={fratura {1}{6}}deixei(soma _{a+b+c=n}t_{uma}t_{b}t_{c}+3soma _{a+2b=n}t_{uma}t_{b}+2soma _{3a=n}t_{uma}certo)fim{alinhado}}} where a, b and c are nonnegative integers.

The first few values of {estilo de exibição t_{n}} são 1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 (sequence A000598 in the OEIS) 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 {estilo de exibição 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, deixar {estilo de exibição x_{1},x_{2},ldots } be the variables of the generating function f of {estilo de exibição Y} . Given a vector of weights {displaystyle ômega } , deixar {estilo de exibição x^{ómega }} denote the corresponding monomial term of f. Applying Burnside's lemma to orbits of weight {displaystyle ômega } , the number of orbits of this weight is {estilo de exibição {fratura {1}{|G|}}soma _{gim G}deixei|(S^{X})_{ómega ,g}certo|} Onde {estilo de exibição (S^{X})_{ómega ,g}} is the set of colorings of weight {displaystyle ômega } that are also fixed by g. If we then sum over all possible weights, nós obtemos {estilo de exibição F(x_{1},x_{2},ldots )={fratura {1}{|G|}}soma _{gim G,ómega }x^{ómega }deixei|(S^{X})_{ómega ,g}certo|.} Meanwhile a group element g with cycle structure {estilo de exibição j_{1}(g),j_{2}(g),ldots ,j_{n}(g)} will contribute the term {estilo de exibição 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 {displaystyle phi in Y^{X}} if and only if the function φ is constant on every cycle q of g. For every such cycle q, the generating function by weight of |q| identical colors from the set enumerated by f is {estilo de exibição esquerdo(x_{1}^{|q|},x_{2}^{|q|},x_{3}^{|q|},ldots right).} 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, ou seja.

{estilo de exibição {começar{alinhado}soma _{ómega }x^{ómega }deixei|(S^{X})_{ómega ,g}certo|&=prod _{q{texto{ cycle of }}g}abandonou(x_{1}^{|q|},x_{2}^{|q|},x_{3}^{|q|},ldots right)\&=f(x_{1},x_{2},ldots )^{j_{1}(g)}abandonou(x_{1}^{2},x_{2}^{2},ldots right)^{j_{2}(g)}cdots fleft(x_{1}^{n},x_{2}^{n},ldots right)^{j_{n}(g)}fim{alinhado}}} Substituting this in the sum over all g yields the substituted cycle index as claimed.

See also Labelled enumeration theorem References Redfield, J. Howard (1927). "The Theory of Group-Reduced Distributions". Revista Americana de Matemática. 49 (3): 433–455. doi:10.2307/2370675. JSTOR 2370675. MR 1506633. Frank Harary; Ed Palmer (1967). "The Enumeration Methods of Redfield". Revista Americana de Matemática. 89 (2): 373–384. doi:10.2307/2373127. JSTOR 2373127. MR 0214487. G. Enrolar (1937). "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen". Revista de Matemática. 68 (1): 145-254. doi:10.1007/BF02546665. G. Enrolar; R. C. Read (1987). Combinatorial Enumeration of Groups, Gráficos, and Chemical Compounds. Nova york: Springer-Verlag. ISBN 0-387-96413-4. MR 0884155. 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 molecules, an example of Pólya theory. Categorias: Enumerative combinatoricsGraph enumerationTheorems in combinatorics