/compile/output.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 9, No. 1, 2016, 84-113 ISSN 1307-5543 – www.ejpam.com Counting Symmetries with Burnside’s Lemma and Pólya’s Theorem Md. Taufiq Nasseef Department of Mathematics, School of Mathematics,Statistics and Actuarial Science , University of Kent, Kent, United Kingdom Abstract. Counting concerns a large part of combinational analysis. Burnside’s lemma, sometimes also called Burnside’s counting theorem, the Cauchy-Frobenius lemma or the orbit-counting theorem [5], is often useful in taking account of symmetry when counting mathematical objects. The Pólya’s theorem is also known as the Redfield-Pólya Theorem which both follows and ultimately generalizes Burnside’s lemma on the number of orbits of a group action on a set. Pólya’s Theory is a spectacular tool that allows us to count the number of distinct items given a certain number of colors or other characteris- tics. Sometimes it is interesting to know more information about the characteristics of these distinct objects. Pólya’s Theory is a unique and useful theory which acts as a picture function by producing a polynomial that demonstrates what the different configurations are, and how many of each exist.The dynamics of counting symmetries are the most interesting part. This subject has been a fascination for mathematicians and scientist for ages. Here 16 Bead Necklace, patterns of n tetrahedron with 2 colors, patterns of n cubes with 3 and 4 colorings and so on have been solved. 2010 Mathematics Subject Classifications: 14L,14P,14Q Key Words and Phrases: Burnside’s Lemma, Pólya’s Theorem, Counting Symmetries,Group 1. Introduction and Preliminaries 1.1. Group Action Let G be a group and A is a set which is nonempty. Suppose that G is a permutation group acting on a set A, and consider the set BA of all functions f : A→ B. Then G acts naturally on BA as follows: if g ∈ G and f ∈ BA then define the function f g by [8] f g(a) = f (ag−1). Email address: taufiq278@gmail.com http://www.ejpam.com 84 c© 2016 EJPAM All rights reserved. T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 85 1.2. The Cycle Index of a Permutation Group Let us consider G is a permutation group acting on a set A which contains p number of elements. Suppose X ∈ G which can be written as the product of t1 disjoint cycles of length 1, t2 disjoint cycles of length 2, . . . , tp disjoint cycles of length p then X is called of cycle type (t1, t2, . . . , tp). Example 1. Let G = {X1, X2, X3} be a cyclic group of order 3 and the set A= {1,2,3}. Then we have X1 = � 1 2 3 1 2 3 � = (1)(2)(3) X2 = � 1 2 3 2 3 1 � = (123) X3 = � 1 2 3 3 1 2 � = (132) Here X1 has 3 cycle type of length 1. It is of type (3,0,0), known as identity mapping. X2 and X3 each has 1 cycle type of length 3 and are of type (0,0,1) [6]. Note that if we split A into k1 cycles of length 1, k2 cycles of length 2, . . . , kp cycles of length p then we have k1 + 2k2 + 3k3 + . . .+ pkp = p, the sum of lengths of the cycles are the total number of elements in A [2]. Definition 1. Let G be a group and its elements are the permutations of the set A. Consider the group operation be multiplication and let us define a polynomial in p variables t1, t2, t3, . . . , tp where the coefficients are non negative. Then for every g ∈ G we can form the product t k1 1 , t k2 2 , t k3 3 , . . . , t kp p . So the cycle index G is the polynomial defined by Z(G, t1, t2, t3, . . . , tp) = 1 |G| { ∑ g∈G t k1 1 t k2 2 t k3 3 . . . t kp p } Example 2. Consider G = S3 = {X1, X2, X3, X4, X5, X6} where X1 = � 1 2 3 1 2 3 � = (1)(2)(3) X2 = � 1 2 3 2 3 1 � = (123) X3 = � 1 2 3 3 1 2 � = (132) X4 = � 1 2 3 3 2 1 � = (2)(13) X5 = � 1 2 3 1 3 2 � = (1)(23) T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 86 X6 = � 1 2 3 2 1 3 � = (12)(3) We observe that the permutations of each X4, X5 and X6 has one cycle of length 2 and one cycle of length 1 and are of type (1,1,0). X1, X2 and X3 are known to us by the Example 1. The order of this group is 3!= 6. Hence by the definition the cycle index of S3 is [6] Z(S3, t1, t2, t3) = 1 6 {t3 1 + 3t1 t2 + 2t3}. Theorem 1. The cycle index of the symmetric group Z(Sp) can be defined by Z(Sp) = 1 p! { ∑ t(t k1 1 t k2 2 t k3 3 . . . t kp p )} where t = p! (1k1!)(2k2!)(3k3!) . . . (pkp !) and the summation is over p-tuple (k1, k2, k3, . . . , kp) which are nonnegative integers ki satisfying 1k1 + 2k2 + 3k3 + . . .+ pkp = p [6]. There are some formulas for cycle indices. In this study we will use indices for symmetric groups, cyclic groups, and dihedral groups. Definition 2. The totient function φ(n), also called Euler’s totient function or the Euler-phi func- tion, 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 four numbers relatively prime to 12 that are less than 12 (1,5,7, and 11), so φ(12) = 4. For cyclic groups and dihedral groups we have the following formulas: Z(Cn) = 1 n ∑ k/n φ(k)t n/k k , (1) and Z(Dn) = 1 2 Z(Cn) + ¨ 1 2 t1 t (n−1)/2 2 if n odd, 1 4(t n/2 2 + t2 1 t (n−2)/2 2 ) if n even. Z(Dn) is divided 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 [4]. ∗K. R. Rumery, Twelve-Tone Composition, Part One, http://jan.ucc.nau.edu/~krr2/12tone/12tone1. html T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 87 Example 3. Let us use this formula to compute the cycle index of C4, ZC4 = 1 4 ∑ l/4 φ(l)t 4/l l = 1 4 (φ(1)t 4/1 1 +φ(2)t 4/2 2 +φ(4)t 4/4 4 ) = 1 4 (t4 1 + t2 2 + 2t4) Example 4. Here we will illustrate the formula by computing the cycle index of D4, ZD4 = 1 2 ZC4 + 1 4 (t 4 2 2 + t2 1 t 4−2 2 2 ) = 1 2 ( 1 4 (t4 1 + t2 2 + 2t4)) + 1 4 (t 4 2 2 + t2 1 t 4−2 2 2 ) = 1 8 (t4 1 + t2 2 + 2t4) + 1 4 (t2 2 + t2 1 t2) = 1 8 (t4 1 + 2t2 1 t2 + 3t2 2 + 2t4) Now we have already got the cycle index of the symmetric groups from Theorem 1. The following example will find the coefficient on n-th term. Example 5. Let A be a set of n elements and let G be the group of all permutations of A. That is G is a symmetric group of degree n. Its cycle index turns out to be equal to the coefficient of xn in the development of ex p(x t1 + x2 t2 2 + x3 t3 3 + . . .) as a power series of in x. This expression can be written as ∞ ∑ g1=0 x g1 t g1 1 g1! ∞ ∑ g1=0 x2g2 t g2 2 g2!2g2 . . . The coefficient of xn is obtained by summing the expression t g1 1 t g2 2 . . . (g1!g2!2g2 . . .)−1 over all possible g1, g2, . . . satisfying g1 + 2g2 + . . .= n [2]. Definition 3. The set of elements g of a group G such that g−1H g = H, is said to be the nor- malizer NG with respect to a subset of group elements of H. If H is a subgroup of G, NG(H) is also a subgroup containing H. T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 88 1.3. Equivalence Relations Let A be a set and ∼ be a binary relation of A. Then ∼ is an equivalence relation if and only if for all p,q, r ∈ A the following conditions are satisfied: Reflexivity p ∼ p Symmetry If p ∼ q then q ∼ p Transitivity If p ∼ q and q ∼ r then p ∼ r The equivalence class of p under ∼ is the set {p ∈ A|p ∼ q} [1]. These equivalence classes are called patterns. 1.4. Weights and Inventory Definition 4. Given a set of colors C we want to associate a weight wc for all c ∈ C. Then we will define the weight of a coloring a ∈ A to be the product of the weights of the colored elements [1]. w(a) = ∏ i∈N wa(i) This is also called the inventory of A. Example 6. Consider 4 bead necklace to illustrate with C={Red(r), Yellow(y)}. Let a = r r y y where a(1) = Red, a(2) = Red, a(3) = Yel low and a(4) = Yel low Let the colors Red and Yellow have weights R and Y respectively. Then the coloring of a as follows w(a) = ∏ i∈N wa(i) =wa(1)wa(2)wa(3)wa(4) =RRY Y =R2Y 2 Definition 5. Let G be a permutation group on a set A. Suppose that ∼ defines an equivalence relation on A. Then the equivalence class containing the element a, denoted by Or b(a) is called the G-orbit of a. It is defined as [6] Or b(a) = {π(a) : π ∈ G} Example 7. Consider 4 bead necklace where A = {1,2,3,4}, B = {Red(R), Yel low(Y )}, C be the group of coloring with f : A→ B and G = {e, (12), (34), (12)(34)} be the permutation group [1]. Then Or b(RRRR) ={RRRR}Or b(RRRY ) = Or b(RRY R) = {RRRY,RRY R} T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 89 Or b(RRY Y ) ={RRY Y }Or b(RY RR) = Or b(Y RRR) = {RY RR, Y RRR} Or b(Y Y Y Y ) ={Y Y Y Y }Or b(Y Y Y R) = Or b(Y Y RY ) = {Y Y Y R, Y Y RY } Or b(Y Y RR) ={Y Y RR}Or b(Y RY Y ) = Or b(RY Y Y ) = {Y RY Y,RY Y Y } Or b(RY RY ) =Or b(Y RY R) = Or b(RY Y R) = Or b(Y RRY ) = {RY RY, Y RY R,RY Y R, Y RRY } The problem of determining the equivalent objects in A is to count all G-orbits. How- ever this method looks impractical and even more boring in complex situations. Fortunately, Burnside’s Lemma gives an analytical formula for such counting of G-orbits. It is a powerful technique and particularly efficient when the order of the group is small. It is also considered one of the essential parts in development of the Pólya Theory. Definition 6. Let G be a permutation group on a set A. An element a in A is said to be invariant under a permutation π ∈ G if and only if π(a) = a. To each a ∈ A, the stabilizer of a, denoted by Stab(a) is defined to be the set Stab(a) = {π ∈ G : π(a) = a} and ∀a ∈ G. Let η(π) denotes the number of elements of A that are invariant under π that is [6] η(π) = {a ∈ A : π(a) = a} Example 8. Following the Example 7 the stabilizer sets for each coloring in C are given below Stab(RRRR) =Stab(Y Y Y Y ) = Stab(RRY Y ) = Stab(Y Y RR) = {e, (12), (34), (12)(34)} Stab(RRRY ) =Stab(Y Y Y R) = Stab(RRRY ) = Stab(Y Y Y R) = {e, (12)} Stab(RY RR) =Stab(Y RY Y ) = Stab(RY Y Y ) = Stab(Y RRR) = {e, (34)} Stab(Y RRY ) =Stab(RY Y R) = Stab(RY RY ) = Stab(Y RY R) = {e} 2. Burnside’s Lemma and Pólya’s Theorem 2.1. Orbit-Stabilizer Formula Let G be a group, acting on a set A, then For all a ∈ A, |G|= |Stab(a)||Or b(a)| [6]. Example 9. By following the Example 7 and 8 we have Stab(Y Y RR) ={e, (12), (34), (12)(34)}Stab(Y RRR) = {e, (34)} Or b(Y Y RR) ={Y Y RR}Or b(Y RRR) = {RY RR, Y RRR} Therefore |Stab(Y Y RR)|= 4 |Stab(Y RRR)|= 2 |Or b(Y Y RR)|= 1 |Or b(Y RRR)|= 2 ⇒ |Stab(Y Y RR)||Or b(Y Y RR)|= 4.1= 4 ⇒ |Stab(Y RRR)||Or b(Y RRR)|= 2.2= 4 T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 90 2.2. Burnside’s Lemma Lemma 1. Let G be a finite group that acts on a set A. For each g ∈ G, let Ag denote the set of elements in A that are fixed by g. Burnside’s lemma asserts the following formula for the number of orbits, denoted |A/G|: |A/G|= 1 |G| ∑ g∈G |Ag | Thus the number of orbits (a natural number or +∞) is equal to the average number of points fixed by an element of G [3]. Proof. The proof uses orbit-stabilizer theorem and the fact that A is the disjoint union of the orbits: ∑ g∈G |Ag |=|{(g, a) ∈ G × A|g · a = a}|= ∑ a∈A |Stab(a)|= ∑ a∈A |G| |Or b(a)| =|G| ∑ a∈A 1 |Or b(a)| = |G| ∑ P∈A/G ∑ a∈P 1 |P| = |G| ∑ P∈A/G 1= |G| · |A/G| Therefore [6] 1 |G| ∑ g∈G |Ag |= |A/G| This proves the lemma. Example 10. Continuing With the Example 7 and 8, We have A(e) = C A(12) ={RRRR,RRY R,RRRY,RRY Y, Y Y RR, Y Y Y R, Y Y RY, Y Y Y Y } A(34) ={RRRR, Y RRR,RY RR,RRY Y, Y Y RR,RY Y Y, Y RY Y, Y Y Y Y } A((12)(34)) ={RRRR,RRY Y, Y Y RR, Y Y Y Y } By applying Burnside’s Lemma, we have 1 |G| ∑ g∈G |Ag |= 1 4 (16+ 8+ 8+ 4) = 9 Example 11. Let G be the group of rotations of a cube induced on the set of 6 faces (Fig. 1). The rotations of the cube which leaves it invariant are (i) 6 rotations of 90 degree(clockwise or anti-clockwise) about the axes joining the centers of the opposite faces; (ii) 3 rotations of 180 degree each of the above axes; (iii) 8 rotations of 120 degree(clockwise or anti-clockwise) about the axes joining the opposite vertices; T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 91 (iv) 6 rotations of 180 degree about the axes joining the midpoints of the opposite edges and (v) the identity. To determine the cyclic index of its action on the set of faces it is observed that (i) has rotations of order 4 and cycle type t2 1 t4; (ii) has rotations of order 2 and cycle type t2 1 t2 2; (iii) has rotations of order 3 and cycle type t2 3 (iv) has rotations of order 2 and cycle type t3 2 (v) has rotations of order 1 and cycle type t6 1 Therefore the cycle index of G is Z(G, t1, t2, . . . , t6) = 1 24 (6t2 1 t4 + 3t2 1 t2 2 + 8t2 3 + 6t3 2 + t6 1). Figure 1: Faces of the cube (a) Axis (b) Corner (c) Midpoint Figure 2: Types of Rotations of the Cube Consider G = Cn be cyclic group of order n with regarded as the group of permutations of the vertices of a regular n-gon. However it is the subgroup of Sn generated by an n-cycle(1,2,. . . ,n). For a generator g of Sn, the element g i has the same cyclic structure as that of gcd{i, n} and cycle of length d = n gcd(i,n) and therefore has of order d. The number of elements of order d is equal to T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 92 the number of integers 1 ≤ p ≤ d with gcd(p, d) = 1, which is already given by Euler’s function φ from the elementary theory (Definition 4). Thus from (Eq1) we obtain Z(G, t1, t2, . . . , tn) = 1 n ∑ d/n φ(d)t n/d d where φ(pn) = (p− 1)pn−1 for prime powers and φ(m) = Πk i=1 φ(p ni i ) for m= Πk i=1 p ni i [3]. Example 12. Again let G be the group of rotations of a cube induced on the set of 8 vertices. The rotations of the cube which leaves it invariant are the same as Example 11. It is now necessary to see what the rotations do with the vertices. To determine the cycle index of its action on the set of faces it is observed that (i) has rotations of order 4 and cycle type t2 4; (ii) has rotations of order 2 and cycle type t4 2 ; (iii) has rotations of order 4 and cycle type t2 1 t2 3 (iv) has rotations of order 2 and cycle type t4 2 (v) has rotations of order 1 and cycle type t8 1 Therefore the cycle index of G is [2] Z(G, t1, t2, . . . , t8) = 1 24 (6t2 4 + 9t4 2 + 8t2 1 t2 3 + 6t3 2 + t8 1). 2.3. Pólya’s Substitution Let σ(c1, c2, . . . , ck) be the polynomial obtained from the cycle index Z(G, t1, t2, . . . , tn) by substituting t1 7−→c1 + c2 + . . .+ ck, t2 7−→c2 1 + c2 2 + . . .+ c2 k , . . . tn 7−→cn 1 + cn 2 + . . .+ cn k , Then the number of non-equivalent k colorings of A pattern [p1, p2, . . . , pk] is equal to the co- efficient of the term c p1 1 c p2 2 . . . c pk k in σ(c1, c2, . . . , ck) [3]. Then we find the generating function ZG k ∑ i=1 ci , k ∑ i=1 c2 i , . . . , k ∑ i=1 cn i ! , where n stands for the largest cycle length. This is known as Pólya’s Enumeration Formula. T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 93 Problem 1 (Edge Coloring of a Tetrahedron). A tetrahedron has 6 edges. How many in- equivalent ways are there to color it with (a) 2 colors? (b) 3 black and 3 yellow edges? Solution: First we need to find out the symmetries of the tetrahedron with permutations of the edges. Let us consider the set A of the edges of a tetrahedron and G be the set of permutations of A which will be produced by rotating the tetrahedron. Their cyclic structures are given as follows (i) The identity leaves all 6 edges fixed with structure t6 1. (ii) There are four 120◦ rotations about a corner and the middle of the opposite face (Fig. 3). They are two cycles of length three. They cyclically permute the edges incident to that corner and also the edges bounding the opposite face, so the cycle structure representation is t2 3. (iii) There are four 240◦ rotations as like the 120◦ rotations (Fig. 3). So the cycle structure is also same. (iv) There are three 180◦ rotations about opposite edges leave the two edges fixed. The other four edges are left in cycles of length 2. Thus we have the cycle structure t2 1 t2 2 [7]. Figure 3: Rotation of tetrahedron by 120◦ and 240◦ T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 94 Then by Burnside’s Lemma we have Z(G, t1, t2, . . . , t6) = 1 12 (t6 1 + 8t2 3 + 3t2 1 t2 2) (a) The number of distinct 2 colorings on tetrahedron edge will be ZG = 1 12 (26 + 8(22) + 3(22)(22)) = 12 (b) Now we will apply Pólya’s Substitution method. Let the colors black and yellow be denoted by x and y respectively. Then substituting t i → (x i + y i) for each i = {1,2,3,4,5,6} in the previous equation, we get ZG = 1 12 ((x + y)6 + 8(x3 + y3)2 + 3(x + y)2(x2 + y2)2) By Maple we get, ZG = x6 + x5 y + 2x4 y2 + 4x3 y3 + 2x2 y4 + x y5 + y6 The term 4x3 y3 contains tetrahedron with 3 black and 3 yellow edges. The coefficient of this term is 4. Hence there are 4 ways to color the edge of tetrahedron. 2.4. Pólya’s Fundamental Theorem Theorem 2. The Pattern inventory is P I = ZG( ∑ c∈C wc , ∑ c∈C w2 c , ∑ c∈C w3 c , . . . , ∑ c∈C wp c ) where ZG is the cycle index and p = |D| [2]. Proof. Let X = X1 ∪ X2 ∪ . . .∪ Xm be the equivalence classes of X under the relation x ∼ y if and only if W (x) =W (y) By Orbit-Stabilizer Formula, g ∗ x ∼ x for all x ∈ X , g ∈ G and so we can think of G acting on each X i individually. We use the fact that x ∈ X i implies g ∗ x ∈ X i for all i ∈ [m], g ∈ G. We use the notation g(i) ∈ G(i) when we restrict attention to X i . Let mi denote the number of orbits. Then PI = m ∑ i=1 miWi = m ∑ i=1 Wi( 1 |G| ∑ g∈G |F ix(g(i))|), By Burnside’s Lemma, we have PI = 1 |G| ∑ g∈G m ∑ i=1 |F ix(g(i))|Wi = 1 |G| ∑ g∈G W (F ix(g)) (2) T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 95 Note that (1) follows F ix(g) = ⋃m i=1 F ix(g(i)) since x ∈ F ix(g(i)) if and only if x ∈ Wi and g ∗ x = x . Suppose that ZG = x k1 1 x k2 2 . . . x kp p . Then we can claim that W (F ix(g)) = ( ∑ c∈C wc) k1( ∑ c∈C wc) k2 . . . ( ∑ c∈C wc) kp (3) Substituting (2) and (3) yields the theorem. To verify (2) we use the fact that if x ∈ F ix(g)), then the elements of a cycle of g must be given the same color. A cycle of length i will then contribute a factor ∑ c∈C wi c where the term wi c comes from the choice of c for every element of the cycle [8]. Example 13. Let A= {1,2,3,4,5,6} and B = {white, black, gra y}. Consider a function f ∈ BA which is a 6-tuple of colors and can be viewed as necklace representation. w1 w 2 b 3 b 4 g 5 b6 Figure 4: Colored Necklace Now we are interested to assign different weights to the beads. Suppose that black(b) = 1, white(w) = 10 and gra y(g) = 100. Then the weight of the necklace is W ( f ) = 10× 10× 1× 1× 100= 104 Note that rotation does not change the weight. To count the necklaces (without weight), we have to calculate the number of fixed points for each element of C6. T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 96 Table 1: Fixed Points Element g | f i x(g)| e 36 (1,2,3,4,5,6) 3 (1,3,5)(2,4,6) 32 (1,4)(2,5)(3,6) 33 (1,5,3)(2,6,4) 32 (1,6,5,4,3,2) 3 Now we have to consider counting the sums of the weights of the fixed points of each element of C6. Let us calculate Wfix(g) for the element g = (1,4)(2,5)(3,6). For a function f to be fixed by g we must have f (1) = f (4) f (2) = f (5) f (3) = f (6) and hence W ( f ) =W ( f (1))2W ( f (2))2W ( f (3))2 Now f (1), f (2) and f (3) can be any white, black or gray and that is why W f ix(g) = (W (white)2 +W (black)2 +W (gra y)2)3 . By repeating this process we can find out the other elements of C6. Then we get Table 2: Weighted Fixed Points Element g Wfix(g) e (W (white) +W (black) +W (gra y))6 (1,2,3,4,5,6) W (white)6 +W (black)6 +W (gra y)6 (1,3,5)(2,4,6) (W (white)3 +W (black)3 +W (gra y)3)2 (1,4)(2,5)(3,6) (W (white)2 +W (black)2 +W (gra y)2)3 (1,5,3)(2,6,4) (W (white)3 +W (black)3 +W (gra y)3)2 (1,6,5,4,3,2) W (white)6 +W (black)6 +W (gra y)6 For any given values of W (white),W (black) and W (gra y) we can calculate this sum and find the sum of the weights of the weighted (6,3)− necklaces. At this moment we would like to apply Pólya’s Fundamental Theorem. First we need to assign the weights of the three colors. Let W (white) = x, W (black) = y and W (gra y) = z. Then the weight of a necklace representative is not a number, but a multivariate polynomial in the variables x, y and z [8]. W ( f ) = x × x × y × y × z × y = x2 y3z. T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 97 x1 x 2 y 3 y 4 z 5 y6 Figure 5: Weighted Necklace By using Burnside’s Lemma we get that Z(C6, t1, t2, . . . , t6) = 1 6 (t6 1 + t3 2 + 2t2 3 + 2t6) According to Pólya’s Substitution we have t1 7−→ x + y + z, t2 7−→ x2 + y2 + z2, t3 7−→ x3 + y3 + z3, t4 7−→ x4 + y4 + z4, t5 7−→ x5 + y5 + z5, t6 7−→ x6 + y6 + z6, Now PI = 1 6 ((x + y + z)6 + (x2 + y2 + z2)3 + 2(x3 + y3 + z3)2 + 2(x6 + y6 + z6)) Using Maple the result becomes P I =16x2 y2z2 + 10x3 y2z + 5x4 yz + 10x3 yz2 + 10x2 y3z + 10x y3z2 + 10x y2z3 + 5x y4z + x5 y + x5z + 3x4 y2 + 3x4z2 + 4x3 y3 + 4x3z3 + 3x2y4 + 3x2z4 + x y5 + xz5 + y5z + 3y4z2 + 4y3z3 + 3y2z4 + yz5 + 10x2 yz3 + 5x yz4 + x6 + y6 + z6 Each term of this expression corresponds to necklaces with a fixed number of red, green and blue beads. For example, the term 3x2 y4 says that there are 3 orbits with weight x y4z or in other words 3 necklaces with 2 white beads, 4 black beads and 0 gray. They are T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 98 x1 y 2 y 3 y 4 x 5 y6 (a) y1 x 2 y 3 y 4 x 5 y6 (b) x1 x 2 y 3 y 4 y 5 y6 (c) Figure 6: 3 Necklaces with 2 White Beads and 4 Black Beads Problem 2 (Face Coloring of a Cube). A cube has 6 faces and the faces are to be colored. How many inequivalent ways are there to color it with namely (a) 4 red and 2 green faces? (b) 3 red, 2 green and 1 blue faces? (c) 2 red, 1 green, 1 blue and 2 yellow faces? Solution: We have to color the faces of the cube. So recall Example 11. Then the cycle index is Z(G, t1, t2, . . . , t6) = 1 24 (6t2 1 t4 + 3t2 1 t2 2 + 8t2 3 + 6t3 2 + t6 1) Now we will apply Pólya’s Substitution method. Let the colors red, green, blue and yellow be denoted by x , y, z and p respectively. Then substituting t i → (x i + y i + z i + pi) for each i = {1,2,3,4,5,6} in the previous equation, we get ZG = 1 24 (6(x + y + z + p)2(x4 + y4 + z4 + p4) + 3(x + y + z + p)2(x2 + y2 + z2 + p2)2 + 8(x3 + y3 + z3 + p3)2 + 6(x2 + y2 + z2 + p2)3 + (x + y + z + p)6) Using Maple we find that, ZG =3y3px2 + 3y3zp2 + 3yz3p2 + 3y3pz2 + 3yp3z2 + 3x p3 y2 + 3x3p y2 + 3x3pz2 + 3x p3z2 + 6x2z2p2 + 2ypx4 + 2zpx4 + 2yzp4 + 2x pz4 + 3zp3 y2 + 2yzx4 + 8x yz2p2 + 8xz y2p2 + 8x p y2z2 + 8yzx2p2 + 8ypx2z2 + 8zpx2 y2 + 5x3 yzp + 5x y3zp+ 5x yzp3 + 5x yz3p+ 3yz3 x2 + 3yp3 x2 + 3x y3z2 + 2x yz4 + 6x2 y2z2 + 6x2 y2p2 + 2ypz4 + 2x p y4 + 2x yp4 + 3xz3p2 + 3x3zp2 + 2xzp4 + 3x3 yp2 T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 99 + 3x3 yz2 + 3x y3p2 + 2zp y4 + 2xz y4 + 3y3zx2 + 3x3zy2 + 3z3px2 + 6y2z2p2 + 3z3p y2 + 3zp3 x2 + 3xz3 y2 + 2y2z4 + y5z + yz5 + 2z2 x4 + 2z2 y4 + x5z + xz5 + 2y2x4 + 2x2 y4 + 2x2z4 + x5 y + x y5 + x6 + y6 + z6 + p6 + 2x3 y3 + 2x3z3 + 2y3z3 + 2x2p4 + x5p+ x p5 + 2y2p4 + y5p+ yp5 + 2z2p4 + z5p+ zp5 + 2p2 x4 + 2p2 y4 + 2p2z4 + 2x3p3 + 2y3p3 + 2z3p3 Each term of this expression on the right hand side corresponds to a fixed number of red, green, blue and yellow colors. (a) The term 2x4 y2 says that there are 2 possible ways to color the cube with 4 red and 2 green faces. (b) The term 3x3 y2z says that there are 3 possible ways to color the cube with 3 red, 2 green and 1 blue faces. (c) The term 8x2 yzp2 says that there are 8 possible ways to color the cube with 2 red, 1 green, 1 blue and 2 yellow faces. Problem 3 (Vertex Coloring of a Cube). A cube has 8 vertices and the vertices are to be colored. How many inequivalent ways are there to color it with (a) 6 black, 1 yellow and 1 green vertices? (b) 1 black, 1 red, 4 blue and 2 yellow vertices? (c) 3 black, 1 red, 1 green 1 blue and 2 yellow vertices? Solution: We have to color the vertices of the cube. So recall Example 12. Then the cycle index is Z(G, t1, t2, . . . , t8) = 1 24 (6t2 4 + 9t4 2 + 8t2 1 t2 3 + 6t3 2 + t8 1). Now we will apply Pólya’s Substitution method. Let the colors black, red, green, blue and yellow be denoted by x , y, z, p and v respectively.Then substituting t i → (x i+ y i+z i+ pi+ v i) for each i = {1,2,3,4,5,6,7,8} in the previous equation, we get ZG = 1 24 (6(x4 + y4 + z4 + p4 + v4)2 + 9(x2 + y2 + z2 + p2 + v2)4 + 8(x + y + z + p+ v)2(x3 + y3 + z3 + p3 + v3)2 + 6(x2 + y2 + z2 + p2 + v2)3 + (x + y + z + p+ v)8). We use Maple to expand and find that the expression on the right hand side is very long. Each term of this expression corresponds to a fixed number of black, red, green, blue and yellow colors. (a) the term 3x6zv contains cube with 6 black, 1 green and 1 yellow vertices. The coefficient of this term is 3. Hence there are 3 possible ways to color the cube. T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 100 (b) In this case the term is 35p4v2 x y which contains cube 1 black, 1 red, 4 blue and 2 yellow vertices. So there are 35 ways to color the cube. (c) For this we need to find out the coefficient of the term 140pv2 x3 yz which contains cube with 3 black, 1 red, 1 green 1 blue and 2 yellow vertices. There are 140 ways to color the cube. Problem 4 (16 Bead Necklace). Count the number of ways to arrange beads on a necklace, where 16 total beads arranged on the necklace with (a) 2 different colors; (b) 14 red and 2 black colors; (c) 4 different colors; Solution: With a necklace, we will obviously rotate it around and flip over it. We will also use the Definition 2 with the formula for the cyclic and dihedral groups to solve this problem. The cycle index of this group C16 from (1) is Z(C16, t1, . . . , t16) = 1 16 ∑ l/16 φ(l)t 16/l l = 1 16 (φ(1)t 16/1 1 +φ(2)t 16/2 2 +φ(4)t 16/4 4 +φ(8)t 16/8 8 +φ(16)t 16/16 16 ) = 1 16 (t16 1 + t8 2 + 2t4 4 + 4t2 8 + 8t1 16) Now we will illustrate the formula by computing the cycle index of D16 Z(D16, t1, . . . , t16) = 1 2 Z(C16, t1, . . . , t16) + 1 4 (t8 2 + t2 1 t7 2) = 1 2 ( 1 16 (t16 1 + t8 2 + 2t4 4 + 4t2 8 + 8t1 16)) + 1 4 (t8 2 + t2 1 t7 2) = 1 32 (t16 1 + 9t8 2 + 8t2 1 t7 2 + 2t4 4 + 4t2 8 + 8t1 16) (4) Let us consider 2 colors red and black denoted by x and y respectively. Now we will ap- ply Pólya’s Substitution Method. Substituting t i → (x i + y i) for each i = {1,2,3, . . . , 16} in equation (4), we get Z(D16, t1, . . . , t16) = 1 32 ((x + y+)16 + 9(x2 + y2)8 + 8(x + y)2(x2 + y2)7 + 2(x4 + y4)4 + 4(x8 + y8)2 + 8(x16 + y16)1) (i) Let x = y = 1. Then using Maple by the above equation we get the total count 2250. T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 101 (ii) Expanding the same equation we have by Maple ZD16 =x15 + 8x14y2 + 21x13 y3 + 72x12 y4 + 147x11 y5 + 280x10 y6 + 375x9 y7 + 440x8 y8 + 375x7 y9 + 280x6 y10 + 147x5 y11 + 72x4 y12 + 21x3 y13 + 8x2 y14 + x y15 + x16 + y16 The term 8x14 y2 contains 14 red and 2 black colors. The coefficient of this term is 8. So there are 8 ways to decorate a 16 beaded Necklace with 14 red and 2 black colors. (iii) For this case consider 4 colors x , y, z, and p. We will again apply Pólya’s Substitution Method. Substituting t i → (x i + y i + z i + pi) for each i = {1,2,3, . . . , 16} in equation (4), we get Z(D16, t1, . . . , t16) = 1 32 ((x + y + z + p)16 + 9(x2 + y2 + z2 + p2)8 + 8(x + y + z + p)2(x2 + y2 + z2 + p2)7 + 2(x4 + y4 + z4 + p4)4 + 4(x8 + y8 + z8 + p4)2 + 8(x16 + y16 + z16 + p16)1) Let x = y = z = p = 1. Then using Maple by the above equation we get the total count 134301715. 3. Generalization of Pólya’s Theorem In the preceding sections we considered mappings of X into Y , introduced by a permutation group G of X . We are now going to move on more general situation. Let us consider two mappings f1 ∈ Y X and f2 ∈ Y X . They are equivalent if there exist elements g ∈ G and h ∈ H such that f1 g = hf2, that is f1(g x) = hf2(x) for all x ∈ X . Next we assume that each f ∈ Y X has a certain weight W ( f ). Then we can also assume that equivalence functions have the same weight: f1 ∼ f2 implies W ( f1) =W ( f2). If F denotes a pattern, we define its weight W (F) as the common value of all W ( f ) with f ∈ F [2]. Lemma 2. The Pattern inventory is ∑ W (F) = 1 |G| 1 |H| ∑ g∈G ∑ h∈H (g,h) ∑ f W ( f ) where ∑(g,h) f W ( f ) means the sum of W ( f ) extended over all f that satisfy f g = hf [2]. T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 102 3.1. Patterns of One-to-one Mappings We already have the finite sets X and Y , subject to the permutation groups G and H. Now we define the weight W ( f ) of any f ∈ Y X by W ( f ) = ¨ 1 if f is a one-to-one mapping 0 otherwise If g ∈ G and h ∈ H, then the mapping hf g−1 is one-to-one if and only if f is one-to-one and thus W ( f1) =W ( f2). The inventory ∑ W (F) is just the number of patterns of one-to-one function. Now let g be of type {g1, g2, . . .}where gi shows the number of cycles of length i. Similarly let h be of type {h1,h2, . . .}. We will find the number of one-to-one mappings f of Y into X that satisfies f g = hf . Let x be any element in X , belonging to a cycle of length j. This cycle consists of elements x , g x , g2 x , . . . , g j−1 x and we have g j x = x . Now f g = hf implies f g2 = f g g = hf g = hhf = h2 f , f g3 = h3 f , . . . Hence we have h j f x = f g j x = f x . It follows that the length of cycle of Y to which f x belongs is a divisor of j. The number of elements of one-to-one mappings of a set g j elements into a set of h j elements equals h j(h j − 1)(h j − 2) . . . (h j − g j + 1) which is zero if h j < g j . Therefore we have (g,h) ∑ f W ( f ) = ∏ j jg j h j(h j − 1)(h j − 2) . . . (h j − g j + 1). This product runs over all j for g j > 0; but if g j = 0 we can take the over all values j = 1,2,3, . . . as well. Next we can write jgh(h−1)(h−2) . . . (h− g+1) as gth derivative of (1+ jz)h at the point z = 0. As the result of a number of partial differentiations with respect to variables z1, z2, . . . at the points z1 = z2 = . . .= 0, we have � ∂ ∂ z1 �g1 � ∂ ∂ z2 �g2 � ∂ ∂ z3 �g3 . . . (1+ z1) h1(1+ 2z2) h2(1+ 3z3) h3 . . . The differential operator is obtained from a term of cycle index ZG(t1, t2, . . .) of G upon sub- stitution of t1 = ∂ ∂ z1 , t2 = ∂ ∂ z2 , . . . and the operand is obtained upon substitution of t1 = 1+z1, t2 = 1+ 2z2, . . . into a term of the index ZH(t1, t2, ..) of H [2]. Theorem 3. The number of patterns of one-to-one mappings of X into Y equals ZG � ∂ ∂ z1 , ∂ ∂ z2 , ∂ ∂ z3 , . . . � ZH(1+ z1, 1+ 2z2, 1+ 3z3, . . .) evaluated at z1 = z2 = z3 = . . .= 0. T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 103 If |X |= |Y |, then we always have ∑ j g j = ∑ j h j . So that we have either g1 = h1, g2 = h2, . . . or at least once g j > h j . Thus we have [2] � ∂ ∂ z1 �g1 � ∂ ∂ z2 �g2 � ∂ ∂ z3 �g3 . . . (z1) h1(2z2) h2(3z3) h3 . . . . . Theorem 4. If |X |= |Y |, then the number of patterns is equal to ZG � ∂ ∂ z1 , ∂ ∂ z2 , ∂ ∂ z3 , . . . � ZH(z1, 2z2, 3z3, . . .) evaluated at z1 = z2 = z3 = . . .= 0. The inverse mappings are one-to-one mappings of Y onto X . In this case we can easily find that the number of patterns is equal to ZH � ∂ ∂ z1 , ∂ ∂ z2 , ∂ ∂ z3 , . . . � ZG(z1, 2z2, 3z3, . . .) evaluated at z1 = z2 = z3 = . . .= 0 [2]. Problem 5. How many geometrically different ways can the faces of a cube be arranged in cyclic order [2]? Solution: We need to find out the number of patterns of one-to-one mappings. Let X be the set of faces of a cube and G be the cube induced by rotations(Example 11); Y be the 6th roots of unity and again H is the group of permutation induced by the rotations in the complex plane (Definition 2 with cycle index formula Z(Cn)). Then |X |= |Y |. The cycle indexes are ZG = 1 24 (t6 1 + 6t3 2 + 8t2 3 + 3t2 1 t2 2 + 6t2 1 t4) ZH = 1 6 (t6 1 + t3 2 + 2t2 3 + 2t6) The number of patterns is equal to ZG � ∂ ∂ z1 , ∂ ∂ z2 , ∂ ∂ z3 � ZH(z1, 2z2, 3z3) = 1 24 · 1 6 � � ∂ ∂ z1 �6 (z1) 6 + � ∂ ∂ z2 �3 (2z2) 3 + � ∂ ∂ z3 �2 (3z3) 2 � = 1 24 · 1 6 (6!+ 6 · 23 · 3!+ 16 · 32 · 2!) =9 Problem 6. How many geometrically different ways can the edges of a tetrahedron be ar- ranged in cyclic order? T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 104 Solution: Here we also need to find out the number of patterns of one-to-one mappings. Again let X be the set of edges of a tetrahedron and G be the tetrahedron induced by rotations;Y be the 6th roots of unity and again H is the group of permutation induced by the rotations in the complex plane (Definition 2 with cycle index formula Z(Cn)). Then |X |= |Y |. The cycle indexes are ZG = 1 12 (t6 1 + 8t2 3 + 3t2 1 t2 2) ZH = 1 6 (t6 1 + t3 2 + 2t2 3 + 2t6) The number of patterns is equal to ZG � ∂ ∂ z1 , ∂ ∂ z3 � ZH(z1, 2z2) = 1 12 · 1 6 � � ∂ ∂ z1 �6 (z1) 6 + � ∂ ∂ z3 �2 (3z3) 2 � = 1 12 · 1 6 (6!+ 16 · 32 · 2!) =14 Example 14. We have 6 colored labels l1, l2, l3, l4, l5, l6 to be pasted on the faces of a cube, one on each side. Label l1 and l2 are yellow and black respectively. The labels l3 and l4 are both violet and can not be distinguished from each other. The same condition holds for l5 and l6 which are both purple. We are interested to find out the number of patterns. Now X be set of 6 labels and Y is the set of 6 faces. The group G consists of 8 permutations, characterized by the conditions that l1 and l2 are fixed and the subset {l3, l4} mapped onto either itself or the set {l5, l6} [2]. The cycle index of this group is ZG = 1 8 (t6 1 + 2t4 1 t2 + 3t2 1t2 2 + 2t2 1t4) and also given by ZH = 1 24 (t6 1 + 6t3 2 + 8t2 3 + 3t2 1t2 2 + 6t2 1t4) For the number of patterns we obtain ZH � ∂ ∂ z1 , ∂ 2 ∂ z1∂ z2 , ∂ 2 ∂ z1∂ z4 � ZG(z1, 2z2, 4z4) = 1 24 · 1 8 � � ∂ ∂ z1 �6 (z1) 6 + � ∂ 2 ∂ z1∂ z2 �2 (z12z2) 2 + � � ∂ ∂ z1 �2� ∂ ∂ z1 � � (z2 14z4) � = 1 24 · 1 8 (6!+ 3 · 3 · 2!22 · 2!+ 6 · 2 · 2!4 · 1!) =5 T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 105 Example 15. Consider 6 colors l1, l2, l3, l4, l5, l6 to be colored on the edges of a tetrahedron, one on each edge by following the same conditions with Example 14. Then the cycle index of this group is ZG = 1 8 (t6 1 + 2t4 1 t2 + 3t2 1t2 2 + 2t2 1 t4) and also given by ZH = 1 12 (t6 1 + 8t2 3 + 3t2 1t2 2) For the number of patterns we obtain ZH � ∂ ∂ z1 , ∂ 2 ∂ z1∂ z2 � ZG(z1, 2z2) = 1 12 · 1 8 � � ∂ ∂ z1 �6 (z1) 6 + � ∂ 2 ∂ z1∂ z2 �2 (z12z2) 2 � = 1 12 · 1 8 (6!+ 3 · 3 · 2!22 · 2!) =9 3.2. The Total Number of Patterns Again consider finite sets X and Y with permutation groups G and H of X and Y re- spectively. We will find the number of patterns. Again we will apply Lemma 2 to evaluate ∑(g,h) f W ( f ). We will use the subsection 3.1. So we can easily compute the number of possi- bilities for f . For each cycle of X we will select an element, called the selected element. The number of possibilities for the element of Y onto which is selected element can be mapped by an f is ∑ j/i jc j , where i is the length of the cycle of X to which the selected item belongs, c′s are of type {c1, c2, . . .} of h and the sum is over all divisors j of i. Because the choices of function values for the various selected elements are independent and determine f completely. The number of f equals the product of ∑ j/i jc j taken over all selected elements. Since there are gi cycles of length i, then we get (g,h) ∑ f W ( f ) = ∏ ( ∑ j/i jc j) gi =(c1) g1(c1 + 2c2) g2(c1 + 3c3) g3(c1 + 2c2 + 4c4) g4 . . . (5) Note that a power with exponent 0 has to be interpreted as 1 in this context even if the base is zero. Therefore is no difficulty about the interpretation of the infinite product. As in subsection 3.1, we can interpret the previous equation as a derivative. A power ab can be written as the bth derivative of eaz at z = 0; if a = b = 0, this still gives the desired value 0◦ = 1. So the previous expression can be written as � ∂ ∂ z1 �g1 � ∂ ∂ z2 �g2 � ∂ ∂ z3 �g3 . . . ex p( ∑ i zi ∑ j/i jc j), T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 106 evaluated at z1 = z2 = . . .= 0. The exponent can be expressed as ( ∑ i zi ∑ j/i jc j) = ∑ j jc j(z j + z2 j + z3 j + . . .). Now the differential operator is obtained from t g1 1 t g2 2 t g3 3 . . . on substitution of t1 = ∂ ∂ z1 , t2 = ∂ ∂ z2 , t3 = ∂ ∂ z3 4, . . . and the operand is obtained from t c1 1 t c2 2 t c3 3 . . . on substitution of [2] t1 = ez1+z2+z3+..., t2 = e2(z2+z4+z6+...), t3 = e3(z3+z6+z9+...), . . . . Theorem 5. The total number of patterns of mapping of X into Y equals ZG � ∂ ∂ z1 , ∂ ∂ z2 , ∂ ∂ z3 , . . . � ZH[e z1+z2+z3+..., e2(z2+z4+z6+...), e3(z3+z6+z9+...), . . .] evaluated at z1 = z2 = z3 = . . .= 0. There is a second expression for the number of patterns, which sometimes may turn out to be simpler to handle. Note that (5) is obtained by substituting t1 = c1, t2 = c1 + 2c2, . . . into t g1 1 t g2 2 . . .. Summing for g and dividing by |G|, we obtain ZG(c1, c1 + 2c2, c1 + 3c3, c1 + 2c2 + 4c4, . . .), in which the ith argument is ∑ j/i jc j . Thus again using Lemma 2 for the number of patterns we have |H|−1 ∑ h∈H ZG(c1, c1 + 2c2, c1 + 3c3, c1 + 2c2 + 4c4, . . .) Here it has to be remembered that {c1, c2, c3, . . .} is of type h [2]. Now we are going to discuss some of the examples. In all cases, m and n stand for the number of elements of X and Y respectively. Example 16. Let G be a group consisting of the identity only, where ZG = tm 1 . Then the patterns are called patterns of variation with repetition. Now let {1,2, . . . , m} be a sequence of X then for each f ∈ X Y , the sequence { f (1), f (2), . . . , f (m)} shows repetitions. For the number of patterns, theorem 4 gives the expression �� d dz �m ZH(e z, 1, 1, . . .) � z=0 (6) A second specialization of (6) can be obtained by keeping Y and H general but X has only one element d1. Now two functions f1 and f2 are equivalent if and only if f1(d1) are mapped to f2(d1). So the number of patterns is the number of transitive sets. If we take m = 1 in (6) then we get |H|−1c1 and c1 is the number of elements of Y that are invariant under the permutation h [2]. Example 17. Again let G be the symmetric group of X with H not specified. We are only interested in the number of elements of X that a function f maps onto a given element of Y . Thus our patterns of mappings ψ of Y into the set P = {0,1,2, . . .}, with restriction ∑ r∈Rψ(r) = m, T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 107 whereas patterns are formed with respect to H acting on Y . Let the weights of P be 1, w1, w2, . . .. If we apply theorem 4, we have as differential operator the coefficient of wm in ex p(w ∂ ∂ z1 + 1 2 w2 ∂ ∂ z2 + . . .) by Example 5. The effect of this operator on a function ψ(z1, z2, . . .) at z1 = z2 = . . . = 0 is ψ(w, 1 2 w2, 1 3 w3, . . .). Now by substituting z1 = w, z2 = 1 2 w2, z3 = 1 3 w3, . . . in theorem 4 we get ex p(z1 + z2 + . . .) =ex p(w+ 1 2 w2 + 1 3 w3 + . . .) = (1− w)−1 ex p(2(z2 + z4 + . . .)) =ex p(w2 + 1 2 w4 + 1 3 w6 + . . .) = (1− w2)−1 etc. Thus we obtain ZH[(1−w)−1, (1− w2)−1, . . .] [2]. Example 18. Next let us take for H the symmetric group of all permutations of Y and for G take the identity only. Now the patterns turn out to be class partition of X into at most m parts, where a class partition is defined as a set of disjoint subsets(classes) of X whose union is X . The previous result follows from the fact that if f ∈ Y X , then f defines a class partition by putting into one class all d that are mapped by f onto one and the same element of Y . According to (a) and Example 5 we find that the number of patterns is the coefficient of wm in �� d dz �m ex p(wez + 1 2 w2 + 1 3 w3 + . . .) � z=0 and we can easily find to be m! times the coefficient of zmwn in the expression of (1−w)−1ew(ez−1). Here the number of partitions can be at most n parts. So the total number of patterns equals m! times the coefficients of zm in eez−1 [2]. Example 19. Now we are interested for H the symmetric group of X without any specialization of G. We get partitions of class partitions of X . It seems to us impossible to simplify the result of theorem 4. If we take G to the symmetric group of X , the partitions become class partitions of a set of unidentifiable objects. So we are only concern about the size of the classes. Our patterns can be brought into one-to-one correspondence with the partitions of m into at most n parts. A partition of m is a solution {g1, g2, . . .} of the equation g1 + 2g2 + 3g3 + . . .= m in nonnegative integers g1, g2, . . . So m has been partitioned into g1 1’s, g2 2’s, . . . and accordingly g1 + g2 + g3 + . . . is called the number of parts of the partition. The number of partitions can be obtained from Example 17 by specializing H to be the sym- metric group. We obtain the coefficient of zm in ZH[(1− z)−1, (1− z2)−1, . . .] T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 108 which becomes in this case, the coefficient of zmwn in ex p[w(1− z)−1 + 1 2 w2(1− z2)−1 + 1 3 w3(1− z3)−1 + . . .], and this expression can be reduced to ex p[log(1−w)−1 + log(1−wz)−1 + log(1−wz2)−1 + . . .] = ∞ ∏ k=1 1 1− wzk . This is a well-know result for the generating function of the number of partitions of a given number into a given number of components [2]. Example 20. Let H be a symmetric group and let G be specialized by taking n = 2. So the patterns of class partitions into at most two parts. By (5) the number of these is 1 2 ZG(2,2,2, . . .) + 1 2 ZG(0,2,0,2, . . .), since ZH = 1 2 t2 1 + 1 2 t2. If we compare this to the number of patterns of partitions into two labeled classes, ZG(2,2,2, . . .), we observe that the term ZG(0,2,0,2, . . .) represents the number of symmetric patterns of X into two classes X1 and X2. That is, ZG(0,2,0,2, . . .) represents the number of symmetric patterns of subsets X1 that are equivalent to there complement, where equivalence is defined by the permuta- tions of G and patterns are defined by this equivalence. Let X be the set of 10 roots of unity and G be the group of 10 rotations. The cycle index (see Definition 2 with cyclic groups formula (1)) is ZG = 1 10 (t10 1 + t5 2 + 4t2 5 + 4t10) and therefore [2] ZG(0,2,0,2, . . .) = 1 10 ((2)5 + 4.2) = 4. Theorem 6 (Pólya). We have ZG[H](t1, t2, . . .) = ZG[ZH(t1, t2, t3, . . .), ZH(t2, t4, t6, . . .), . . .] where ZG[H] is in Kranz group and the the right hand side is obtained on substitution of x j = ZH(t j , t2 j , t3 j , . . .) into ZG(x1, x2, x3, ...) [2]. Example 21. Consider n cubes and we want to color the faces with Red and Yellow. We are interested for the number of ways to do this when equivalences are defined by permutations of the sets of cubes and rotations of the separate cubes. The group is considered as Sn[G] where Sn is the symmetric group of degree n and G is the cube-face group of Example 11. Then we have to substitute t1 = t2 = . . . = 2 in to its cycle index to find the required number. If we make this substitution in any of the polynomials ZG(t1, t2, t3, . . .), ZG(t2, t4, t6, . . .), ZG(t3, t6, t9, . . . ), . . . , (7) T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 109 we always get ZG(2,2,2, . . .) and hence ZG(2,2,2, . . .) = 1 24 (6(2)2(2) + 3(2)2(2)2 + 8(2)2 + 6(2)3 + 26) = 10 Thus the answer of the question is Sn(10,10,10, . . .). This number equals the coefficient of wn in the development of ex p(10w+ 1 2 10w2 + 1 3 10w3 + . . .) = (1−w)−10 therefore Sn(10,10,10, . . .) = (n+ 9)! n!9! How many of the preceding patterns have the property that they do not change if we interchange the color? According to Example 20 this number is found by substituting t1 =t3 = t5 = ....= 0, t2 =t4 = t6 = ...= 2 into the cycle index. Under the substitution the polynomials (7) become ZG(0,2,0,2, . . .) and ZG(2,2,2, . . .), alternately. As ZG(0,2,0,2, . . .) = 2. We obtain ZSn[G] (0,2,0,2, . . .) = ZSn (2,10,2,10, . . .) This is the coefficient of wn in ex p(2w+ 1 2 10w2 + 1 3 2w3 + 1 4 10w4 + . . . .) =ex p[2log(1−w)−1 + 8log(1−w2)−1/2] =(1−w)−2(1−w2)−4 =(1+ 2w+w2)(1−w2)−6 =1+ 2w+ 7w2 + 12w3 + 27w4 + 42w5 + 77w6 + 112w7 + 182w8 + 252w9 + . . . For example if n= 9 the required number of patterns is 252 [2]. Example 22. Consider n tetrahedrons and we want to color the edges with Red and Yellow. By following problem 1 we get from edge coloring of a Tetrahedron ZG(2,2,2, . . .) = 12 Thus the answer of this question is Sn(12,12,12, . . .). This number equals the coefficient of wn in the development of ex p(12w+ 1 2 12w2 + 1 3 12w3 + . . .) = (1−w)−12 T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 110 therefore Sn(12,12,12, . . .) = (n+ 11)! n!11! Now we want to find the number of the preceding patterns having the property that they do not change if we interchange the color. Again following problem 1 we get ZSn[G] (0,2,0,2, . . .) = ZSn (2,12,2,12, . . .) This is the coefficient of wn in ex p(2w+ 1 2 12w2 + 1 3 2w3 + 1 4 12w4 + . . . .) =ex p[2log(1−w)−1 + 10log(1−w2)−1/2] =(1−w)−2(1−w2)−5 =(1+ 2w+w2)(1−w2)−7 =(1+ 2w+w2)(1+ 7w2 + 28w4 + . . .) =1+ 2w+ 8w2 + 14w3 + 35w4 + . . . For example if n= 4 the required number of patterns is 35. Problem 7. Let us take n cubes and we want to color the faces with Red, Yellow and green. We are interested for the number of ways to do this when equivalences are defined by permutations of the sets of cubes and rotations of the separate cubes. Solution: The group is considered as Sn[G] where Sn is the symmetric group of degree n and G is the cube-face group of Example 11. Then we have to substitute t1 = t2 = . . .= 3 in to its cycle index to find the required number. If we make this substitution in any of the polynomials ZG(t1, t2, t3, ] . . .), ZG(t2, t4, t6, . . .), ZG(t3, t6, t9, . . .), . . . , we always get ZG(3,3,3, . . .) and hence ZG(3,3,3, . . .) = 1 24 (6(3)2(2) + 3(3)2(3)2 + 8(3)2 + 6(3)3 + 36) = 57 Thus the answer of the question is Sn(57,57,57, . . .). This number equals the coefficient of wn in the development of ex p(57w+ 1 2 57w2 + 1 3 57w3 + . . .) = (1−w)−57 therefore Sn(57,57,57, . . .) = (n+ 56)! n!(56)! How many of the preceding patterns have the property that they do not change if we inter- change the color? T. Nasseef / Eur. J. Pure Appl. Math, 9 (2016), 84-113 111 By (5), this number is found by substituting t1 =t2 = t4 = t5 . . .= 0, t3 =t6 = t9 = . . .= 3 into the cycle index. Under the substitution the polynomials become ZG(0,0,3,0,0,3, . . .) and ZG(3,3,3, . . .), alternately. As ZG(0,0,3,0,0,3, . . .) = 3. We obtain ZSn[G] (0,0,3,0,0,3, . . .) = ZSn (3,3,57,3,3,57, . . .) This is the coefficient of wn in ex p(3w+ 1 2 3w2 + 1 3 57w3 + 1 4 3w4 + ....) =ex p[3log(1−w)−1 + 54log(1−w3)−1/3] =(1−w)−3(1−w3)−18 =(1+ 3w+ 6w2 + 10w3 . . .)(1+ 18w3 + 171w6 + . . .) =1+ 3w+ 6w2 + 28w3 + . . . For example if n= 3 the required number of patterns is 28. Problem 8. Let us take n cubes and we want to color the faces with Red, black, Yellow and green. How many of the patterns have the property that they do not change if we interchange the color? Solution: With the help of (5), this number is found by substituting t1 =t3 = t5 = t7 . . .= 0, t2 =t6 = t10 = . . .= 4, t4 =t8 = . . .= 4 into the cycle index. Under the substitution the polynomials become ZG(0,0,0,4,0,0,0,4, . . .), ZG(0,4,0,4,0,4,0,4, . . .) and ZG(4,4,4, . . .), alternately. Now ZG(4,4,4, . . .) = 1 24 (6(4)2(4) + 3(4)2(4)2 + 8(4)2 + 6(4)3 + 46) = 240 and ZG(0,4,0,4, . . .) = 1 24 (6(0)2(4) + 3(0)2(4)2 + 8(0)2 + 6(4)3 + 06) = 16 As ZG(0,0,0,4,0,0,0,4, . . .) = 0. We obtain ZSn[G] (0,0,0,4,0,0, . . .) = ZSn (0,16,0,240,0,16,0,240, . . .) This is the coefficient of wn in ex p(0w+ 1 2 16w2 + 1 3 0w3 + 1 4 240w4 + . . .) REFERENCES 112 =ex p( 1 2 16w2 + 1 4 240w4 + 1 6 16w6 + 1 8 240w8 . . .) =ex p[16log(1−w2)−1/2 + 224log(1−w4)−1/4] =(1−w2)−8(1−w4)−56 =(1+ 8w2 + 36w4 + . . .)(1+ 56w4 + 1596w8 + . . .) =1+ 8w2 + 92w4 + . . . For example if n= 4 the required number of patterns is 92. 4. Conclusion Counting symmetries is a vast and challenging topic. Many Mathematicians have already researched on it. In this study it has already observed that Pólya’s Theory has remarkable and numerous applications in counting symmetries. This theory has been used on Colorings on Cube (Faces and Vertices) and Tetrahedron. Furthermore we have also discussed on Gen- eralization of Pólya’s Theorem with some problems and examples; but there are penalty of other uses as well. Pólya and Reade[9] mentioned the other following applications without exploring the details (i) 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. (ii) Counting the number of essentially different propositions of n statements, and showing that the problem is equivalent to coloring the vertices of a hypercube. (iii) Counting finite automata and certain binary matrices. (iv) Counting graphs in statistical mechanics. There are certainly more which have not been mentioned. Hence we can conclude that Pólya’s Theory is one of the most powerful and useful tools in counting symmetries. ACKNOWLEDGEMENTS The authors thank the readers of European Journal of Pure and Applied Mathematics, for making our journal successful. References [1] A. N. Bjørge. Counting and Coloring with Symmetry, M.Sc Thesis, NTNU, May, 2009. [2] N. G. D. Bruijn. Counting and Enumeration, Pólya’s theory of counting, page 144-183, 1964. [3] P. Fleischmann. Groups and Symmetries, Institute of Mathematics and Statistics, Univer- sity of Kent at Canterbury, U.K., 2011. REFERENCES 113 [4] Harary, Frank, Palmer, and M. Edgar. Graphical Enumeration, New York: Academic Press, 1973. [5] P. M. Neumann. A lemma that is not Burnside’s, The Mathematical Scientist 4(2): 133– 141, ISSN 0312-3685, MR562002, 1979. [6] F. Y. Tomakin. The Pólya Theory and Permutation Groups, Chamchuri Journal of Mathe- matics, Vol. 1(2), page 1-23, 2000. [7] A. Tucker. Applied Combinatorics, 4th Edition, John Wiley and Sons, New York. 2002 [8] V. C. Venkaiah, T. A. Gulliver. Quasi-cyclic codes over F13 and enumeration of defining polynomials, Journal of Discrete Algorithms, Vol. 16, Pages 249âĂŞ257. 2012.