Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Claudia wants to use 8 indistinguishable red beads and 32 indistinguishable blue beads to make a necklace such that there are at least 2 blue beads between any red beads. In how many ways can she do this? This is one of the unsolved problem in the book 'A Path to Combinatorics for Undergraduates' by Titu Andreescu and Zuming Feng. My approach: Denote blue by b, red by r. Then we create elements of the form 'brb'(8 elements), and 16'b's. We place the 16 'b's arounds a circle with a space in between them and we choose from those 16 available places 8 for the 'brb' and divide the whole be 2 to account for rotational symmetry.

I am not sure whether I am fully accounting for the rotational symmetry and the fact that the beads are indistinguishable. Not Homework. Trying to learn. Thank you.

share|improve this question
    
Look up Polyá Counting or Burnsides Lemma. –  utdiscant Dec 22 '12 at 7:11
    
Okay I will but I was looking for something simple. I am only in high school. –  Noel Dec 22 '12 at 13:32
    
Sorry - irrelevant - but I laughed a little. The book's called "A Path to Combinatorics for Undergraduates," it's natural that you'll receive undergraduate tools here, regardless of what level of schooling you're actually at. :) –  kigen Dec 22 '12 at 23:31

1 Answer 1

This problem can indeed be solved by Polya counting. First place the eight red beads along a circle, leaving some kind of space between them for the blue beads. Now place two blue beads between each adjacent pair of red beads as well as an empty slot that will be filled later. That leaves $32-2*8 = 16$ blue beads. Now the empty slots may be filled by any number of blue beads as long as there are $16$ blue beads in total. This means that the blue beads going into the eight slots have generating function $$ f(z) = \frac{1}{1-z}.$$ What we have in fact is that the generating function is $$g(z) = 1 + z + z^2 + z^3 + \cdots z^{15} + z^{16}$$ but we shall see that we can use $f(z)$ in place of $g(z)$ with no overcounting.

Now the eight slots are being permuted by $C_8$, the cylic group of order $8.$ The cycle index of the cyclic group $C_n$ is $$ Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d}$$ so that $Z(C_8)$ is $$ Z(C_8) = \frac{1}{8} \left(a_1^8 + a_2^4 + 2 a_4^2 + 4 a_8 \right).$$ It follows that the number of orbits or necklace configurations is given by $$ [z^{16}] Z(C_8)_{a_1=f(z); a_2=f(z^2); a_4=f(z^4); a_8=f(z^8)}$$ which is $$ [z^{16}] \frac{1}{8} \left(\frac{1}{(1-z)^8} + \frac{1}{(1-z^2)^4} + 2 \frac{1}{(1-z^4)^2} + 4 \frac{1}{(1-z^8)} \right).$$ Finally recall that $$ [z^n] \frac{1}{(1-z)^q} = \binom{n+q-1}{q-1}$$ so that the value of the coefficient of $z^{16}$ is $$\frac{1}{8} \left( \binom{16+7}{7} +\binom{8+3}{3} +2\binom{4+1}{1} +4\binom{2+0}{0}\right) = 30667.$$ In the case where instead of the cyclic group $C_n$ the dihedral group $D_n$ is acting on the slots on the necklace (i.e., the symmetry includes reflections) the cycle index is given by $$ Z(D_n) = \frac{1}{2} Z(C_n) + \frac{1}{4} \left( a_1^2 a_2^{(n-2)/2} + a_2^{n/2}\right)$$ so that the answer becomes $$ \frac{1}{2} 30667 + \frac{1}{4} [z^{16}] \left( \frac{1}{(1-z)^2}\frac{1}{(1-z^2)^3} + \frac{1}{(1-z^2)^4}\right) = 15581.$$

share|improve this answer
    
I am sure your solution to the problem is correct, but frankly I was looking for something much simpler. The problem is from a chapter on 'Combinations', in fact there is no mention of Polya counting anywhere in the book. It would also be very helpful if you could point out where I went wrong with my answer of (16 Choose 2)/2. –  Noel Dec 24 '12 at 16:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.