Pólya’s Inventory Theorem

You may have guessed we can do more, otherwise we would have simply written \(x\) instead of each \(x_i\) in the cycle index polynomial!

We can now easily solve our original problem, so let’s make it harder. How many 10-bead necklaces can you make out of 2 red beads, 3 green beads and 5 blue beads?

To answer questions like these, we borrow techniques from generating functions. First we define weights for each colour denoted by \(w()\).

We might pick \(w(R) = x, w(G) = w(B) = 1\). The weight of a colouring \(\phi:X\rightarrow C\) is the product of the weights of each bead:

\[ w(\phi) = \prod_{x\in X} w(\phi(x)) . \]

For example, \(w(RGBRGB) = x^2\), and more generally a colouring has exactly two red beads if and only if its weight is \(x^2\).

Colourings in the same orbit have the same weight, allowing us to define the weight of an orbit to be the weight of any one of its members.

We define the pattern inventory \(I\) to be the sum of the weighted orbits:

\[ I = \sum_{\Delta \in S} w(\Delta) \]

where \(S\) is the set of all orbits. In our example, the coefficient of \(x^2\) would then be the number of necklaces with exactly two red beads.

Exercise: Prove the Weighted Burnside Lemma:

\[ I = \frac{1}{|G|} \sum_{g\in G} \sum w(\alpha) [{\alpha\in\mathrm{Fix}_g(\Omega)}] \]

This implies:

Theorem: (Pólya’s Inventory Theorem)

\[ I = P_{(G,X)}(p_1,...,p_n) \]

where \(|X| = n\) and \(p_k = \sum_{c\in C} w(c)^k \) (the \(k\)th power sum of the weights).

In particular, for our problem, we compute \(P\), the cyclic index polynomial of the dihedral group of order 20, and choose the weights \(w(R) = x, w(G) = y, w(B) = z\). Then we want the coefficient of \(x^2 y^3 z^5\) in

\[ \array{ I = P(x+y+z, ..., x^{10} + y^{10} + z^{10}) \\ = 20^{-1} ((x+y+z)^{10} + (x^2+y^2+z^2)^5 + 4 (x^5+y^5+z^5)^2 + 4 (x^{10}+y^{10}+z^{10}) \\ + 5 (x+y+z)^2 (x^2+y^2+z^2)^4 + 5 (x^2+y^2+z^2)^5 ) } \]

Thus the answer is:

\[ 20^{-1} \left( \binom{10}{2,3,5} + 5\cdot 2\cdot\binom{4}{1,1,2} \right) = 132 \]

Ben Lynn blynn@cs.stanford.edu 💡