**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^{-1}A
= 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_{9} 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_{9 } by hand if you had to,
though the size of the group is in the hundreds of thousands.

** 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^{10
} the identity

2^{5 } 5 reflections

1^{2}2^{4} 5 reflections

5^{2} rotations by 2 4 6 and 8

10 rotations by 1 3 7 and 9.

2^{5}
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^{4}1^{2}, and 6/20 for
5 rotations and a reflection with structure 2^{5}.

** 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_{1}*x_{2}*
. . . *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_{1}^{10}.

Two 5 cycles can only stabilize colorings that
are constant on the cycles, which have the form x_{a}^{5}x_{b}^{5}.

The other cycle structures stabilize colorings
that have the form x_{a}x_{b}x_{c}^{2}x_{d}^{2}x_{e}^{2}x_{f}^{2},
and x_{z}^{2}.
. . x_{e}^{2} 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})^{10} + (4/20)(t_{s}^{10})
+ (5/20)(t_{s}^{5})^{2}
+ (5/20(t_{s})^{2}(t_{s}^{2})^{4}
+ (6/20)(t_{s}^{2})^{5}

^{ }

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^{10}/20 + 7/5 + 7^{2}/4^{ } + 7^{6}/4 +3*7^{5}/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}^{3}
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^{7} + (1/4)*C(2,1)*6*C(4,1)*6^{3 } and that is the number of distinct patterns
of necklaces having exactly 3 red beads. This number is 6^{8} + 2*6^{4}.

**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^{3}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^{1}*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.**