Hi All, its been a long time again and I thought I would not be blogging again anytime soon. But recently, I came across what can arguably called one of the most powerful and beautiful theorem in Combinatorics, The Pólya Enumeration Theorem. When I started reading about it and applied it to solve certain enumeration problems I just couldn't stop but wonder this marvelously simple theorem. Maybe, had Gauss discovered it he would have called it 'The Remarkable Theorem in Combinatorics'.
Pólya's Enumeration Theorem's usefulness comes from its ability to solve a great many variety of counting problems which would otherwise be too hard to solve or would require a customized approach that give you insights for that particular problem but cannot be generalized to very many other class of problems. The theorem uses the fundamental concepts of Group Theory, especially the permutation groups.
After surfing through a lot of material in the web to clearly understand the theorem I stumbled upon the PDF titled '
' by Amanda Noel Bjorge. This PDF was easy to follow because it explains every step of all the proofs with examples which makes it easier for the reader to follow. Of course, you've got to have some understanding of basic group theory and this PDF takes it from there. Yet another material I found very useful is
Now one may ask, If I have this PDF what is the point in creating a post about the same theorem? After all am an amateur and what more could I possibly add to an already well written thesis? Well, most of all the files available on the internet seems to explain the theorem in a more academic way. What I intend to do is to present the theorem to myself and maybe, add a few things which a casual google search may not reveal. So I suggest one should first read the file above for it will make following this post a lot easier and interesting.
To start with, I assume you've developed an understanding about the permutation groups and their corresponding pattern index. In particular, the
is extremely interesting and required a bit of thought before I completely understood it. The four basic permutation groups that appear frequently in counting problems are the Symmetric group, the Alternating group, the Cyclic group and the Dihedral group. Of these, the most easiest to understand are the last two. Mainly because they have a geometric description and can be visualized as placing beads or balls in a regular n-gon.
So when the question is about n-bead necklace discounting rotational symmetries, you understand that the answer has to do with Cyclic group and when it is about discounting both rotational and reflectional symmetries, you use the dihedral group.
To begin with, let's look at a simple example:
Example 1: How many 4-bead necklaces can formed with $m$ different colored beads discounting rotational symmetries?
Strictly speaking (or blogging), we don't need Pólya's Enumeration Theorem to find this. Burnside's Lemma will suffice. To solve this we first need the
cycle index of the Cyclic group of degree 4, conventionally denoted as $Z_{C_4}$.
$Z_{C_4}(x_1,x_2,x_3,x_4)=\frac{1}{4}(x_1^4+x_2^2+2x_4)$
We substitute $m$ for all $x_i$'s, which gives us, $Z_{C_4}(m,m,m,m)=\frac{1}{4}(m^4+m^2+2m)$
Say you have three different colored beads, substitute $m =3$ in the above expression and you will have $Z_{C_4}(3,3,3,3)=24$
Example 2: But what if I have one White bead, one Black bead and two Red beads and I want the number of 4-bead necklaces discounting rotational symmetries?
Here's where Pólya comes to the rescue. Plainly, the theorem says let $x_i=W^i+B^i+R^i$ and the coefficient of $WBR^2$ will give you the required answer. With a little help from Mathematica, we find
$Z_{C_4}(W+B+R, W^2+B^2+R^2, W^3+B^3+R^3, W^4+B^4+R^4)=B^4 + B^3 R + 2 B^2 R^2 + B R^3 + R^4 + B^3 W + 3 B^2 R W +$
$3 B R^2 W + R^3 W + 2 B^2 W^2 + 3 B R W^2 + 2 R^2 W^2 + B W^3 +
R W^3 + W^4$
Hence you can form $3$ 4-bead necklaces with the above restrictions. Though the theorem doesn't show how these three necklaces will be, with little thought we find them to be
brww, bwrw and
rbww. Note that the first and third arrangements are different as you cannot transform one into the other using rotations.
The same logic applies to the Dihedral group as well. Just find the
cycle index of the Dihedral group and follow the same procedure.
But what of the Symmetric and Alternating groups? We visualized the Cyclic and Dihedral groups with n-gons and applied them to n-bead necklaces. Well, I cannot find an equivalent way for visualizing the Symmetric and Alternating groups. But as for application, we can use the Symmetric groups in n-ball Urns. Both these groups helps us in solving urn problems where order doesn't matter.
Example 3: Say if we have 4 Urns and balls of $m$ different colors. In how many ways can you put one ball in each urn?
Now if the order matters, then this is one the most elementary questions in Combinatorics. Each urn has $m$ choices. Hence the answer is $m^4$. But the Symmetric group doesn't take order into account. So Let's see what Burnside's Lemma gives. We first need
$Z_{S_4}$.
$Z_{S_4}(x_1,x_2,x_3,x_4)=\frac{1}{24}(x_1^4+6x_1^2x_2+3x_2^2+8x_1x_3+6x_4)$
One could easily see that $Z_{S_4}(m,m,m,m)=(m^4+6m^3+11m^2+6m)/24$. For $m=3$, this gives $Z_{S_4}(3,3,3,3)=15$
Let's finish applying the Pólya's Enumeration theorem with three colors - White, Black and Red.
$Z_{S_4}(W+B+R, W^2+B^2+R^2, W^3+B^3+R^3, W^4+B^4+R^4)=B^4 + B^3 R + B^2 R^2 + B R^3 + R^4 + B^3 W + B^2 R W +$
$B R^2 W +R^3 W + B^2 W^2 + B R W^2 + R^2 W^2 + B W^3 + R W^3 + W^4$
These are the 15 combinations that we got from Burnside's Lemma. Note that
bbbr and
brbb are different when you take order into account whereas they are counted as same when order doesn't matter.
Now you maybe tempted to disregard Symmetric groups as uninteresting in Pólya's Enumeration theorem. But they come in a remarkable fashion when we try to understand the Alternating groups. The 'definition' of Alternating groups, which am about to give, is one of the high points of this discussion. In fact, I cannot find any material in the internet which clearly spells this application.
Example 4: Let's take same 4-urn problem. But now we want is the number of ways you can put one ball in each urn such that no urns have balls of the same color?
Clearly, if you have 4 urns and only three different colored balls, you cannot do it. But if you have 4 different colored balls, you can do it in 1 way. In fact, the answer to the question is too simple. Its $\binom{m}{4}$ when you have $m$ different colored balls. Let's see whether Burnside's Lemma gives the same answer. But first we need the cycle index. But of what? The Alternating group? The Symmetric group? No. Its the difference between the cycle index of the Alternating group and the Symmetric group.
Equation (14) of the PDF gives a succinct way of calculating this.
$Z_{A_n}-Z_{S_n}=Z_{S_n}(x_1,-x_2,x_3,-x_4,...)$, which we will denote by $Z_{-S_n}(x_1,x_2,x_3,x_4,...)$ for convenience. Hence we see that the Alternating group comes in a disguised form to solve a special class of constraint namely 'no two are alike'.
$Z_{A_4}-Z_{S_4}(x_1,x_2,x_3,x_4)=Z_{S_4}(x_1,-x_2,x_3,-x_4)=Z_{-S_4}(x_1,x_2,x_3,x_4)=\frac{1}{24}(x_1^4-6x_1^2x_2+3x_2^2+8x_1x_3-6x_4)$
So in case of $m$ colors, we have $Z_{S_4}(m,-m,m,-m)=Z_{-S_4}(m,m,m,m)=(m^4-6m^3+11m^2-6m)/24=\binom{m}{4}$
Note that $Z_{-S_4}(m,m,m,m)=0$ for $m<4$.
Pólya's Enumeration Theorem for the same gives,
$Z_{-S_4}(x_1,x_2,x_3,x_4)=B G R W + B G R Y + B G W Y + B R W Y + G R W Y$, where $x_i=W^i+B^i+R^i+G^i+Y^i$.
We have used five colors for this example because using anything less than four colors will only give us $0$.
Frankly, we don't see very good use of the last example as a source of solving problems. But I see the power of Symmetric and Alternating polynomials are apparent when we start using compositions of the permutation groups. See Example 6.1 and Figure 8 in the PDF to see what I mean.
The same problem also gives us further scope to understand our notion of the Alternating group. In the said Example the author has used the Symmetric group because he was looking for the number of arrangements of 2 necklaces without regard to order. Hence the three arrangements are {
bbbb, wwbb}, {
bbbb, wbwb}, and {
bwbb, bwbb}. The third arrangement repeats the same necklace twice. But what if we only want the arrangements where no two necklaces are alike. Here we would be using our idea of Alternating group along with the Symmetric group.
Using $Z_{-S_2}$ and $Z_{C_4}$ we get,
$Z_{-S_2[C_4]}(W+B,...,W^8+B^8)=B^7 W + 2 B^6 W^2 + 3 B^5 W^3 + 3 B^4 W^4 + 3 B^3 W^5 + 2 B^2 W^6 + B W^7$
Now we see that, of the 15 arrangements of 2 necklaces each with 4 beads, there are 2 with a total combination of 6 black beads and 2 white beads such that the two necklaces are different from each other.
To sum up the permuatation groups, we give the following:
- Cyclic group: Discounts rotational symmetry.
- Dihedral group: Discounts rotational and relfectional symmetry.
- Symmetric group: Arrangements not taking order into account.
- Alternating group: Arrangements not taking order into account and no two patterns are alike.
We'll continue with the other applications of the theorem in
this post. Write ya later.
Until then
Yours Aye
Me
