Colouring a necklace

How many ways there are of colouring the 11 beads of this necklace either red or green if reflections and rotations are considered to be identical?


The answer is 126.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Miles Koumouris
Dec 25, 2017

The Polya Enumeration Theorem tells us that the number of ways N N of colouring the beads can be found by obtaining the cycle index of the dihedral group D 11 D_{11} ; note that Z ( D n ) = 1 2 Z ( C n ) + { 1 2 a 1 a 2 n 1 2 if n 1 ( mod 2 ) 1 4 ( a 2 n 2 + a 1 2 a 2 n 2 2 ) if n 0 ( mod 2 ) , Z\left(D_n\right)=\dfrac 12Z\left(C_n\right)+\left\{ \begin{array}{lll} \dfrac 12a_1a_2^{\frac{n-1}{2}} & \hspace{0.5cm} & \text{if }\; n\equiv 1\;\; (\text{mod }2) \\ \dfrac 14\left(a_2^{\frac{n}{2}}+a_1^2a_2^{\frac{n-2}{2}}\right) & & \text{if }\; n\equiv 0\;\; (\text{mod }2), \end{array}\right. where C n C_n is the cyclic group, and Z ( C n ) = 1 n k n ϕ ( k ) a k n k . Z\left(C_n\right)=\dfrac 1n \sum_{k\mid n}\phi (k)a_k^{\frac nk}. Evaluating this sum at n = 11 n=11 and substituting a i = r i + g i a_i=r^i+g^i (to account for the two colours) yields the generating function Z ( D 11 ) [ r + g ] = r 11 + g 11 + r 10 g + r g 10 + 5 r 9 g 2 + 5 r 2 g 9 + 10 r 8 g 3 + 10 r 3 g 8 + 20 r 7 g 4 + 20 r 4 g 7 + 26 r 6 g 5 + 26 r 5 g 6 , Z\left(D_{11}\right)_{[r+g]}=r^{11}+g^{11}+r^{10}g+rg^{10}+5r^9g^2+5r^2g^9+10r^8g^3+10r^3g^8+20r^7g^4+20r^4g^7+26r^6g^5+26r^5g^6, and thus N = 1 + 1 + 1 + 1 + 5 + 5 + 10 + 10 + 20 + 20 + 26 + 26 = 126 . N=1+1+1+1+5+5+10+10+20+20+26+26=\boxed{126}.

Huh, didn't know of that. I just used Burnside's Lemma.

Sharky Kesa - 3 years, 5 months ago

Log in to reply

Well PET follows from Burnside's Lemma. It is after all a generalisation, so in a sense, I did exactly the same thing...

Miles Koumouris - 3 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...