Polya’s Counting Theory - Report

PÓLYA’S COUNTING THEORY May 9, 2012 1 Introduction In combinatorics, there are very few formulas that apply comprehensively to all cases of a given problem. Pólya’s Counting Theory is a spectacular tool that allows us to count the number of distinct items given a certain number of colors or other characteristics. Basic questions we might ask are, “How many distinct squares can be made with blue or yellow vertices?” or “How many necklaces with n beads can we create with clear and solid beads?” We will count two objects as ’the same’ if they can be rotated or flipped to produce the same configuration. While these questions may seem uncomplicated, there is a lot of mathematical machinery behind them. Thus, in addition to counting all possible positions for each weight, we must be sure to not recount the configuration again if it is actually the same as another. We can use Burnside’s Lemma to enumerate the number of distinct objects. However, sometimes we will also want to know more information about the characteristics of these distinct objects. Pólya’s Counting Theory is uniquely useful because it will act as a picture function - actually producing a polynomial that demonstrates what the different configurations are, and how many of each exist. As such, it has numerous applications. Some that will be explored here include chemical isomer enumeration, graph theory and music theory. This paper will first work through proving and understanding Pólya’s theory, and then move towards surveying applications. Throughout the paper we will work heavily with examples to illuminate the simplicity of the theorem beyond its notation. 2 2.1 Burnside’s Lemma Group Theory We will first clarify some basic notation. Let S be a finite set. Then |S| denotes the number of its elements. If G is a group, then |G| represents the number of elements in G and is called the order of the group. Finally, if we have a group of permutations of a set S, then |G| is the degree of the permutation group. Gallian [3] provides the following definitions, necessary for Theorem 1 and Theorem 2. Definition 1. Coset of H in G Let G be a group and H a subset of G. For any a ∈ G, the set {ah|h ∈ H} is denoted by aH. Analogously, Ha = {ha|h ∈ H} and aHa−1 = {aha−1 |h ∈ H}. When H is a subgroup of G, the set aH is called the left coset of H in G containing a, whereas Ha is called the right coset of H in G containing a. 1 Definition 2. Stabilizer of a Point Let G be a group of permutations of a set S. For each i ∈ S, let stabG (i) = {φ ∈ G|φ(i) = i}. We call stabG (i) the stabilizer of i in G. The set stabG (i) is a subset of G and is also a subgroup of G. We know it is nonempty because the identity element will certainly fix i ∈ S. If φa , φb ∈ stabG (i), then φa (i) = i and φb (i) = i. Thus −1 −1 φa φ−1 b (i) = φa (φb (i)) = φa (i) = i, which confirms that φa φb ∈ stabG (i). Definition 3. Orbit of a Point Let G be a group of permutations of a set S. For each s ∈ S, let orbG (s) = {φ(s)|φ ∈ G}. The set orbG (s) is a subset of S called the orbit of s under G. All the objects in a given orbit will be considered the same, or isomorphic. For counting purposes, we will be counting the number of orbits. Tucker [10] offers the following definition for the elements fixed by φ. Definition 4. Elements Fixed by φ For any group G of permutations on a set S and any φ in G, we let f ix(φ) = {i ∈ S|φ(i) = i}. This set is called the elements fixed by φ. 2.2 The Orbit-Stabilizer Theorem Gallian [3] also proves the following two theorems. Theorem 1. Lagrange’s Theorem If G is a finite group and H is a subgroup of G, then |H| |G| divides |G|. Moreover, the number of distinct left cosets of H in G is |H| . Proof. Let a1 H,a2 H,. . ., ar H denote the distinct left cosets of H in G. For each a in G, we have aH = ai H for some i and a ∈ aH. Thus, each member of G belongs to one of the cosets ai H. In symbols, G = ai H ∪ · · · ∪ ar H. Since these cosets are disjoint, |G| = |a1 H| + |a2 H| + · · · + |ar H|. Because |ai H| = |H| for each i, we have |G| = r|H|. Here are some basic examples of this theorem. Example 1. Consider the group Z15 and its subgroup H = {0, 3, 6, 9, 12}. Then |H| = 5, which divides 15, and there are 15 5 = 3 distinct left cosets. They are H, 1 + H = {1, 4, 7, 10, 13}, and 2 + H = {2, 5, 8, 10, 14}. 2 Example 2. Consider the dihedral group, D4 . The dihedral group D4 consists of the elements R0 , R90 , R180 , R270 , H, V , D, and D0 , where the Ri0 s are rotations by i degrees. H is a flip with respect to the horizontal line, V is a flip with respect to the vertical line, D is a flip with respect to the diagonal through the lower left corner and the upper right corner, and D0 is a flip with respect to the other diagonal. Then consider the subgroup S = {R0 , H}. As expected, |S| = 2 divides |D4 | = 8 and the subgroup has four distinct left cosets, R0 H, R90 H,R180 H, and R270 H. Theorem 2. Orbit-Stabilizer Theorem Let G be a finite group of permutations of a set S. Then, for any i from S, |G| = |orbG (i)||stabG (i)|. Proof. We know that |stab|G| is the number of distinct left cosets of stabG (i) in G by Lagrange’s G (i)| Theorem. Define a correspondence T : G × S → S by T ((φ, i)) = φ(i). If there is one-to-one correspondence between the left cosets of stabG (i) and the elements in the orbit of i, we are done. To show that T is well-defined, we must show that αstabG (i) = βstabG (i) implies α(i) = β(i). But αstabG (i) = βstabG (i) implies α−1 β ∈ stabG (i), so that (α−1 β)(i) = i and, therefore, β(i) = α(i). Because these arguments can be reversed from the last step to the first step, T is one-to-one. To show T is onto orbG (i), let j ∈ orbG (i). Then α(i) = j for some α ∈ G and T (αstabG (i)) = α(i) = j. Thus T is onto. 2.3 Burnside’s Lemma Tucker [10] provides the following theorem. Theorem 3. Burnside’s Theorem If G is a finite group of permutations on a set S, then the number of orbits of G on S is 1 X |f ix(φ)|. |G| φ∈G Burnside’s Lemma can be described as finding the number of distinct orbits by taking the average size of the fixed sets. Gallian [3] provides the proof. Proof. Let n denote the number of pairs (φ, i), with φ ∈ G, i ∈ S, and φ(i) = i. We begin by counting these pairs in two ways. First, for each particular φ in G, the number of such pairs is exactly |f ix(φ)|, as i runs over S. So, X n= |f ix(φ)|. (1) φ∈G Second, for each particular i in S, observe that |stabG (i)| is exactly the number of pairs of the form (φ, i), as φ runs over G. So, X n= |stabG (i)|. (2) i∈S 3 Figure 1: Fixed by R180 We know that if s and t are in the same orbit of G, then orbG (s) = orbG (t) and |stabG (s)| = |stabG (t)|. So if we choose t ∈ S, sum over orbG (s), and appeal to Theorem 2, we have X |stabG (t)| = |orbG (s)||stabG (s)| = |G|. (3) t∈orbG (s) Finally, by summing over all the elements of G, one orbit at a time, it follows from Equations 1, 2, and 3 that X X |f ix(φ)| = |stabG (i)| = |G| ∗ (number of orbits) φ∈G i∈S and then we are done. 2.4 Enumerating Squares Now that we have established sufficient theory, we will show how this can be applied to a problem involving distinct squares. Two squares will be considered distinct if they cannot be made identical by rotating and/or flipping one of the squares. Example 3. How many distinct squares are there with turquoise and salmon beads at the corners? Let G be the dihedral group, D4 , consisting of the elements defined in Example 2, and let S be the set of not necessarily distinct squares that can be created with turquoise and salmon beads. Since there are 4 corners and 2 colors, there are 24 elements in S. Now we must find how many square configurations each element of D4 fixes. The identity, R0 , fixes all 16 configurations. Both R90 and R270 only fix two elements, namely the square with all turquoise dots and the square with all salmon dots. Note that every element in D4 fixes these two monochrome squares. In addition to these two, R180 also fixes the squares shown in Figure 1. H also fixes the squares in Figure 2 and V fixes those in Figure 3. The six additional squares fixed by D and D0 are shown in Figure 4 and Figure 5. 4 Figure 2: Fixed by H Figure 3: Fixed by V Figure 4: Fixed by D 5 Figure 5: Fixed by D0 g ∈ D4 R0 R90 R180 R270 H V D D0 |f ix(g)| 16 2 4 2 4 4 8 8 Figure 6: Table of |f ix(g)| values 6 Figure 7: Orbit of s Figure 6 shows the order of |f ix(g)| for all elements of D4 . Now we can finally use Theorem 3 to count the number of orbits of D4 on S. 1 1 X |f ix(g)| = (16 + 2 + 4 + 2 + 4 + 4 + 8 + 8) = 6. |G| 8 g∈G We conclude that it is possible to create 6 distinct squares with turquoise and salmon beads at the corners. These 6 orbits can be seen in Figure 8, where each row shows a different orbit, except the first row which shows the two monochrome figures which are each alone in their own orbits. Moreover, Theorem 2 is easily viewed in this context. Consider the upper left square in Figure 7 and call this configuration s. Using elements of D4 , s can be mapped to itself or the other three squares in the same figure. It is fixed by two elements, D0 and R0 . Thus we have that |orbD4 (s)||stabD4 (s)| = 4 ∗ 2 = 8. Unsurprisingly, |D4 | = 8. 2.5 Cube Vertices and Faces Example 4. Let S be the set of vertices of a cube colored black or white, and let G be the set of permutations of S that can be produced by rotating the cube. Since there are 8 vertices, |S| = 28 . There are 24 elements in |G|, which we can split into five categories: 1. The identity 7 Figure 8: All possible square configurations arranged into equivalent rows 8 2. Three 180 degree rotations about lines through the centers of opposite faces 3. Six 180 degree rotations about lines through the centers of opposite edges 4. Three 90 degree rotations and three 270 degree rotations about the lines through the centers of opposite faces 5. Four 120 degree rotations and four 240 degree rotations about lines connecting opposite vertices. The identity fixes all 28 elements of S. The three 180 degree rotations about lines through the centers of opposite faces fix configurations of a cube where, if the cube were sliced in half, the vertices on one side of the cube must match or mirror the vertices on the other side. For example, if the cube in Figure 9 is rotated about the centers of face abcd and face ef gh, then c would be colored the same as a, d the same as b, h the same as f , and e the same as g. Then we have 24 choices, since the second four vertices are dependent on the first four. The six 180 degree rotations about lines through the centers of opposite edges fix 24 configurations. If the cube was rotated about a line connecting eh and ab, then e and h, a and b, c and f , and d and f would have the same color. Again, there are four vertices that are independent, but the other four are dependent on them. The 90 degree rotations fix cubes that have one side of identical vertices and another side of identical vertices. For example, using labels from Figure 9, if we rotated about the centers of face abcd and face ef gh, then a, b, c, and d would need to be colored black or white, and e,f ,g, and h would all need to be colored either black or white. This gives 22 choices. Finally, the 120 degree rotations and 240 rotations each give 24 possible choices. For example, if we rotate the cube in Figure 9 about the line through c and f , then the coloring of both c and f is arbitrary. The vertices b, d and h must be colored identically, and vertices a, g, and e must be colored identically. Then, using Burnside’s Lemma, we have (28 + 3 ∗ 24 + 6 ∗ 24 + 6 ∗ 22 + 8 ∗ 24 )/24 = 23. Thus there are 23 distinct cubes that can be created using either black or white vertices. For the cube, we can also count face colorations. Example 5. Let S be the set of faces of a cube colored black or white, and let G be the set of permutations of S that can be produced by rotating the cube. Since there are 6 faces, |S| = 26 . There are 24 elements in G, which we can split into the same five categories as in Example 4. The identity fixes all 26 elements of S. The second type of rotation fixes 23 elements of S. If we rotate about a line through the center of 9 c b d a h g e f Figure 9: The cube D E C B A F Figure 10: The cube 10 Figure 11: The cube for the fourth rotation face A and face D of Figure 10, then A and D can be either color but B, C, E, and F must be the same. The third type of rotation fixes 23 elements. If we rotate about a line through the center of the edge connecting A and B and the center of the edge connecting E and D, then the pairs C and F , A and B, and E and D must match. The fourth type of rotation fixes 24 elements. If we rotate about a line through the center of face A and face D of Figure 10, then A and D can be either color but B and E must match, as must C and F . The fifth type of rotation fixes 22 elements. If we rotate the cube around a line connecting two opposite vertices as in Figure 11, the “top” three faces must all be colored the same, as must the “bottom” three. Then, using Burnside’s Lemma, we have (26 + 6 ∗ 23 + 3 ∗ 24 + 8 ∗ 22 + 6 ∗ 23 )/24 = 10. Thus there are 10 distinct cubes that can be created using either black or white faces. Since our numbers are still small, we can figure out what these 10 cubes look like without the help of Pólya’s Theorem. There are 2 monochrome cubes and 2 with one face colored differently (either all black with one white or all white with one black). Then there are 2 with two adjacent same-colored faces and 2 with two same-colored faces on opposite sides. Finally, there is 1 with three co-corner faces (only one since it will include both the three co-corner black faces and three co-corner white faces) and 1 with three non co-corner faces. 11 g ∈ D4 R0 R90 R180 R270 H V D D0 |f ix(g)| 34 3 32 3 32 32 33 33 Figure 12: Table of |f ix(g)| values 2.6 More Colors We will now extend our square and cube examples to three colors. This is exceedingly easy since our previous examples already have set up the entire problem. We can extend them to the case with n colors by simply replacing the three with n. Example 6. How many distinct squares are there with turquoise, salmon, and brown beads at the corners? Let G be the dihedral group, D4 = {R0 , R90 , R180 , R270 , H, V, D, D0 }, and let S be the set of not necessarily distinct squares that can be created with turquoise, salmon, and brown beads. Since there are 4 corners and 3 colors, there are 34 elements in S. Now we must find how many square configurations each element of D4 fixes. We can simply use the basic logic followed in Example 3, but since there are 3 color choices there will be 3i instead of 2i fixed elements. Figure 12 shows the order of |f ix(g)| for all elements g in D4 . Now we can use Burnside’s Lemma to count the number of orbits of D4 on S. 1 X 1 |f ix(g)| = (81 + 3 + 9 + 3 + 9 + 9 + 27 + 27) = 21. |G| 8 g∈G We conclude that it is possible to create 21 distinct squares with turquoise and salmon beads at the corners. We can use similar logic to extend Example 13 to the case with three colors. Example 7. Let S be the set of faces of a cube colored black, white, or brown, and let G be the set of permutations of S that can be produced by rotating the cube. Since there are 6 faces, |S| = 36 . There are 24 elements in G, which we can again split into five categories. We will use the exact same logic as in Example 13 to use Burnside’s Lemma, but we will now raise 3 to the various powers, since we have 3 instead of 2 colors. It follows that (36 + 6 ∗ 33 + 3 ∗ 34 + 8 ∗ 32 + 6 ∗ 33 )/24 = 57. 12 Thus there are 57 distinct cubes that can be created using either black, white, or brown faces. Example 8. Finally, we will extend the example to find the number of distinct cubes that can be created using either black, white, or brown vertices. Without revisiting the details of the rotations again, we will apply Burnside’s Lemma to find (38 + 3 ∗ 34 + 6 ∗ 34 + 6 ∗ 32 + 8 ∗ 34 )/24 = 333. Thus there are 333 distinct cubes that can be created with three different colors at the vertices. 3 3.1 Pólya’s Counting Theory The cycle index De Buijn [2] introduces this notation. Note that if S is a finite set, a permutation of S is a one-toone mapping of S onto itself. If a permutation π is given, then we can split S into cycles, which are subsets of S that are cyclically permuted by π. If l is the length of a cycle, and s is any element of that cycle, then the cycle consists of s, πs, π 2 s, . . . , π l−1 s, where π 2 = ππ, π 3 = πππ, etc. Definition 5. Let S be a finite set. If S splits into b1 cycles of length 1, b2 cycles of length 2, etc., then π is of type {b1 , b2 , b3 , . . . }. Definition 6. Let G be a group whose elements are the permutations of S, where |S| = m. We define the polynomial in m variables x1 , x2 , . . . , xm , with nonnegative coefficients, where for each φ ∈ G we form the product xb11 xb22 · · · xbmm , if {b1 , b2 , b3 , . . . } is the type of φ. Then the polynomial PG (x1 , x2 , . . . , xm ) = 1 X b1 b2 x1 x2 · · · xbmm |G| φ∈G is called the cycle index of G. This formula closely resembles Burnside’s Lemma. The key difference is that now we differentiate between cycles of different lengths, and specify how many of each cycle there are. Later, this will allow us to not only count the number of different objects we seek, but also have an idea of what the appearance of each different object is like. Example 9. Consider the simple example when G consists of only the identity permutation. Then the identity permutation is of type {m, 0, 0, . . . } and thus PG = xm 1 . Example 10. Suppose we have a necklace that is made from three beads and four colors. For this example, we can rotate the necklace but we cannot flip it. Then G = {R0 , R120 , R270 } where the three elements of G represent the three possible rotations of the necklace. These three permutations are of type {3, 0, 0, . . . }, {0, 0, 1, 0, . . . }, and {0, 0, 1, 0, . . . }, respectively. The cycle index is then 1 PG = (x31 + 2x3 ). 3 13 It follows that the number of 4-colored strings of three beads is PG (4, 4, 4) = 13 (43 + 2 ∗ 4) = 24. To generalize, the number of n-colored strings of three beads is PG (n, n, n) = 13 (n3 + 2 ∗ n). Example 11. Returning to the example of distinct cube face colorations, the cycle index will allow us to differentiate between permutations of different lengths. Recall that we can split the 24 elements in G into the following five categories: 1. The identity 2. Three 90 degree rotations and three 270 degree rotations about the lines through the centers of opposite faces 3. Three 180 degree rotations about lines through the centers of opposite faces 4. Eight 120 degree rotations about lines connecting opposite vertices 5. Six 180 degree rotations about lines through the centers of opposite edges The five categories produce the types {6, 0, 0, . . . }, {2, 0, 0, 1, 0, . . . },{2, 2, 0, . . . },{0, 0, 2, 0, . . . }, and {0, 3, 0, 0, . . . } respectively. This corresponds to the cycle index PG = 1 6 (x + 6x21 x4 + 3x21 x22 + 8x23 + 6x32 ). 24 1 If we find PG (2, 2, 2, 2), the function will yield the same solution as found in Example 13. And if we find PG (n, n, n, n) to represent n different colors, we can find the number of distinct cubes that can be created using n colors. Known Cycle Indices There are actually formulas for some of the better known cycle indices. The ones that will be of use in this paper are the indices for symmetric groups, cyclic groups, and dihedral groups. But first, Gallian [3] defines what a symmetric group actually is. Definition 7. Let A = {1, 2, . . . , n}. The set of all permutations of A is called the symmetric group of degree n and is denoted by Sn . The order of the group is n! since there are n choices for mapping the first element, n − 1 choices for the mapping of the second, and so on. This group will be particularly useful for our discussion of graph applications. Symmetric groups quickly get large for large values of n, but here are the smallest four: S0 = S1 = {e} S2 = {e, (12)} S3 = {e, (12), (13), (23), (123), (132)} . 14 Theorem 4. The cycle index of the symmetric group Sn is given by Z(Sn ) = X Q (j) Y j 1 skk , j kj ! k k k k where the summation is taken over all partitions (j) of n. Proof. Consider some partition (j) of n where (j) = (j1 , j2 , . . . , jn ). Assume that the cycles of some permutation having cycles given by (j) are ordered in n! different ways. However, for each k, the jk cycles can be ordered Q in jk ! different ways, and can begin in k different elements. Thus, any permutation is represented k k jk jk ! times, so that there are a total of Q kn!jk j ! permutations k k with cycle structure given by (j). This allows us to reindex over (j) rather than the individual permutations, obtaining the cycle structure as stated in the theorem. Before we venture to the formula for cyclic groups, Cn and dihedral groups, Dn , we need the following definition given by Weisstein [12]: Definition 8. The totient function φ(n), also called Euler’s totient function or the Euler-phi function, is defined as the number of positive integers ≤ n that are relatively prime to n, where 1 is counted as being relatively prime to all numbers. For example, there are eight numbers relatively prime to 24 that are less than 24 (1, 5, 7, 11, 13, 17, 19, and 23), so φ(24) = 8. Harary and Palmer [4] give the following formulas: Z(Cn ) = 1X n/k φ(k)sk , n k|n and 1 Z(Dn ) = Z(Cn ) + 2 ( (n−1)/2 1 2 s1 s2 (n−2)/2 1 n/2 + s21 s2 ) 4 (s2 if n odd, if n even. (4) We can easily understand why Z(Dn ) is split into two cases by imagining a necklace of four beads versus a necklace of five beads. With four beads, there are two types of flips: those over the line through the centers of opposite edges, and those over the line connecting opposite vertices. However, with five beads, there is only one type of flip: those over lines connecting a vertex with the center of an opposite edge. This can be extended to any even or odd number of beads, respectively. 15 3.2 Pólya’s Counting Theory (simple version) Tucker [10] provides the following theorem, which is central to this entire paper. It will allow us to not only count the number of distinct orbits, but to also list out and view what all the objects look like. Theorem 5. Pólya’s Enumeration Formula Let S be a set of elements and G be a group of permutations of S that acts to induce an equivalence relation on the colorings of S. The inventory of nonequivalent colorings of S using colors c1 , c2 , . . . , cm is given by the generating function   m m m X X X PG  cj , c2j , . . . , ckj  , (5) j=1 j=1 j=1 where k corresponds to the largest cycle length. So the inventory of colorings of S using three colors, A, B, and C, is given by   PG (A + B + C), (A2 + B 2 + C 2 ), . . . , (Ak + B k + C k ) . 3.3 Pólya’s Counting Theory De Buijn [2] provides the following slightly more formalized version of the theorem. Instead of just colors, De Buijn will use weights, which can represent, for example, a number, variable, or an element of a commutative ring containing the rational numbers. Before we define weights, we must clarify a few other terms. Let D and R be finite sets, so we consider mappings of D into R. The set of all such functions is denoted by RD . Suppose that we are given a group G of permutations of D. This group then introduces an equivalence relation in RD : Two functions f1 ,f2 ∈ RD are called equivalent (denoted f1 ∼ f2 ) if there exists an element g ∈ G such that f1 (g(d)) = f2 (d) for all d ∈ D. We will verify that this is an equivalence relation. 1. We know f ∼ f since G contains the identity permutation. 2. If f1 ∼ f2 , then f2 ∼ f1 because if g ∈ G, then g −1 ∈ G. 3. Finally, if f1 ∼ f2 and f2 ∼ f3 , then f1 ∼ f3 . This is because if g1 ∈ G, g2 ∈ G, then the composite mapping g1 g2 is in G. So ∼ is an equivalence relation, and the set RD splits into equivalence classes that will be called patterns. In Example 13 with the sepia or teal face colorations of the cube, the ten distinct colorations were the ten patterns. 16 Now we have the notation to define weights. De Buijn [2] gives the following definition: Definition 9. Let D and R be finite sets, and G be a permutation group of D. We will assign a weight to each element r ∈ R, call it w(r). The weight W (f ) of a function f ∈ RD is the product Y W (f ) = w[f (d)]. (6) d∈D Note that if f1 ∼ f2 , that is, if they belong to the same pattern, then they have the same weight. Therefore, we may define the weight of the pattern as a common value. Thus if F denotes a pattern, we will denote the weight of F by W (F ). Theorem 6. Pólya’s Fundamental Theorem Let D and R be finite sets and G be a permutation group of D. The elements of R have weights w(r). The functions f ∈ RD and the patterns F have weights W (f ) and W (F ), respectively. Then the pattern inventory is  X X X X 2 3 w(r), [w(r)] , [w(r)] , . . . , , (7) W (F ) = PG F r∈R r∈R r∈R where PG is the cycle index. In particular, if all weights are chosen to be equal to unity, then we obtain the number of patterns = PG (|R|, |R|, |R|, . . . ). (8) Corollary 7. The coefficient of xr in Z(A, 1 + x) is the number of A-equivalence classes of r-sets of X. Proof. In the figure counting series 1 + x, the term 1 = x0 can indicate the absence of an object in X while x = x1 stands for its presence. The corollary now follows immediately from Pólya’s Enumeration Theorem 5. 3.4 Examples Example 12. Suppose we have a necklace that is made from three beads and n colors. Then, by Example 10 the cycle index is 1 PG = (x31 + 2x3 ). 3 Suppose we want to examine the necklaces made by amber, A, and beige, B, beads. Then
1 PG (A + B), (A2 + B 2 ), (A3 + B 3 ) = ((A + B)3 + 2 ∗ (A3 + B 3 )) 3 1 3 = (A + 3A2 B + 3AB 2 + B 3 + 2A3 + 2B 3 ) 3 1 = (3A3 + 3A2 B + 3AB 2 + 3B 3 ) 3 = A3 + A2 B + AB 2 + B 3 . 17 (9) (10) Equation 9 shows us that the configurations fixed by R0 will be the necklace with three amber beads, three necklaces with two amber beads and one beige bead, three necklaces with one amber bead and two beige beads, and the necklace with three beige beads. The configurations fixed by R120 and R240 will be the necklace of three amber beads and the necklace with three beige beads. Equation 10 displays all the possible necklace colorations that are completely distinct. The next example, which should be very familiar by now, will also be given with two colors. For now, we are avoiding an example with three colors simply because the expansion of the generating function would be tedious. If the number of colors is large or if the sums are raised to a large power, computer algebra software can be used to do the work. Example 13. In Example 11 we found the cycle index of distinct cube face colorations to be PG = 1 6 (x + 6x21 x4 + 3x21 x22 + 8x23 + 6x32 ). 24 1 We also found that the number of distinct cubes that could be created from two colors was 10. Suppose a face can be colored with sepia or teal. Substituting xi = (si + ti ) for each i = {1, 2, 3, 4}, we get
1 (s + t)6 + 6(s + t)2 (s4 + t4 ) + 3(s + t)2 (s2 + t2 )2 + 8(s3 + t3 )2 + 6(s2 + t2 )3 24 1 (s6 + 6s5 t + 15s4 t2 + 20s3 t3 + 15s2 t4 + 6st5 + t6 ) + 6(s2 + 2st + t2 )(s4 + t4 ) = 24
+ 3(s2 + 2st + t2 )(s4 + 2s2 t2 + t4 ) + 8(s6 + 2s3 t3 + t6 ) + 6(s4 + 2s2 t2 + t4 )(s2 + t2 ) 1 = (24s6 + 24s5 t + 48s4 t2 + 48s3 t3 + 48s2 t4 + 24st5 + 24t6 ) 24 = s6 + s5 t + 2s4 t2 + 2s3 t3 + 2s2 t4 + st5 + t6 . PG = Now, not only can we count that there are ten distinct colorations by adding the coefficients, we also have a list of what they are. For instance, the term 2s4 t2 indicates that there are two different configurations where there are four sepia sides and two teal sides. The two teal sides could either be touching on an edge (one configuration) or they could be on opposite faces (the second configuration). Example 14. To find the pattern inventory for the edge colorings of a tetrahedron, we first need to consider the symmetries of the tetrahedron as permutations of the edges. Let S be the set of edges of a tetrahedron colored silver or tangerine, and G be the set of permutations of S that can be produced by rotating the tetrahedron. Figure 13 shows the 120 and 240 rotations of the tetrahedron, and Figure 14 shows the 180 degree rotations of the tetrahedron. Both figures assume a bird’s-eye perspective looking down on a translucent tetrahedron. In Figure 14, the tetrahedron is rotated about the opposite edges A and E. Thus C and D switch, and B and F switch. The 12 elements in G and their cycle structures are as follows: 1. The identity leaves all 6 edges fixed and has structure representation x61 . 2. Four 120 degree rotations about a corner and the middle of the opposite face give two cycles of length three. They cyclically permute the edges incident to that corner and also the edges 18 D A F B E C B F A D E D E C B A F C Figure 13: Rotation of tetrahedron by 120 degrees and 240 degrees bounding the opposite face, so the cycle structure representation is x23 . The four colorations this fixes are shown in Figure 15. 3. Four 240 degree rotations essentially do the same thing as the 120 rotations, also giving a structure of x23 . The four colorations this fixes are the same as shown in Figure 15. 4. Three 180 degree rotations about opposite edges leave the two edges fixed. The other four edges are left in cycles of length 2. Thus we have the structure x21 x22 . The sixteen fixed colorations are shown in Figures 16 and 17, and are rotated about sides A and E, as labeled in Figure 14. We then have the function 1 6 (x + 8x23 + 3x21 x22 ). 12 1 If we use n colors, the number of distinct tetrahedron edge colorations will be given by PG = PG = 1 6 (n + 8n2 + 3n4 ). 12 More specifically, if we have the two colors silver and teal, then we will substitute xi = (si + ti ) for 19 D A F B E C C A F B E D Figure 14: Rotation of tetrahedron by 180 degrees about edges A and E Figure 15: Colorations of the tetrahedron fixed by rotations of 120 or 240 degrees 20 Figure 16: First eight colorations of the tetrahedron fixed by rotations of 180 degrees 21 Figure 17: Second eight colorations of the tetrahedron fixed by rotations of 180 degrees 22 each i = {1, 2, 3, 4} to get
1 (s + t)6 + 8(s3 + t3 )2 + 3(s + t)2 (s2 + t2 )2 12 1 = (s6 + 6s5 t + 15s4 t2 + 20s3 t3 + 15s2 t4 + 6st5 + t6 ) + (8s6 + 16s3 t3 12
+ 8t6 ) + (3s6 + 6s5 t + 9s4 t2 + 12s3 t3 + 9s2 t4 + 6st5 + 3t6 ) 1 = (12s6 + 12s5 t + 24s4 t2 + 48s3 t3 + 24s2 t4 + 12st5 + 12t6 ) 12 = s6 + s5 t + 2s4 t2 + 4s3 t3 + 2s2 t4 + st5 + t6 . PG = (11) Thus there are twelve distinct colorations of the edges of a tetrahedron using the colors silver and teal. The list of these colorations is given by the terms of Equation 11. For instance, the term 2s2 t4 indicates that there are two configurations with two edges that are silver and four edges that are teal. 4 Application 1: Chemical Enumeration As stated earlier, one of the main applications of Pólya theory is chemical isomer enumeration. Isomers are compounds which have the same number and types of atoms but different structural formulas because the atoms are bonded to each other differently. We will now examine the derivatives of benzene and cyclopropane. Reade [7] walks through both examples. Example 15. The benzene molecule can be seen in Figure 18. It consists of six carbon atoms in a ring, to each of which a hydrogen atom is attached. Since its structure is “flat,” we can do the same analysis that we would to count distinct six bead necklaces. Derivatives of benzene are formed by replacing the hydrogen atoms by other atoms or groups of atoms. We will first consider dichlorobenzenes, in which chlorines can be substituted for hydrogens. Since the molecule does not change when rotated or flipped, the group G that we will consider is the dihedral group D6 . It contains elements R0 , R60 , R120 , R180 , R240 , R300 , F0 , F30 , F60 , F90 , F120 . and F150 . The rotations should be clear, and the flips are made about the lines in Figure 19 that are i degrees clockwise away from the vertical axis. We then have twelve permutations with the subsequent structure properties: 1. The identity leaves all six atoms fixed, giving six cycles of length one and thus the structure x61 . 2. The two rotations R120 and R240 each give two cycles of length three. In particular, they each fix the configurations that are all chlorine or all hydrogen, or the alternating H, Cl configurations, shown in Figure 20. Thus we have index 2x23 . 3. The three flips F30 , F90 , and F150 and the rotation R180 all have cycle length two. For the the flips, we can imagine the molecule being symmetric across the axes that they are flipped 23 Figure 18: The benzene molecule F0 F30 F60 F90 F120 F150 Figure 19: The axes for the Fi flips 24 H Cl Cl H H Cl Cl H H Cl Cl H Figure 20: Dichlorobenzenes fixed by R120 and R240 across, and thus leaving half the atoms dependent on the first three. For the rotation, we can let three atoms be hydrogen or chlorine, but then the three that are rotated into their places must match. This gives index 3x32 + x32 = 4x32 . 4. Now consider the remaining flips F0 , F60 , and F120 . The two atoms on the axes will be fixed by the flip and therefore have cycle length 1. The other four other atoms are left in two cycles of length two. Thus we have the structure 3x21 x22 . 5. Finally, the two rotations R60 and R300 each have just one cycle length six, and thus produce the structure 2x6 . We then have the function PD6 = 1 6 (x + 2x23 + 4x32 + 3x21 x22 + 2x6 ). 12 1 If we use n different atoms or groups of atoms, the number of distinct isomers will be given by PD6 = 1 6 (n + 2n2 + 4n3 + 3n4 + 2n) 12 by Burnside’s Lemma. But if we want to find how many isomers there are of a certain type, it is useful to substitute the precise weights we are concerned about. More specifically, for dichlorobenzenes, we will substitute xi = (H i + Cli ) for each i = {1, 2, . . . , 6} to get   1 6 3 3 2 2 2 3 2 2 2 2 6 6 PD6 = (H + Cl) + 2(H + Cl ) + 4(H + Cl ) + 3(H + Cl) (H + Cl ) + 2(H + Cl ) 12 = H 6 + H 5 Cl + 3H 4 Cl2 + 3H 3 Cl3 + 3H 2 Cl4 + HCl5 + Cl6 . (12) We used WolframAlpha to simplify the above polynomial. Therefore, not counting the original benzene molecule, we can create twelve distinct dichlorobenzene isomers. We can also know the number of distinct isomers with two hydrogen and four chlorine atoms (3) or of any other certain combination, given by Equation 12. The formula can be generalized to other isomers if we include the other atoms or groups of atoms in the xi substitution. 25 H C H H C H C H H Figure 21: Three dimensional image of cyclopropane structure Now we will count distinct derivatives of cyclopropane. Sometimes an extension of Pólya’s Theorem is necessary when one variable is not sufficient, as is the case in this next example. Example 16. Cyclopropane differs from benzene in that we must consider its structure in three dimensions, as seen in Figure 21. It also differs from benzene in that we must draw from two families of variables. To obtain derivatives of cyclopropane, each hydrogen atom H may be left unchanged or can be replaced by a fluorine atom F or an iodine atom I, and each carbon atom c can be left unchanged or replaced by an atom of radioactive carbon r. We will use variables xi for the first set and yi for the second. Since the molecule can be rotated or flipped, the group we will consider is the dihedral group D3 , consisting of the identity, two rotations and three flips. We then have six types of permutations with the subsequent structure representations: 1. The identity leaves all six hydrogen locations fixed and all three carbon locations fixed, giving the structure x61 y13 . 2. The two rotations of 120 degrees or 240 degrees give one cycle of length three for the carbon locations, and 2 cycles of length three for the hydrogen locations. Their structure is given by 2x23 y3 . 3. There are three flips which occur along each median of the central triangle. There are three cycles of length two for the hydrogen locations as well as one cycle of length one for the fixed carbon location, and one cycle of length two for the two other interchanged carbon locations. Thus we have the structure 3x32 y1 y2 . 26 We then have what is called the compound cycle index 1 PD3 = (x61 y13 + 2x23 y3 + 3x32 y1 y2 ). 6 We will substitute xi = (H i + F i + I i ) and yi = (ci + ri ) for each i = {1, 2, 3} to get   1 6 3 3 3 3 2 3 3 2 2 2 3 2 2 (H + F + I) (c + r) + 2(H + F + I ) (c + r ) + 3(H + F + I ) (c + r)(c + r ) . PD3 = 6 If simplified, this equation would give a complete description of all distinct derivatives of cyclopropane. Finding the number of distinct derivatives is a much easier calculation. Let H = F = I = c = r = 1 and we have   1 6 3 2 3 PD3 = (3) (2) + 2(3) (2) + 3(3) (2)(2) = 1032. 6 5 Application 2: Graphs Pólya’s Theorem can be used to calculate the number of graphs up to isomorphism with a fixed number of vertices. Definition 10. A graph is a collection of points and lines connecting some (possibly empty) subset of them. The points of a graph are most commonly known as vertices, and the lines connecting the vertices are known as edges. To apply Pólya’s Theorem and count the number of different graphs, we need a weight structure. If the edge exists, it will have weight 1, and it if does not, it will have weight 0, giving f (x) = 1 + x as the generating function for the set of colors, as seen in Corollary 3.3. Remember that for any positive integer n, the symmetric group on the set {1, 2, 3, . . . , n} is called the symmetric group on n elements, and is denoted by Sn . Example 17. We will find the number of graphs on three vertices. We will consider the symmetric group S3 (although we could also use D3 again for this example). For the identity permutation (1)(2)(3), there are three cycles of length 1, giving the structure s31 . The three permutations (1)(23),(2)(13), and (3)(12) each have one cycle of length 1 and one of length 2, so the term is given by 3s1 s2 . Finally, the two permutations (123) and (132) both are of length three, giving 2s3 . Then 1 PS3 = (s31 + 3s1 s2 + 2s3 ). 3! Thus we have 1 ((x + 1)3 + 3(x + 1)(x2 + 1) + 2(x3 + 1)) 3! = x3 + x2 + x + 1 PS3 (x + 1, x2 + 1, x3 + 1) = (13) which shows there is one graph with each number of edges. These can be seen in Figure 22. As a demonstration of Corollary 3.3, the coefficient of x3 shows the number of equivalence classes of graphs on three vertices with three edges. (There is only one.) 27 Figure 22: All graphs on three vertices, up to isomorphism The logical next consideration is a generalization of this to p vertices. Harary and Palmer [4] give us the following and unsightly formula. Theorem 8. The polynomial gp (x) which enumerates graphs of order p by number of lines is given by gp (x) = Z(Sp(2) , 1 + x), (14) where Z(Sp(2) ) = Y kj Y 1 X p! k(jk ) Y (r,t)jr jt 2k+1 Q j s[r,t] . s2k+1 (sk sk−1 )j2k sk 2 2k p! k k jk ! r Edges 2 3 4 5 6 7 8 9 10 11 12 13 ------------------------------------------------------------------------------------------------------0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 1 2 2 2 2 2 2 2 2 2 2 3 0 1 3 4 5 5 5 5 5 5 5 5 4 0 0 2 6 9 10 11 11 11 11 11 11 5 0 0 1 6 15 21 24 25 26 26 26 26 6 0 0 1 6 21 41 56 63 66 67 68 68 7 0 0 0 4 24 65 115 148 165 172 175 176 8 0 0 0 2 24 97 221 345 428 467 485 492 9 0 0 0 1 21 131 402 771 1,103 1,305 1,405 1,446 10 0 0 0 1 15 148 663 1,637 2,769 3,664 4,191 4,435 11 0 0 0 0 9 148 980 3,252 6,759 10,250 12,763 14,140 12 0 0 0 0 5 131 1,312 5,995 15,772 28,259 39,243 46,415 13 0 0 0 0 2 97 1,557 10,120 34,663 75,415 119,890 154,658 14 0 0 0 0 1 65 1,646 15,615 71,318 192,788 359,307 517,121 15 0 0 0 0 1 41 1,557 21,933 136,433 467,807 1,043,774 1,711,908 16 0 0 0 0 0 21 1,312 27,987 241,577 1,069,890 2,911,086 5,546,619 17 0 0 0 0 0 10 980 32,403 395,166 2,295,898 7,739,601 17,422,984 18 0 0 0 0 0 5 663 34,040 596,191 4,609,179 19,515,361 52,664,857 19 0 0 0 0 0 2 402 32,403 828,728 8,640,134 46,505,609 152,339,952 20 0 0 0 0 0 1 221 27,987 1,061,159 15,108,047 104,504,341 420,048,805 21 0 0 0 0 0 1 115 21,933 1,251,389 24,630,887 221,147,351 1,101,083,128 22 0 0 0 0 0 0 56 15,615 1,358,852 37,433,760 440,393,606 2,739,261,020 23 0 0 0 0 0 0 24 10,120 1,358,852 53,037,356 825,075,506 6,461,056,816 24 0 0 0 0 0 0 11 5,995 1,251,389 70,065,437 1,454,265,734 14,441,470,390 25 0 0 0 0 0 0 5 3,252 1,061,159 86,318,670 2,411,961,516 30,583,652,956 26 0 0 0 0 0 0 2 1,637 828,728 99,187,806 3,765,262,970 61,372,294,334 27 0 0 0 0 0 0 1 771 596,191 106,321,628 5,534,255,092 116,724,411,757 28 0 0 0 0 0 0 1 345 395,166 106,321,628 7,661,345,277 210,474,287,115 29 0 0 0 0 0 0 0 148 241,577 99,187,806 9,992,340,187 359,954,668,522 30 0 0 0 0 0 0 0 63 136,433 86,318,670 12,281,841,209 584,089,835,857 31 0 0 0 0 0 0 0 25 71,318 70,065,437 14,229,503,560 899,632,282,299 32 0 0 0 0 0 0 0 11 34,663 53,037,356 15,542,350,436 1,315,729,343,451 33 0 0 0 0 0 0 0 5 15,772 37,433,760 16,006,173,014 1,827,823,498,798 34 0 0 0 0 0 0 0 2 6,759 24,630,887 15,542,350,436 2,412,694,353,115 35 0 0 0 0 0 0 0 1 2,769 15,108,047 14,229,503,560 3,026,821,673,656 36 0 0 0 0 0 0 0 1 1,103 8,640,134 12,281,841,209 3,609,810,088,490 37 0 0 0 0 0 0 0 0 428 4,609,179 9,992,340,187 4,093,273,437,761 38 0 0 0 0 0 0 0 0 165 2,295,898 7,661,345,277 4,413,678,080,790 39 0 0 0 0 0 0 0 0 66 1,069,890 5,534,255,092 4,525,920,859,198 40 0 0 0 0 0 0 0 0 26 467,807 3,765,262,970 4,413,678,080,790 41 0 0 0 0 0 0 0 0 11 192,788 2,411,961,516 4,093,273,437,761 42 0 0 0 0 0 0 0 0 5 75,415 1,454,265,734 3,609,810,088,490 43 0 0 0 0 0 0 0 0 2 28,259 825,075,506 3,026,821,673,656 44 0 0 0 0 0 0 0 0 1 10,250 440,393,606 2,412,694,353,115 45 0 0 0 0 0 0 0 0 1 3,664 221,147,351 1,827,823,498,798 46 0 0 0 0 0 0 0 0 0 1,305 104,504,341 1,315,729,343,451 47 0 0 0 0 0 0 0 0 0 467 46,505,609 899,632,282,299 48 0 0 0 0 0 0 0 0 0 172 19,515,361 584,089,835,857 49 0 0 0 0 0 0 0 0 0 67 7,739,601 359,954,668,522 50 0 0 0 0 0 0 0 0 0 26 2,911,086 210,474,287,115 51 0 0 0 0 0 0 0 0 0 11 1,043,774 116,724,411,757 52 0 0 0 0 0 0 0 0 0 5 359,307 61,372,294,334 53 0 0 0 0 0 0 0 0 0 2 119,890 30,583,652,956 54 0 0 0 0 0 0 0 0 0 1 39,243 14,441,470,390 55 0 0 0 0 0 0 0 0 0 1 12,763 6,461,056,816 56 0 0 0 0 0 0 0 0 0 0 4,191 2,739,261,020 57 0 0 0 0 0 0 0 0 0 0 1,405 1,101,083,128 58 0 0 0 0 0 0 0 0 0 0 485 420,048,805 59 0 0 0 0 0 0 0 0 0 0 175 152,339,952 60 0 0 0 0 0 0 0 0 0 0 68 52,664,857 61 0 0 0 0 0 0 0 0 0 0 26 17,422,984 62 0 0 0 0 0 0 0 0 0 0 11 5,546,619 63 0 0 0 0 0 0 0 0 0 0 5 1,711,908 64 0 0 0 0 0 0 0 0 0 0 2 517,121 65 0 0 0 0 0 0 0 0 0 0 1 154,658 66 0 0 0 0 0 0 0 0 0 0 1 46,415 67 0 0 0 0 0 0 0 0 0 0 0 14,140 68 0 0 0 0 0 0 0 0 0 0 0 4,435 69 0 0 0 0 0 0 0 0 0 0 0 1,446 70 0 0 0 0 0 0 0 0 0 0 0 492 71 0 0 0 0 0 0 0 0 0 0 0 176 72 0 0 0 0 0 0 0 0 0 0 0 68 73 0 0 0 0 0 0 0 0 0 0 0 26 74 0 0 0 0 0 0 0 0 0 0 0 11 75 0 0 0 0 0 0 0 0 0 0 0 5 76 0 0 0 0 0 0 0 0 0 0 0 2 77 0 0 0 0 0 0 0 0 0 0 0 1 78 0 0 0 0 0 0 0 0 0 0 0 1 ------------------------------------------------------------------------------------------------------Totals 2 4 11 34 156 1,044 12,346 274,668 12,005,168 1,018,997,864 165,091,172,592 50,502,031,367,952 37 Figure 33: Counting graphs Definition 11. The n-scale is taken to be equal (well) tempered and consists of the integers from 0 to n − 1. We equate octave notes, so our scale is mathematically Zn with addition. For example, Western music has n = 12, Debussy used a whole tone scale with n = 6, and Ives used a quarter tone scale with n = 24. 6.1 Chords Definition 12. A k-chord in the n-scale is an equivalence class of subsets of k elements each of Zn . We can use the dihedral group Dn to induce the equivalence relation between chords. A group element would have the form T i I : a → i − a(mod n). For example, the C major chord is equivalent to the C minor chord: {C, E, G} = {0, 4, 7} ∼ {0, 3, 7} = {C, E[, G}, under the element T 7 I. This is actually no different from the two-color necklace problems we have worked with previously. We now have a circular “necklace” of notes to choose from, and we choose the notes in the chord by coloring them one color, and coloring the rest another color. Chords in twelve-tone music To examine twelve-tone music with dihedral symmetry, we will need to obtain the cycle index for D12 . As a sidenote, we could also go through a similar analysis using the cyclic group C12 , but we will use D12 since we are more familiar with it thus far. There are 24 elements in D12 and their cycle structures are as follows: 1. There are two types of flips. Because we now have an even number of vertices, we can flip over lines through pairs of vertices or lines through pairs of edges. (a) We’ll first deal with the flips over opposite pairs of vertices. As seen in Figure 34, this will fix the two green vertices and leave the rest of the blue “beads” on cycles of length two. Note that the matching shades of blue correspond with the beads that are in the same cycle. There are six such flips, and their structure is x21 x52 . (b) The second type flips over the centers of opposite edges . As seen in Figure 34, there will be six cycles of length two. There are also six of these, and their structure is x62 . 2. There are twelve rotations which break into six different types. We will call them R0 , R30 , R60 , . . . , R330 . (a) The identity, R0 leaves everything fixed and thus has the cycle index x12 1 . (b) The rotations R30 , R150 , R210 , and R330 all have structures x112 . With these rotations, each bead would visit every spot before returning to its orginial place after the twelve rotations. 38 Figure 34: Examples of the two types of flip permutations in D12 Figure 35: Rotations R60 and R300 both have structures x26 39 Figure 36: Rotations R90 and R270 have structures x34 Figure 37: Rotations R120 and R240 have structures x43 (c) The rotations R60 and R300 both have structures x26 . As seen in Figure 35, these permutations will rotate the blue beads in a cycle of length six, and rotate the green beads in a cycle of length six. (d) The rotations R90 and R270 have structures x34 , as these rotations create three cycles of length four. These can be demonstrated by the three colors in Figure 36. (e) The rotations R120 and R240 have structures x43 , creating four cycles of length three. This is shown in Figure 37. (f) Finally, the rotation R180 has six cycles of length 2, not unlike the second type of flip, giving the structure x62 . These cycles can be seen in Figure 38 with the matching pairs of shades of blue. Thus we have ZD12 = 1 1 2 3 4 6 (6x21 x52 + 6x62 + x12 1 + 4x12 + 2x6 + 2x4 + 2x3 + x2 ). 24 (25) We will use the substitution xi = (xi + 1), as the term 1 = x0 indicates the absence of an object while x = x1 represents its presence. So xi indicates that i distinct objects are present. 40 Figure 38: The rotation R180 has structure x62 Substituting xi = (xi + 1) for each i = {1, 2, . . . , 12} and using WolframAlpha to simplify the polynomial we get ZD12 = 1 (6(x + 1)2 (x2 + 1)5 + 6(x2 + 1)6 + (x + 1)12 + 4(x12 + 1) + 2(x6 + 1)2 24 + (x4 + 1)3 + 2(x3 + 1)4 + (x2 + 1)6 ) (26) = x12 + x11 + 6x10 + 12x9 + 29x8 + 38x7 + 50x6 + 38x5 + 29x4 + 12x3 + 6x2 + x + 1. (27) The number of k-chords is the coefficient of xk in Equation 27. Thus, in twelve-tone music, there are 12 types of tetrachords, 29 types of pentachords, 50 types of hexachords, and so on. These can be summed for a total of 224 distinct chords. We could go through the above analysis for each n-scale to find the cycle index of Dn or Cn . However, it would be more convenient to use the general formula for Dn or Cn if we want to find indices for large values of n or a large number of n’s. These formulas can be found in the discussion of cycle indices. 6.2 Tones The Virginia Tech Multimedia Music Dictionary defines a Tone Row as a specific arrangement of the twelve tones of the twelve-tone scale as a basis for a twelve-tone composition. We already know there are 12! such arrangements, but ’symmetry’ will make some of these equivalent. We will shortly define what these symmetries are. Rumery [9] brings us the following example with figures. Example 20. Consider a row extracted from Schoenberg’s first twelve-tone composition, as in Figure 6.2. The pitches are numbered according to their position in the chromatic scale beginning on E. 41 Figure 39: Row from Suite, Op. 25, Schoenberg Figure 40: Row in original and retrograde form E is numbered 0 because it is the first note of the row. The pitch class numbers of the remaining notes indicate their distance above E in half-steps. We can extend this to n rows, which Reiner [8] does in the following definition: Definition 13. An n-tone row is an equivalence class of permutations in Sn . Our equivalence classes are induced by the group generated by transposition, T : Sn → Sn : (a1 , . . . , an ) → (a1 + 1, . . . , an + 1)(mod n); inversion, I : (a1 , . . . , an ) → (a1 , 2a1 − a2 , . . . , 2a1 − an )(mod n); and retrogradation, R : (a1 , . . . , an ) → (an , . . . , a1 ). According to Reiner [8], music theorists regard transposition as such a basic transformation that, instead of working with all the permutations, they work with equivalence classes of permutations under transposition, those beginning with 0 be regarded as class representatives. So our set is the set of (n − 1)! permutations of {1, . . . , n − 1}, and our group is generated by R and I. Since RI = IR, we are working with what is known as the Klein four-group, which is also known as Z2 × Z2 . To better grasp the group elements, retrograde form is created by writing the notes in the original version in reverse order, as in Figure 40. The inversion form has all the intervals written upside down, with the interval directions changed, as in the left side of Figure 41. Lastly, the retrograde inversion from is just the inversion form, but with the notes in reverse order, as in the right side of Figure 41. For further clarification, Pickett [6] provides the matrix in Figure 6.2. Tone rows in their original forms are listed from left to right. The retrograde version can be read from right to left, and the inverted version can be read by starting at the same note but then reading down the column. Finally, the row’s retrograde inverted version can be found by reading the column from bottom to top. 42 Figure 41: Row in inversion and retrograde inversion form 43 To count the number of distinct tone rows, we will count the number of equivalence classes. By Burnside’s Lemma, the number of equivalence classes for a group G acting on D is 1 X (# of elements of D f ixed by g). |G| g∈G Closely following the analysis done by Reiner [8], we find the number of elements fixed by each permutation e, I, R, and IR. To avoid the trivial cases, assume n ≥ 3. 1. Since our set has (n − 1)! elements, the identity e fixes (n − 1)! elements. 2. Consider I. I(0, a2 , . . . , an ) = (0, −a2 , . . . , −an ) ∼ (0, a2 , . . . , an ) implies ai ≡ −ai (mod n) for i = 2, . . . , n. The first element 0 is fixed. There is at most one nonzero solution to x ≡ −x (mod n), which is not sufficient to fill out the permutation. So there are are 0 elements fixed by I. 3. Consider R. R(a1 , . . . , an ) = (an , . . . , a1 ) ∼ (a1 , . . . , an ) implies that t exists such that a1 ≡ an +t, a2 ≡ an−1 +t, . . . (mod n). If n is odd, the middle element is fixed and no transposition is allowed: t = 0. But then we have the contradiction that an = a1 . So R fixes 0 elements if n is odd. However, if n is even, the first and last congruences imply that 2t = 0; thus t = 0 or t = n/2. We already saw that t = 0 fails, but the other gives fixed permutations. Since a1 = 0, then an = n/2. For a2 , we can choose any of n − 2 elements, and this determines an−1 . For a3 , we have n − 4 choices, and so on. Hence if n is even, the number of elements fixed by R is (n − 2)(n − 4) · · · (2). 4. Consider IR. IR(a1 , . . . , an ) = (−an , . . . , −a1 ) ∼ (a1 , . . . , an ) implies that t exists such that a1 + an ≡ t, a2 + an−1 ≡ t, . . . (mod n). The last congruence for n odd is 2a(n+1)/2 ≡ t (mod n). It is not essential that we fix the first element as 0, as we could fix a(n+1)/2 as 0 and find the same count. Hence we may assume t = 0, a(n+1)/2 = 0, giving n − 1 choices for a1 , which determines an , n − 3 choices for a2 , etc. Thus if n is odd, we have (n − 1)(n − 3) · · · (2) fixed elements. If n is even, we fix a1 so an 6= t 6= 0. We see that t must be odd in order to complete the permutation. If t = 2k, there is no mate for k in the permutation. So there are n/2 choices for t = an . For a2 , there are n − 2 choices, which determines an−1 , and so on. Thus there are (n/2)(n − 2)(n − 4) · · · (2) elements fixed by IR. Finally, we conclude that the number of n-tone rows is 1 [(n − 1)! + (n − 1)(n − 3) · · · (2)] 4 1 n [(n − 1)! + (n − 2)(n − 4) · · · (2)(1 + )] 4 2 Thus in twelve-tone music, there are 9985920 tone rows. 44 if n is odd; (28) if n is even. (29) 7 Conclusion We have already seen that Pólya’s Counting Theory has numerous and remarkable applications. The two most extensively researched are graphical and chemical isomer enumeration, but there are plenty of other uses as well. Without exploring the details too extensively, Reade [7] mentions the other following applications: 1. Investigating crystal structure and studying nuclear magnetic resonance and NMR spectroscopy, as well as other applications in theoretical chemistry. 2. Counting Latin squares, which are n × n arrays filled with n different symbols, each occurring exactly once in each row and exactly once in each column. 3. Enumerating the number of Boolean functions under various conditions. 4. Counting the number of essentially different propositions of n statements, and showing that the problem is equivalent to coloring the vertices of a hypercube. 5. Counting finite automata and certain binary matrices. 6. Counting graphs in statistical mechanics. 7. Studying kinetic structures. And there certainly are more which have not been mentioned. Though we will not explore them here, we can easily conclude that Pólya’s Counting Theory is one of the most useful and satisfying tools to exist in combinatorics. References [1] B. Butler, Enumeration of Unlabeled Graphs, http://www.durangobill.com/UnlblGraphs.html. [2] N. G. De Buijn, Pólya’s Theory of Counting, Applied Combinatorial Mathematics, John Wiley and Sons, Inc., New York, 1964, 144–184 . [3] J. A. Gallian, Contemporary Abstract Algebra, 5th Edition, Houghton Mifflin Company, 2002. 45 [4] F. Harary and E. Palmer, Graphical Enumeration, Academic Press, New York, 1973. [5] C. Pinter, A Book of Abstract Algebra, 2nd Edition, Dover Publications, 2010. [6] S. Pickett, Plain Talk About Harmony, Volume 2, CoMuse Publishing, 2008. [7] G. Pólya and R. C. Reade, Combinatorial Enumberation of Groups, Graphs, and Chemical Compounds, Springer-Verlag, New York, 1987. [8] D. L. Reiner, “Enumeration in Music Theory,” The American Mathematical Monthly, Vol. 92, No. 1 (Jan., 1985), p. 51-54. [9] K. R. Rumery, “Twelve-Tone Composition, Part One,” http://jan.ucc.nau.edu/∼krr2 /12tone/12tone1.html [10] A. Tucker, Applied Combinatorics, 4th Edition, John Wiley and Sons, 2002. [11] T. L. Vis, Enumeration of Unlabeled Graphs, UC Denver, 2007. [12] E. W. Weisstein, “Totient Function,” MathWorld http://mathworld.wolfram.com/TotientFunction.html 46 – A Wolfram Web Resource,