Make your own free website on Tripod.com


     5. The Pólya Enumeration Theorem

Let X be a finite set; the reader might like to keep in mind the set of vertices (or edges, or faces) of a polygon or polyhedron; and let G be a finite symmetry group acting on X. Suppose X has n elements, and that G has m elements; we write |X| = n, |G| = m. We may represent the elements of the set X by the integers 1,2,...,n. If g G, then g acts as a permutation of {1,2,...,n}. Now every permutation is uniquely expressible as a composition of cyclic permutations on mutually exclusive subsets of the elements of X. For example, the permutation

æ
ç
è
1 2 3 4 5  6  7 8  9 10 11
2 4 7 1 3 11 5 6  8 10  9
ö
÷
ø
(5.1)


is the composite (1 2 4)(3 7 5)(9 8 6 11)(10), where, e.g., (1 2 4) denotes the cyclic permutation

æ
ç
è
1 2 4
2 4 1
ö
÷
ø

Thus the permutation (5.1) is the composite of one cyclic permutation of length 1, two cyclic permutations of length 3, and one cyclic permutation of length 4, the cyclic permutations acting on disjoint subsets of the set X. In general a permutation of X has the type (a1, a2,...,an} if it consists of a1 permutations of length 1, a2 permutations of length 2,..., an permutations of length n, the permutations having disjoint domains of action; notice that i = 1 nai = n. For example the permutation (5.1) has the type {1,0,2,1,0,0,0,0,0,0,0}. If g has the type {a1,a2,...,an}, we define the cycle index of g to be the monomial

Z(g) = Z(g ; x1,x2,...,xn) = x1a1x2a2 ...xnan.

The cycle index of G is Z(g) = ( g GZ(g) )/m.

Example 5.1 We consider the symmetries of the square as shown in Figure 8.


2Kb

Figure 8: We denote this labeling of the square by 1234.

The group G of symmetries is a group of order 8, which we describe by permutations of the set of vertices {1,2,3,4}. Thus

g1 (Identity) (1 2 3 4) (1 2 3 4)      (cycle index x14 )
g2               (1 2 3 4) (2 3 4 1)      (cycle index x4 )
g3               (1 2 3 4) (3 4 1 2)      (cycle index x22 )
g4               (1 2 3 4) (4 1 2 3)      (cycle index x4 )
g5            (1 2 3 4) (3 2 1 4)      (cycle index x12x2 )
g6            (1 2 3 4) (1 4 3 2)      (cycle index x12x2 )
g7               (1 2 3 4) (2 1 4 3)      (cycle index x22 )
g8               (1 2 3 4) (4 3 2 1)      (cycle index x22 )

Thus the cycle index of G is (x14+2x1 2x2+3x22+2x4)/8.

Now suppose we want to color the elements of X; that is, we have a finite set Y of colors, |Y| = r, and a coloring of X is a function 4 f: X ® Y. For any g G, we regard the colorings f and fg as indistinguishable or equivalent; and a pattern is an equivalence class of colorings. Then Pólya's first theorem is as follows.

Theorem 5.1: The number of patterns is Z(G;r,r,...,r).

Example 5.1: (continued) Suppose the vertices are to be colored red or blue. Then r = 2, and the number of patterns is (16+16+12+4)/8 = 6. In fact, the patterns are represented by the 6 colorings: RRRR, BRRR, BBRR, BRBR, RBBB, BBBB,

1Kb

We now describe Pólya's second theorem. This is really the 'big' theorem and the first theorem is, in fact, deducible from it. Let us enumerate the elements of Y (the 'colors') as y1,y2, ...,yr.

Theorem 5.2: Evaluate Z(G;x1,x2, ...,xn) at xi = j = 1ryji. Then the coefficient of y1n1y2n2 ...yrnr is the number of patterns assigning the color yj to nj elements 5.

Example 5.1: (continued) For the symmetries of the square we know that

Z(G) = (x14+2x1 2x2 +3x22+2x4)/8.

Thus if Y = {R,B}, then the evaluation of Z(G) at xi = Ri+Bi yields

((R+B)4+2(R+B)2(R2+ B2)+3(R2+B2)2 +2(R4+B4))/8 =

R4 + R3B + 2R2B2 + RB3 + B4

(It is, of course, no coincidence that this polynomial is homogeneous (of degree |X| and symmetric. Thus the Pólya Enumeration Theorem tells us that there is one pattern with 4 red vertices (obvious); one pattern with 3 red vertices and 1 blue vertex, represented by the coloring RRRB; 2 patterns with 2 red vertices and 2 blue vertices, represented by the colorings BRRB and RBRB, and the remaining possibilities are analyzed by considerations of symmetry.)

Now, given a pattern, there are the various functions fg : X ® Y, where f is a fixed coloring and g G, in that equivalence class of colorings. These are the homologues, or, more precisely, the homologues of f. Let us revert to our example.

Example 5.1: (continued) As we have seen, there is one coloring in which all vertices are colored red. There is only one homologue, namely RRRR,

1Kb

There is one coloring in which 3 vertices are colored red and one blue. There are 4 homologues, namely BRRR, RBRR, RRBR, RRRB,

1Kb

where one vertex is colored blue. There are two colorings in which 2 vertices are colored red and 2 blue. In the first there are 4 homologues, namely BBRR, RBBR, RRBB, BRRB,

1Kb

In the second there are 2 homologues, namely BRBR, RBRB,

1Kb

The analysis is completed by considerations of symmetry.

Let us show how this conception of homologues agrees with our earlier definition. We are given the group G of permutations of X. Given a coloring f: X ® Y, we consider the subset G0 of G consisting of those g such that fg = f, that is, those movements of X which preserve the coloring. It is easy to see (just as easy as in our earlier, simpler situation) that G0 is a subgroup of G. Corresponding to each coset G0g of G0 in G we have a coloring fg of X and these colorings run through the pattern determined by f. We have described the set of colorings {fg} as the set of homologues of the coloring f; as indicated earlier, they are in one-one correspondence with the cosets of G0 in G.


4 We speak of a coloring of X; this may be literally true or it may merely be a metaphor for a rule for dividing the elements of X into disjoint classes.
5 Of course j = 1r nj = n.


NEXT