Polya's Counting Theory

In the problem of counting, the biggest headache is to deduplicate equivalent cases. The simplest one among them is calculating ways of combination of elements out of elements, we first take out elements for permutation, where there're totally ways to do so, then we deduplicate the permutation of these elements and there're ways to combine them. However, going any further leads us to complete chaos, seemingly every concrete problem has its dedicated method of deduplication, depending on one's IQ to come up with.

Luckily, in many problem, equivalent cases can be seen as being connected by certain group structure. For example, in the problem of counting different schemes of coloring a necklace with beads, which is free to rotate, equivalent coloring schemes are tied by rotation operations, which form the group . Likewise, in the problem of coloring a bracelet with beads, which is free to rotate and flip, equivalent coloring schemes are tied by dihedral group . In the problem of counting molecules formed by substuting hydrogen atoms (H) with to halogen atoms (F, Cl, Br, I, At) in methane molecule (CH₄), the atoms can be seen as vertices of a regular tetrahedron, and molecules that coincide with each other after rotations of tetrahedron governed by other are undoubtedly the same.

In this text, for the problems with group structures tying the equivalent cases, we will see how we can utilize the embedded group's property to deduplicate equivalent cases and solve the problem effectively and elegantly, with Burnside's lemma and Polya's counting theory.

Burnside's lemma

The essence of counting with group is to think about the capability of a group to generate equivalent elements in concrete problems: the under 's group action on , defines what kind of operations generate equivalent elements, and by the orbit-stabilizer theorem, 's acting on generate disjoint subset of , elements in each are equivalent and should be deduplicated to , so the number of orbits is what we want.

The Burnside's lemma ¹ shows us a way of counting orbits as:

Where is the stabilizer subgroup of , and is the subset of fixed by group element . To count orbits, we might either iterate though and do summation of the size of stabilizer subgroup corresponding to each one of them, or iterate through and do the summation of the number of elements in fixed by each one of them.

To prove, let's consider the side of summation of s, partition the summands by disjoint orbits of , and we get:

And for summand , for each , . Consider a map defined by , since it is a group homorphism. And for the equation , multiply by on the left and then on the right we get , so and is a group isomorphism. So and , we get:

Then, imagine how we can list elements such that for the group action : we can iterate through and for each there're of them, or instead we can iterate though and for each there're of them. Either ways yield the same amount of elements so there're of them. Dividing each side by yields the final equation and we conclude the proof.

Halogenation of methane

Let's think about the problem of halogenation of methane we came up with in the prologue. So we are to substitute to hydrogen atoms, which lie on the vertices of a regular tetradron with a carbon atom (C) lying at its center, with halogen atoms (F, Cl, Br, I, At) ², deduplicating the cases that modules coinciding with each other after rotations of tetratedron governed by .

Let's iterate though elements in and see what kind of molecules would be fixed by each element. In fact, elements in can be categorized into identity, product of two transpositions, or -cycles. Each one out of the atoms surrounding the carbon atom might be one of these atoms: H, F, Cl, Br, I, or At. And let's talk about them case by case:

1. For identity, we are free to substitute atoms, and there're ways to substitute.
2. For two transpositions, the atoms in each transposition must be the same, and there're two transpositions, so there're ways to substitute.
3. For -cycles, the atoms inside the cycle must be the same, the atom outside the cycle is free to substitute, so there're ways to substitute.

Finally, given that there're identity, two transpositions, and -cycles. By the Burnside's lemma, there're totally different molecules of them. Noted that the case of methane is comprised and should be eliminated, so there're finally different molecules formed by substituting to hydrogen atoms with halogen atoms in a methane.

Alternatively, you can also count by halogenating the methane with to halogen atoms respectively:

1. halogen atom: .
2. halogen atoms: .
3. halogen atoms: .
4. halogen atoms: .

Counting in this way yields different molecules in total, which matches our previous calculation well.

Necklace and bracelet

Let's think about the problem of counting distinct coloring schemes of necklace or bracelet with beads using colors. The necklaces is free to rotate and governed by , while the bracelet is free to rotate and flip and governed by .

Let's label the beads in necklace bracelet with letters so that we can study them with permutation groups. Under such setting, the necklace's group can be seen to be generated by rotation and the bracelet's group can be seen to be generated by rotation and flipping such that .

It won't be hard to verify that . By we define a group action of 's acting on the letters of beads. Consider the equation , we have and , which means the equation holds iff divides , so the stabilizer subgroup of each letter is trivial. And consider 's acting on , it maps to , to , and so on, which means and are in the same cycle in when there's some . By the orbit-stabilizer theorem, since only the identity fixes every letters, the length of cycle in containing must be . So we can easily draw a conclusion that if , is made up of disjoint -cycles.

For coloring schemes that would like to be fixed by , beads inside each disjoint cycle should have the same color. From the discussion above we know there're disjoint cycles in , and each fixes coloring schemes.

When applying the Burnside's lemma, besides summing over all integers between and , inspecting their greatest common divisor with , we may also partition the summands by their greatest common divisors ³: a greatest common divisor must also be a factor of , and an integer such that must also be multiple of . However, if then instead of , so in order for to hold for , there must be and there're of them. So finally we have:

Where counts distinct coloring schemes of necklace with beads using colors.

Now let's take the flipping operation of the bracelet into consideration. More exactly, we need to consider about what coloring schemes are fixed by and . We know contains only transpositions while is not so intuitive, but by we know also contains only transpositions, and we can treat as a case of when up to structure of cycles. It won't be hard to verify there're and , consider the equation , we have and . So the points that will be fixed by depends completely on the parities of and . When is even, the is fixed by . When are even or odd at the same time, is also fixed by . Besides the points that are fixed by , all other points are inside transpositions.

So when is even, of the s fix letters and have transpositions, of the s fix no letter and have transpositions. When is odd, all of the s fix letter at either or and have transpositions. Finally by the Burnside's lemma we have:

Where counts distinct coloring schemes of bracelet with beads using colors.

Polya's counting theory

For the problem of counting coloring schemes of necklace or bracelet, let's calibrate it into counting coloring schemes of necklace or bracelet with beads where of them are painted red and of them are painted blue, can you find the result quickly?

We've already done some reasoning on necklace or bracelet with beads above, where coloring schemes are inside set and acted on by or . For our problem of counting coloring schemes of necklace or bracelets with red beads and blue beads, we just need to construct another set of these necklaces or bracelets, let or act on and see what happens.

Just as you've noticed, and we must have analyzed all cases of when we analyze , although the analysis of is inseparable from the output of and . Is there a way to preserve some details of finer granularities in the counting of , so that we can combine some of them with ease and form the counting for some ?

Having been aware of such problem, Polya combined the concept of generating function in combinatorics, which is best known for its capability of encoding events algebraically, with the Burnside's lemma, which provides an efficient technique for deduplication when there's some group imbued in the problem. We will see how do they work in this text.

Skimming of the generating function

Since this text is dedicated to Polya's counting theory, we will just demonstrate the idea and mechanism of generating functions briefly and intuitively, and then dive into our topic of Polya's counting theory soon.

We are all familiar with the binomial theorem that . An intuitive interpretation is to treat the expansion of as multiplication of of s, it's obvious that each will contribute a factor of either or to the expanded terms, and if of them contribute , the rest of them must contribute , combining into the term , and there're such cases.

Conversely, encodes every events of taking of and of to form the term , allowing us to study the events algebraically. For example, when we think of the term is formed by taking a term from and a term from , there can only be either or , so .

Consider another problem, assume there's sufficient pennies of dollars, how many ways are there to combine into dollars? One can solve this problem by using dynamic programming: in order to get rid of duplicate countings, (e.g. and then ) we first count the ways of combining into dollars by using only dollars as , and then count the ways of combining into dollars by using and dollars as , and finally count the ways of combining dollars by using dollars as , and there's .

This can also be done using generating functions: let counts the ways of combining into dollars, so the series encodes the combinations using dollars, encodes the combinations using dollars, and encodes the combinations using dollars. Since the terms with rank higher than will not contribute to the coefficent of , we just omit them and expand them into:

So in this way, we also get there're ways to combine sufficient pennies of dollars into dollars.

In short, generating function exploits the equivalence between the set operations of events and the algebraic operations of terms, allowing us to encode and manipulate combinatorical problems algebraically.

Polya's counting theory and its proof

The Polya's counting theory focus on such a scenarios: given a set of colors , assign these colors to letters whose coloring scheme equivalence is governed by permutation group .

The target to be deduplicated by is the set of all coloring schemes using , and obviously the number of each coloring scheme can be generated by .

Since merely permutating the color assignments will not change the number of each color, so coloring schemes are in the same orbit under only if their numbers of each color used are the same. Let identify the type of coloring schemes where each color is assigned to letters, and be the set of coloring schemes of type fixed by . According to the Burnside's lemma, after deduplication there are totally coloring schemes of type .

On the other hand, for each permutation , it only fixes the coloring schemes that have the same color in each disjoint cycle. Let the amount of cycle of length in be , obviously the coloring schemes that will be fixed by can be generated by:

Define the cycle index polynomial of as:

By combining with the reasonings above, we can conclude the amount of each coloring scheme after deduplication can be evaluated by:

So we can see the Polya's counting theory is actually an expansion of the Burnside's lemma to generating functions, with terms being the types of coloring scheme and the coefficients being the countings. It's also obvious that once we have determined which permutation group defines the coloring scheme equivalence for the specific problem, we can reuse the cycle index polynomial for any set of colors .

Halogenation of methane remixed

As a warmup, let's apply the Polya's counting theory to the problem of counting halogenation of methane. It won't be hard to find the cycle index polynomial of is , and the set of colors for the problem is . How can we count molecules of type CHX₂Y (X Y)?

First let's estimate how many terms are there if we expand the cycle index polynomial directly. The distinct terms can be seen as letting act on the ordered -tuples of colors so that we deduplicate equivalent tuples of colors. The types of permutations in are:

1. There's single identity in allowing us to choose color in each component of tuple freely, and there're ways to do so.
2. There're of transpositions in allowing us to choose the same color in the components covered by the transpositions but freely out of it, and there're ways to do so.
3. There're of two transpositions in allowing us to choose the same color in the components covered by each transposition, and there're ways to do so.
4. There're of -cycles in allowing us to choose the same color in the components covered by cycle and freely out of it, and there're ways to do so.
5. There're of -cycles in (fix and permutate ), allowing us to choose only the same color in each component and there're ways to do so.

So we can finally deduce that there'll be terms in the expanded cycle index polynomial, rendering it super uneconomical to do so. However, it won't be hard to see that the cycle index polynomial is symmetric, so the coefficient corresponding to CHF₂Cl and CHBr₂I must be the same. And once we've found out the number of modules of CHF₂Cl, we can multiply it by , which is the number of -permutations of atoms other than hydrogen, yielding us the final result.

So we would like to extract the coefficient of corresponding to CHF₂Cl from the expanded cycle index polynomial. However each corresponds to color terms, we may be familiar with binomial theorem of those with two terms, but clearly those with more terms clearly can't be handled so easily. We need to "upgrade" our binomial theorem before getting on.

Let's start by thinking about those with three terms:

For those with more than three terms, under the same rationale we can boldly assume that . It won't be hard to show the assumption is true on . And assume it is true for every cases up to , then for the case of there's:

By now, we've extended the binomial to more than three terms (which is called the multinomial theorem canonically) and proved it. In our problem, this is undoubtedly simpler and more useful for extracting coefficient of certain term.

So the coefficient of would be , and there're totally distinct molecules in the form of CHX₂Y. Despite the result's being simple, we've walked though the methodology of applying Polya's counting theory to concrete counting problems.

Necklace and bracelet remixed

Let's consider counting the necklaces or bracelets of beads where of them are painted red and of them are painted black.

First, inheriting the former analysis on and 's elements, it won't be hard to see the cycle index polynomials corresponding to and are:

(It's recommended to revise the section Necklace and bracelet and compare it with current section, if you've already forgotten about the details, especially on how we analyzed the cycle structures of each element.)

Then, with the set of colors being , let's see how we can extract the coefficient of from the cycle index polynomial . Noted that for each , we have , rendering is contained in only if divides both and , and of course must divide . So the coefficient of in the expanded cycle index polynomial would be:

This is how we count distinct necklaces with red beads and black beads.

Finally, let's consider the extraction of from . The portion of has been analyzed above, so we just need to focus on the portion consisting of , which depends on the parities of and obviously.

In order for to be even, it's either the case that both and are odd, or that both and are even. When both and are odd, it's impossible for to be contained in . And for , must contribute due to the parity constrain. So the coefficient of in the remaining portions must be . When both and are even and non-zero, is contained in both and . And for , must contribute due to the parity constrain this time, and the coefficient of in the remaining portion must be .

Specially, when is even but exactly one of or is zero, it's intuitive that there's exactly monochrome bracelet. And let's check whether it will match up with our cycle index polynomials: without losing generality, assume is zero, so . Noted that each summand enumerates number of the cases of (by ) for . The summation has covered all the cases of , and must therefore be evaluated to . So we have . For the remaining portions in the cycle index polynomial, is contained in both and . For , must contribute only this time, and we have . So the coefficient of is evaluated to . When both and are zero, the problem is ill-formed and evaluated to zero.

In order for to be odd, it's either the case that is odd and is even, or that is even and is odd. Let's assume it is the former case, then for , must contribute the term, and the coefficient must be . The latter case can be analyzed analogously and the coefficient will be then.

Specially, when is odd and the even one of and is zero, assume it is , we have , the coefficient of is also evaluated to .

The coefficient of regarding the nullities and parities of and is listed as below:

This is how we count distinct bracelets with red beads and black beads.

Cycle index polynomials of symmetric and alternating groups

Combinatorical problems with permutation governing the equivalent cases are common (e.g. counting terms in expanded polynomial, counting non-isomorphic graphs), and sometimes it's useful to involve Polya's counting theory in these problems. So in this section, let's derive the cycle index polynomial of symmetric group and alternating group .

Consider how many ways can we choose an element with condition : we can first permutate these letters, and add brackets surrounding every element for the first elements, add brackets surrounding every elements for the elements just after them, etc. For example, to choose an element with condition , we first permutate the elements, and assume one of the permutations is , adding brackets in the way described above yields . However, under such scheme, apparently there're elements equivalent to created from other permutations, like and . We need to know all the cases of our overcounting in order to deduplicate them.

For every element chosen under condition represented as disjoint cycles: shifting elements circularly in each cycle does not affect its identity, for each -cycle, there're equivalent cases generated by full permutation on letters, overcounting them for times totally. Reordering the disjoint cycles does not affect its identity either, and thanks to our way of adding brackets orderly, it's impossible for case like to come, although for the of -cycles, there're equivalent cases generated by the full permutation on letters, overcounting them for times totally. So far, there're no other cases of overcounting. So the cycle index polynomial will be:

For choosing element with condition , while being an even permutation it must also fulfil , and we just need to find a way to filter out the combinations of s that falls into odd permutations, which can be done by multiplying each term by a -or- term . So the cycle index polynomial will be:

Here concludes the derivation of cycle index polynomials of symmetric and alternating groups.

Conclusion

In this text, we introduce a group theory based counting method, utilizing the trait of group's acting on arbitrary set.

The method is applicable to problems with group defining the equivalence relations between distinct cases, that the cases are interchangable under group action. The orbit-stabilizer theorem tells us the group will partition the set of cases into disjoint orbits, turning the problem into counting orbits radically.

Burnside's lemma tells us to count orbits of partitioned by , for each , you will just find out the subset of elements fixed by , and average their size by . To prove, we first do the summation of the size of stabilizer subgroup over . Since , by applying the orbit-stabilizer theorem, the summation of over each distinct orbit in adds up to , so the total summation overcounts for times. Then we discover that the summation of over and the summation of over coincide, since they're just different ways of counting identities in the form of . By putting these two pieces together, we derive the Burnside's lemma, enabling us to count the orbits efficiently.

Polya's counting theory is the combination of Burnside's lemma in group theory and generating functions in combinatorics. In the problems of counting coloring schemes, whose symmetries can be defined by a permutation group, with the theory we can preserve the details of the number of each color used while counting them. Since merely permutating the colors in a coloring scheme does not change the number of colors used, two coloring schemes are in the same orbit only if the number of colors used are the same. And inspired by the concept of generating functions, it may be viable to encode counting result as polynomials, where the number of distinct coloring schemes are encoded as the coefficient, and the number of each color used as the variable. Due to the Burnside's lemma, to count the coloring schemes, we will need to find out how many coloring schemes are fixed by each permutation. A permutation fixes a coloring scheme when colors in each of its disjoint cycles are the same. Due to the principles of generating functions, we can generate coloring schemes fixed by each permutation, by multiplying together the events that colors used in each disjoint cycles are the same. Doing so eventually turns the problem into counting permutations by their number of cycles of each length. By putting all these pieces together, we define the cycle index polynomial of permutation group, which is applicable to problems with different candidate colors but the same symmetries.

We also come up with differnt examples in this text, which can be used as reference of applying Burnside's lemma and Polya's counting theory.