22. Counting Patterns 1. Problem and General Result Suppose now we have a collection of objects and a group G of permutation symmetries, such as the Symmetric group, whose elements act on these objects. We want to know how many distinct patterns, of our objects there are, where two objects A and B have the same pattern if one of the symmetries say g carries A into B, so that B = gA holds. If we take a particular object A, some of the elements of G acting on A produce another object, and some leave it alone. we say that g leaves A alone if gA = A holds. The set of elements that leave A alone form a subgroup of G, which is called the stabilizer of A, which we will denote as S(A). If g is in the stabilizer of A then we have gA = A; otherwise gA is another object that has the same pattern as A has. The set of objects with the same pattern as A is called the orbit of A under action of the group G. The cardinality (size) of the stabilizer of A is the same as the cardinality of the stabilizer of every member of A’s orbit. To see this, let B be the member of A’s orbit with the largest stabilizer, and let g be a group element which takes B to A. We then have S(B) B = B, since every element of S(B) leaves B alone, and gS(B)B will be therefore be A. But B is g-1 A, so we have gS(B) g-1A = A which means gS(B)g-1 stabilizes A, for any A in the orbit of B; and this set has the same cardinality as S(B). (By the way, the stabilizer of A will therefore be a subgroup of G conjugate to S(B).) The set of group elements gS(B) is a coset of S(B) in G and as we have seen, has the same cardinality as S(B) and every one of these elements takes B into A. This means that there are at least |S(B)| group elements that take B into A, and this must hold for every member of the orbit of B. The size of the orbit of A (and of B) is then the number of cosets of S(B) in G. By Lagrange’s theorem we can deduce: (The size of the orbit of B)*|S(B)| = |G|. or in words, the size of the orbit of B is the order of G divided by the order of B’s stabilizer. What we have called a pattern is actually an orbit under the action of G. So our problem, that ofcounting patterns, is the problem of counting orbits of our objects under the action of G. Let’s denote the orbit of A under G as O(A). How do we do it? If we sum 1 for each of our objects, we will have the number of objects. Suppose instead we give a weight to each object: namely we sum over all A 1/|O(A)|. Then the total contribution from all the A in O(A) will be 1. This sum will therefore give us the number of orbits or patterns that we seek! And, by our previous observation, that the size of O(A) is the order of G divided by the order of the stabilizer of A, we find that the number of patterns or orbits will be the sum over all A of |S(A)|/|G|. Furthermore, the sum over all A of |SA)| is actually the number of pairs (object, group element) such as the group element stabilizes the object. We can count this number another way: it is the sum over all group elements g in G of the number of objects stabilized by g. This allows us to draw the following conclusion: The number of distinct patterns or orbits of a set of objects under the action of a group G is the sum over all group elements g of the number of objects stabilized by g, divided by the order of G. This number is the average over all group elements g of G of the number of objects stabilized by g. As we have noted, an orbit of our objects is a set of objects each pair of which is conjugate to one another. Suppose now we choose some function defined on our objects that takes the same value for each member of any conjugate pair. Such a function will be constant on any orbit. We can perform the argument just given without any modification for the sum over distinct patterns of the values of f on them, and deduce the same conclusion for such sums.The general result is: The sum of any orbit constant f over all patterns is the average over all group elements g of the sum of f over all patterns stabilized by g. Exercise: 1. Verify this claim by proving this statement using the arguments above on this sum.A nice feature of this result is that the computation of the average of the number of patterns or the sum of f over patterns stabilized by g will be the same for all g in the same conjugacy class. This implies that the number of distinct terms in this average will be at most the number of conjugacy classes for G. As we have seen, for S9 there are only 30 parttitions of n, and the number of conjugacy classes in the this group is the number of partitions, so that you could compute this sum of S9 by hand if you had to, though the size of the group is in the hundreds of thousands. 3. Application. Counting Necklaces of n colored beads Suppose we have a hoard of beads that are each one of k distinct colors, and wish to make a necklace consisting of n of these beads. How many different ways of doing this are there? Here we mean that two necklaces are different if we cannot find a way of placing one on top of the other so that the colors of each bead on top and the bead underneath it is the same at each position. We have here a permutation group of symmetries, call it Gn. What are the elements of Gn? If we name the beads starting at any place on the necklace and going in some direction, as 1, 2, . . . , n, we can perform a cyclic permutation of these beads; as described by 2.3, 4, . . ., n, 1, and any product of these permutations. We call these rotations. We can also reflect the necklace without changing its structure. If n is odd, any reflection will keep one vertex fixed, and take each vertex a distance j from that vertex to the vertex a distance j from it in the opposite direction. If n is even, there are reflections that keep two opposite vertices fixed, and those that those that keep points on the string of the necklace fixed, reversing the positions of all pairs of beads that are equidistant from any such point. The cycle structure of the reflections is then 1 and (n-1)/2 …