6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Look up Polyá Counting or Burnsides Lemma. $\endgroup$ – utdiscant Dec 22 '12 at 7:11
  • $\begingroup$ Okay I will but I was looking for something simple. I am only in high school. $\endgroup$ – Noel Dec 22 '12 at 13:32
  • $\begingroup$ 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. :) $\endgroup$ – Gyu Eun Lee Dec 22 '12 at 23:31
2
$\begingroup$

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.$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Noel Dec 24 '12 at 16:52
  • $\begingroup$ @Noel I think his solution is correct, but you are looking for an elemental proof. Without algebra. I will try to add one later this day. Still working on this one. $\endgroup$ – thetha Aug 2 '17 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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