18. 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 of counting 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 S₉ 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 S₉ 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 G_n.

What are the elements of G_n?

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 blocks of size 2 for n odd, with n such reflections; and 2 fixed and (n-2)/ blocks of size 2 for n even with n/2 of such reflections, and n/2 other reflections having all blocks of size 2 in the even case.

The identity has all cycles of length 1, while other rotations have either one cycle, or if n is not a prime n/k cycles each of size k for each divisor k of n. There are a total of n-1 rotations, not including the identity.

Thus the group of symmetries, G_n here, has 2n elements.

Suppose for example n=10; then there are the following congruence classes of group elements

1¹⁰ the identity

2⁵ 5 reflections

1²2⁴ 5 reflections

5² rotations by 2 4 6 and 8

10 rotations by 1 3 7 and 9.

2⁵ rotation by 5

There are a total of 20 group elements.

The rotations form a normal subgroup, having 10 elements.

Our formula for the number of patterns of colorings will therefore get contributions from 5 distinct terms depending only on the cycle structure, and these terms will have weights 1/20 for the identity, 4/20 for one 10 cycle, 4/20 for two 5 cycles, 5/20 for 5 reflections with structure 2⁴1², and 6/20 for 5 rotations and a reflection with structure 2⁵.

And how many colorings will there be that are stabilized by each of these?

The identity stabilizes every coloring and these can be described by the function (x₁*x₂* . . . *x_n) where x_j indicates the color of the j-th bead and the sum is over all possible values for each of the x’s.

The 10 cycle only stabilizes the constant color which can be described by x₁¹⁰.

Two 5 cycles can only stabilize colorings that are constant on the cycles, which have the form x_a⁵x_b⁵.

The other cycle structures stabilize colorings that have the form x_ax_bx_c²x_d²x_e²x_f², and x_z². . . x_e² respectively.

All sums here are taken over all the possible values of each x_j here.

And what are the x_j?

To keep track of these, if the j-th vertex is colored with color s, let x_j =t_s

Our sum then becomes

(1/20) (t_s)¹⁰ + (4/20)(t_s¹⁰) + (5/20)(t_s⁵)² + (5/20(t_s)²(t_s²)⁴ + (6/20)(t_s²)⁵

Now suppose we had seven colors for our beads and an unlimited number of each color and we want to count the number of patterns of colorings all together. Then we can set t^s =1 for each of 7 colors, and our sum becomes

7¹⁰/20 + 7/5 + 7²/4 + 7⁶/4 +3*7⁵/10,

and that is how many colorings there.

The fact that we have used variables t here instead of just counting 1’s means we can use the same formula to count how many colorings there are with say 3 red beads and the rest not red (or with any other arrangement of beads, or any similar question.

If there are to be exactly 3 red beads, then t_red must occur in our sum with power 3. That can happen only for the identity, and by the next to last term in which t_red appears in one of the first two terms and one of the second.

We can count the number of these patterns by finding the coefficient of t_red³ when we set all the variables for the other colors to 1

The coefficient of that term is then (1/20)C(10,3)6⁷ + (1/4)*C(2,1)*6*C(4,1)*6³ and that is the number of distinct patterns of necklaces having exactly 3 red beads. This number is 6⁸ + 2*6⁴.

3.Application to counting tree patterns.

We can also count the number of patterns of trees on n vertices this way, though our group here is the symmetric group on n symbols, and this group grows rapidly with n, the number of congruence classes grows fairly slowly.

To apply this you have to be able to count how many trees will be stabilized by each group element.

Again the identity will stabilize them all, and for each other congruence class you must count how large it is, divide that by the order of S_n and multiply by the number of trees stabilized by group elements in that class.

Typically you can choose any tree on the fixed points of the congruence class, then add on a leaf for each cycle to it. When cycles have the same length you get trees when one is added to the other (in any order), but when cycles have different lengths their vertices cannot be added to one another so as to maintain symmetry.

Thus, for example the cycle structure 1³2 3 on 8 vertices will stabilize trees that starting with 3 vertices have a pair of leaves added to any one of these and a triad of leaves added to another. There are 3¹*3*3 such trees stabilized by each such cycle structure, and there are C(8;3.3.2) such structures where this C(8;3,3,2) is the multinomial coefficient 8!/(3!3!2!) which counts the number of ways of picking out the tree vertices and pair and triad of leaves.

I am too lazy to sum up all such terms, for say, trees on 9 vertices, but it can be done quite easily, as many of the 30 cycle structures cannot be symmetries of trees at all, and each of the others allow computation of their contributions as done in the last paragraph.

By the way, this sort of counting, which which has applications to counting isomers in chemistry, is called Polya Theory in honor of one of its discoverers.

When counting tree patterns, bearing in mind that roughly n/e vertices will in general be leaves for large n, will not be unusual for two vertices to both be leaves

attached to the same vertex, and this means there is a symmetry between them. Thus the contributions from symmetries make a contribution here.

Often large structures have very little symmetry and the contribution from the identity term (total number of labeled patterns divided by the order of the symmetry group) is close to the number of patterns.

Exercises: 1. In this same example, how many colorings have exactly 2 red beads and 4 green beads with 7 colors all together?

2. Write out the general formula for necklaces of length 23 analogous to the one above for 10 with powers of sums of powers of t_s’s, and compute how many patterns of colorings there are all together for 5 colors of beads.

3. (extra credit) How many tree patterns are there with 7 vertices? Compute this directly and also by looking at all cycle structures in the symmetric group on 7 vertices, and counting the average number of trees stabilized by the group elements.