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

Simplified, 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. For example, 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 .) 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:

where  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, suppose that

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:

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:

or in the multivariate case:

To reduce to the simplified version given earlier, if there are m colors and all have weight 0, then f(t) = m and

In the celebrated application of counting trees (see below) 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

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

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

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  possible edges, while the set of colors Y = {black, white} corresponds to edges that are present (black) or absent (white). 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. Thus  is the generating function for the set of colors. The relevant symmetry group is  the symmetric group on m letters. This group acts on the set X of possible edges: a permutation φ turns the edge {a, b} into the edge {φ(a), φ(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.

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

(obtained by inspecting the cycle structure of the action of the group elements; see here). Thus, according to the enumeration theorem, the generating function of graphs on 3 vertices up to isomorphism is

which simplifies to

Thus there is one graph each with 0 to 3 edges.

The cycle index of the group S4 acting on the set of 6 edges is

(see here.) Hence

which simplifies to

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). In general, two rooted trees are isomorphic when one can be obtained from the other by permuting the children of its nodes. In other words, 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).

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

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  which by the enumeration theorem gives

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), so that

This is equivalent to the following recurrence formula for the number tn of rooted ternary trees with n nodes:

where a, b and c are nonnegative integers.

The first few values of  are

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

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  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, let  be the variables of the generating function f of . Given a vector of weights , let  denote the corresponding monomial term of f. Applying Burnside's lemma to orbits of weight , the number of orbits of this weight is

where  is the set of colorings of weight  that are also fixed by g. If we then sum over all possible weights, we obtain

Meanwhile a group element g with cycle structure  will contribute the term

to the cycle index of G. The element g fixes an element  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

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.

Substituting this in the sum over all g yields the substituted cycle index as claimed.

See also
Labelled enumeration theorem

References

External links
 Applying the Pólya-Burnside Enumeration Theorem by Hector Zenil and Oleksandr Pavlyk, The Wolfram Demonstrations Project.
 
 Frederic Chyzak Enumerating alcohols and other classes of chemical molecules, an example of Pólya theory.

Enumerative combinatorics
Articles containing proofs
Graph enumeration
Theorems in combinatorics
조합론에서 포여 열거 정리(Pólya列擧定理, )는 군의 작용에 대한 궤도의 수를 주어진 무게에 따라 순환 지표를 사용하여 열거하는 정리이다. 번사이드 보조정리의 일반화이다.

정의

무게가 없는 경우의 열거 정리 
다음과 같은 데이터가 주어졌다고 하자.
 유한군 
 유한 집합 . 그 원소를 구슬()이라고 하자.
 의  위의 왼쪽 충실한 작용
 유한 집합 . 그 원소를 색깔()이라고 하자.
그렇다면 는 함수 집합  위에도 역시 다음과 같이 왼쪽 작용을 갖는다.

그렇다면, 포여 열거 정리에 따르면, 의 궤도의 수 는 다음과 같다.

여기서
 는 를  위의 순열로 생각하였을 때 순환들의 수이다.

일반적 열거 정리 
다음과 같은 데이터가 주어졌다고 하자.
 유한군 
 크기 의 유한 집합 . 그 원소를 구슬()이라고 하자.
 의  위의 왼쪽 충실한 작용
 각 다중지표 에 대하여, 유한 집합 . 그 원소를 무게 의 색깔()이라고 하고, 라고 하자. 는 무한 집합일 수 있다. 즉, 무게 함수 에 대하여 각 자연수의 원상은 유한 집합이다.
그렇다면, 는 역시 함수 집합  위에 작용한다. 함수 의 무게 는 각 구슬의 색깔의 무게의 합이다.

다음과 같은 생성 함수를 정의하자.

여기서

이다. 즉, 의  항의 계수는  속이의 함수 가운데, 무게가 인 것들의 수이다. 또한, 다음과 같은 생성 함수를 정의하자.

즉, 의  항의 계수는 무게가 인 색깔의 수이다.

포여 열거 정리에 따르면, 다음이 성립한다.

좌변에서 는 순열군 의 순환 지표이다. 즉, 계산하고자 하는 생성 함수 는 순환 지표 의 특정한 값이다.

무게의 간단한 예로, 색깔 집합 가 유한 집합이며, 무게 집합은 이며, 색깔 의 무게가

의 꼴이라고 잡을 수 있다. 이 경우, 생성 함수의 형식적 변수 는 의 원소로 생각할 수 있다.

예

목걸이 

크기 의 집합 위의, 순환군 의 작용에 대한 궤도들을 목걸이라고 한다. 가지의 색깔을 가질 수 있는, 길이 의 목걸이들의 열거를 생각하자. 이 경우
  (3차 순환군)
 는 크기 의 집합
 는 크기 의 집합
가 된다. 순환군 의 순환 지표는

이다. 여기서 는 오일러 피 함수이다. 따라서, 목걸이의 수는

이다.

무게를 달리 하여 주어진 색깔들의 중복집합을 갖는 목걸이의 수를 셀 수도 있다. 예를 들어, 이며, 각 색깔 의 무게가 , , 이라고 하자. 이 경우 순환 지표는

이며, 포여 열거 정리에 의해 다음과 같은 생성 함수를 얻는다.

예를 들어, 의 계수가 1이므로  색깔의 구슬 두 개와  색깔의 구슬 하나로 이루어진 목걸이의 수는 하나이다.

팔찌 

크기 의 집합 위의, 정이면체군 의 작용에 대한 궤도들을 팔찌라고 한다. 가지의 색깔을 가질 수 있는, 길이 의 팔찌들의 열거를 생각하자. 이 경우
 
 는 크기 의 집합
 는 크기 의 집합
가 된다. 정이면체군 의 순환 지표는

이다. 따라서, 팔찌의 수는

이다.

무게를 달리 하여 주어진 색깔들의 중복집합을 갖는 팔찌의 수를 셀 수도 있다. 예를 들어, 이며, 각 색깔 의 무게가 , , 이라고 하자. 이 경우 순환 지표는

이며, 포여 열거 정리에 의해 다음과 같은 생성 함수를 얻는다.

예를 들어, 의 계수가 1이므로  색깔의 구슬 두 개와  색깔의 구슬 하나로 이루어진 팔찌의 수는 하나이다.

그래프 

개의 꼭짓점을 가지는 그래프의 동형류를 열거한다고 하자. 이는 다음과 같이 생각할 수 있다.
 은 꼭짓점 집합 위의 대칭군이다.
 는 개의 가능한 변의 집합이다.
 . 0은 변이 없는 것, 1은 변이 있는 것을 나타낸다. 0의 무게는 0, 1의 무게는 1이라고 하자. (즉, 그래프의 무게는 변의 수이다.)
예를 들어, 3개의 꼭짓점을 가지는 그래프를 생각하자. 이 경우 순환 지표는

이며, 따라서

이다. 즉, 3개의 꼭짓점과 3개의 변을 가지는 그래프 1개, 3개의 꼭짓점과 2개의 변을 가지는 그래프 1개, 3개의 꼭짓점과 1개의 변을 가지는 그래프 1개, 3개의 꼭짓점과 0개의 변을 가지는 그래프 1개가 존재한다.

마찬가지로, 4개의 꼭짓점을 가지는 그래프를 생각하자. 이 경우 순환 지표는

이며, 따라서

이다. 즉, (예를 들어) 4개의 쪽짓점과 3개의 변을 가지는 그래프의 동형류는 3개가 있다.

트리 
진 트리는 잎이거나, 아니면 개의 진 트리를 가지로 가지는 마디이다. 즉, 진 트리의 집합 는 다음과 같다.

주어진 마디 수의 진 트리를 열거하는 문제를 생각해 보자. 이는 포여 열거 정리로 다음과 같이 다룰 수 있다.
 는 대칭군
 
 . 즉, 각 가지의 "색깔"은 가지에 대응하는 부분 진 트리이다.
 의 무게는 꼭짓점의 수이다. 즉, 그 생성 함수는 이다.
그렇다면, 포여 열거 정리에 의하여 다음과 같은 점화식을 얻는다.

이를 재귀적으로 풀어, 주어진 마디 수의 진 트리의 동형류의 생성 함수 를 계산할 수 있다.

예를 들어, 이라고 하자. 이 경우 순환 지표는

이다. 따라서

이다. 

마찬가지로, 이라고 하자. 이 경우 순환 지표는

이다. 따라서

이다.

역사 
1927년에 미국의 수학자 존 하워드 레드필드(, 1879~1944)가 발견하였으나 널리 알려지지 못했다. 이후 헝가리의 수학자 포여 죄르지가 1937년에 같은 정리를 독자적으로 발견하였고, 이를 화합물의 수를 세는 데 응용하였다.

참고 문헌

외부 링크 
 
 
 
 

군론
열거조합론
대수학 정리
조합론 정리