Chapter 9 – Polya’s Enumeration Formula
For black-white colorings of the corners of a floating square, the pattern inventory is 1b4+ 1b3w+ 2b2w2+ 1bw3+ 1w4 There are six non-equivalent colorings.
The symmetries are a closed system.
These eight symmetries generalize to any even n-gon.
Colorings C and C’ are equivalent, C ≈ C’, if there exists a symmetry π* such that π*(C) = C’.
Equivalence Relation
i) transitivity: a ≈ b and b ≈ c a ≈ c
ii) reflexivity: a ≈ a
iii) symmetry: a ≈ b b ≈ a
Corresponding properties of the symmetries are:
i) closure: if π, π’ are symmetries, then so is π π’.
ii) identity symmetry: πI.
iii) inverse: each π has an inverse π-1 with ππ-1 = πI.
The set of symmetries form an algebraic group.
We want to count the number of equivalence classes of two-colorings of the corners of a floating square.
A symmetry motion of the square permutes the 4 corners of the square. Any permutation can be decomposed into a set of cycle permutations. For example,
π3 = a b c d = (ac)(bd).
Each corner permutation creates a permutation of the 16 2-colorings of the corners. For example,
π3 (= 180° rotation) is
These bigger permutations are what are important because of the definition of equivalence.
However, we will be able analyze equivalence classes of square colorings in terms of how the symmetries permute 4 corners, not the 16 colorings.
Lemma: For any two permutations πi, πj in a group G, there exists a unique permutation πk
πk = πi-1πj
in G such that πi πk = πj (like solving ax = b)
Proof: πi (πi-1πj) = (πiπi-1) πj = πIπj = πj
Section 9.2
Ideally, if N is number of equivalence classes of the 2-colorings and 8 =|G| is the number of symmetries of a square, then N = 16/8. But no equiv. class has size 8.
Equivalence classes are not size 8 because several symmetries map a coloring C into itself; also several symmetries may map C to the same other C’.
Somehow we need to account for such multiplicities (multiple π’s mapping C to C or mapping C or C’).
Consider the 3 rotational symmetries 0°, 120°, 240°
3 + 1 + 1 + 1 + 1 + 1 + 1 + 3 = 12, now divide by 3
For C10, π1, π3, π7, and π8 leave C10 fixed
and π2, π4, π5, and π6 map C10 to C11.
By the Lemma, we can express π4 as π2πk and similarly for π5 , π6 , and even for π2 . E.g. π5 = π2π8.
Note that the πk’s we use must leave C11 fixed.
Thus, the number of π’s that map C10 to C11 is equal to the number of π’s that leave C11 fixed.
The ideal formula of dividing the no. colorings by no. of symmetries must be modified to count the multiplicities of colorings left fixed.
That is, if (C) denotes the number of π’s that leave a coloring C fixed, then
for each equivalence class E, where |G| is the number of symmetries in G. Illustrate with C2.
Theorem (Burnside, 1897) Let G be a group of permutations on the set S (corners of a square). Let T be any collection of colorings of S (i.e., 2-coloring of the corners) that is closed under G. Then the number N of equivalence classes of T is
where (π) is the number of colorings in T left fixed by π is pronounced ‘psi’).
Both formulas count all occurrences of a symmetry leaving a coloring fixed. The first sums over how many times a coloring is left fixed by various π’s; the second sums over how many times a π leaves fixed various colorings. Similar to how counting the number of times an edge contacts a vertex gives: sum(deg) = 2x(no. of edges)
Example 2: How many different 2-colorings of the bands of a 2- and a 3-band baton are there if the baton is unoriented.
There are two symmetries- 0° and 180° rotations.
In case of 2-band, there are 22 total colorings, all left fixed by the 0° rotation; that is, Y(0°)= 4.
To be left fixed by a 180° rotation, both bands must be the same color. So Y(180°)= 2.
Now plugging into Burnside’s formula, we have
= ½{Y(0°)+Y(180°)}= ½{4+2) = 3.
For 3-bands, Y(0°)= 23=8. And for the 180° rotation, the two end bands must be the same color (they interchange) and the middle band stays fixed and can be any color.
Y(180°)= 2•2=4. And the formula is now ½{8+4} = 6.
Example 3: Suppose a necklace can be made from beads of three colors—black, white and red. How many different necklaces with 3 beads are there?
To make it easier to visualize the symmetries, we think of the 3 beads spaced evenly around the necklace. There are 3 symmetries of a necklace (our necklaces cannot be flipped). We can rotate the necklace 0°, 120°, and 240° (=-120°).
A 0° rotation leaves all 33 necklaces fixed. So Y(0°)= 33=27.
If the bead colors do not move when you rotate 120°, they must all be the same color. If just one was white, it would move when you rotate 120°. So Y(120°)= Y(-120°) = 3.
Answer: 1/3{27+3+3}= 11.
Section 9.3: The Cycle Index
A coloring C is left fixed by π if and only if
for each corner v, v and π(v) are the same color.
In particular, all the vertices in each cycle of π must be the same color
Cycle structure representation of a symmetry π encodes the number of cycles of π of different lengths; e.g., for π3, it is (x2)2.
Then (π) = 2number of cycles in π
Cycle index of G, PG(x1, x2, x3, . . .), is defined to be
PG(x1, x2, x3, . . .) = str. rep. of π
For 2-colorings of the corners of a square
PG(x1, x2, x4) = (1/8){x14 + 2×4 + 3×22 + 2x12x2}
And setting all xi = 2 in PG(x1, x2, x4), we have
(1/8){24 + 2•2 + 3•22 + 2•22•2}= (1/8){16+4+12+16}=48/8= 6
And for m-colorings, (1/8){m4 + 2m + 3m2 + 2•m3}
Theorem: Let S be a set of elements (corners of a square) and G be a group of symmetries of S that acts to induce an equivalence relation on the set of m-colorings of S. Then the number N of non-equivalent colorings is given by setting each xi = m in the cycle index:
N = PG(m, m, m, . . .)
Example 1: Coloring Necklaces For n = 3 and 8, find the number of n-bead necklaces using three colors of beads.
The 3-bead necklace was studied in Sect. 9.1: Example 3.
The 3 rotations are 0°, 120°,240°(=120°). The cycle structure representations are: 0° x13, 120° x3, 240° x3.
PG(x1, x3) = (1/3){x13 + 2×3}. Ans: (1/3){33 + 2•3) = 11
For each of the 8 rotations, 0°, 45°,90°,135°, 180°, 225°, 270°, 315°of the necklace, we need the cycle structure rep.’s
0° x18, 45° x8, 90° x42, 135° x8,
180° x24, 225° x8 270° x42 315° x8
PG(x1, x2, x4, x8) = (1/8){x18 + 4×8 + 2×42 + x24}
Ans: (1/8){38 + 4•3 + 2•32 + 34}
Section 9.4
Make an inventory of the colorings left fixed by each π in terms of the numbers of black and white corners
Theorem (Polya’s Enumeration Formula)
The pattern inventory of 2-colorings of the corners of a figure with group of symmetries G is given by the cycle index with xi = (bi + wi).
Example 1: Determine the pattern inventory for 3-bead (rotating) necklaces using black and white colors. Repeat for black, white, and red colors.
We just determined the cycle index for the problem:
PG(x1, x3) = (1/3){x13 + 2×3}
Now just substitute xi = (bi + wi), yielding
(1/3){ (b + w)3 + 2(b3 + w3) }
With three colors: (1/3){ (b + w + r)3 + 2(b3 + w3 + r3) }
Example 2: Find the number of 7-bead necklaces using three black and four white beads.
Because the length of a cycle must divide the number of beads, except for the identity rotation with cycle rep. x17, all other rotations must have the cycle rep. x7. So the pattern inventory is
(1/7){ (b + w)7 + 6(b7 + w7) }
The coef. of b3w4 will be
(1/7){coef. of b3w4 in (b + w)7} = (1/7)C(7,3).
Example 4: Find the pattern inventory for black-white corner colorings of a floating cube.
Besides identity rotation with cycle rep. x18 , we have
a) about centers of 3 pairs of opposite faces-
rotations of 90° 3×42 , 180° 3×24, 270° (=-90°) 3×42
b) about centers of 6 pairs of opposite edges 6×24
c) about 4 pairs of opposite corners: 120° & 240° 8x12x32
PG(x1, x2, x4, x8) = (1/24){x18 + 6×42 + 9×24+ 8x12x32}
Now set xi = (bi + wi)
Kombinatorische anzahlbestimmungen für gruppen, graphen und chemische verbindungen
φ(C) =|G |