4
$\begingroup$

There are 8 red beads and 32 blue beads. How many necklaces (which can be rotated) are there such that between any two red beads there are at least 2 blue beads.

I reduced the problem to finding the set of solutions of

$$x_1+ x_2 +\cdots +x_{8} = 16$$

Where no 8-tuple is a cyclic permutation of the other. But I really can't see how to make any further progress.

$\endgroup$
  • $\begingroup$ At this point you should apply Burnside's lemma en.wikipedia.org/wiki/Burnside%27s_lemma with $\mathbb{Z}_8$ acting on the set of such $8$-tuples it will give you the number you are looking for. $\endgroup$ – Clément Guérin Apr 30 '15 at 14:42
  • $\begingroup$ I'm just a high school student and sadly I don't know anything about burnside's formula, is there any other way ? $\endgroup$ – Soham Apr 30 '15 at 14:44
2
$\begingroup$

Here’s a solution that doesn’t apply Burnside’s Lemma (though the idea of that lemma is hidden in it).

Suppose you found all the solutions to $x_1+ x_2 +\cdots +x_{8} = 16$, wrote them in a list, and drew the corresponding necklace for each one. There would be $16+8-1\choose8-1$ solutions and pictures of necklaces.

Many necklaces would appear eight times in your list. If every necklace appeared eight times, the number of different necklaces would be easy to calculate; it would be $\frac{1}{8}\cdot{16+8-1\choose8-1}$.

Unfortunately, not every necklace appears eight times. Some necklaces appear only four times, some twice, and one necklace would appear exactly once. Here’s a picture of just a few solutions and (straightened-out) necklaces, grouped by matching necklaces.

enter image description here

So here’s an idea: carefully duplicate some of the solutions just as necessary so that you have a list where all the necklaces do appear exactly eight times.

If a necklace appears only four times, list each solution with that necklace twice. If a necklace appears just twice, list each solution for that necklace four times, and include the solution that gives one necklace ($x_i=2$) eight times instead of once.

You’ll end up with more than $16+8-1\choose8-1$ “solutions.” How many more - how can you count the number of “solutions-plus-repeats”?

The solutions that gave necklaces that appeared only four times are solutions of the form $x_1+ x_2 +x_3+x_4+x_1+x_2+x_3+x_4 = 16$, that is, they are solutions of $x_1+ x_2 +x_3+x_4=8$. We know there are $8+4-1\choose4-1$ of those. These solutions need to be listed twice, not once, so add $8+4-1\choose4-1$ to your tally.

But oops, some of these solutions actually gave necklaces that appeared just twice, and we ultimately need those to be listed four times (not twice, which they are so far) so we need to add an additional two copies of each solution to $x_1+x_2=4$. That’s another $2\cdot{4+2-1\choose2-1}$ to the tally. And finally, add four more copies of the solution $x_i=2$ so we have eight of those.

The final tally of solutions-plus-duplicates is

$$ \begin{align}&{16+8-1\choose8-1}+{8+4-1\choose4-1}+2\cdot{4+2-1\choose2-1}+4\\=&{23\choose7}+{10\choose3}+2\cdot{5\choose1}+4\\=&245,336. \end{align}$$

The number of necklaces is one-eighth of this, or $30,667$.

$\endgroup$
  • $\begingroup$ I was ready to post a similar solution when I noticed yours, which is much better than my draft, lovely, and beautifully didactic. Special props for plotting this. :) +1 (may I ask which book you learned combinatorics from because if it's similar to your answer, I'd be curious about it - or which book you feel argues in similarly intuitive ways) $\endgroup$ – gnometorule Apr 30 '15 at 18:47
  • 1
    $\begingroup$ Thanks. My first exposure to combinatorics was in graduate school courses taught by David Bressoud and Dick Brualdi. I don’t even remember if there was a textbook! Nowadays, I rarely read entire books, but Stanley’s Enumerative Combinatorics is one I like, if aimed for a bit higher audience than MSE readers in high school. There are a lot of good books, but once you have a foundation, nothing beats practice, drawing, calculating, conjecturing, and so on. I enjoy explaining, and the back-and-forth that’s possible on these sites (and that was on Usenet newsgroups 10-15 years ago) helps a lot. $\endgroup$ – Steve Kass Apr 30 '15 at 21:07
0
$\begingroup$

I think your problem reduction is right.

Without taking rotation groups into account, I would say that you need to place 16 blue beads in 8 groups.

Number of ways of distributing n identical objects among r groups

But this does not take into account the rotation symmetry (don't forget the mirror symmetry if rotation is allowed).

Obviously this is not a high school question in that case.

$\endgroup$
  • $\begingroup$ are you talking about balls and bars? If so then I know it ,and yes it would not take into account the rotation symmetry and that is exactly where I got stuck. If high school math is not enough could you say exactly what topics should I read so that I can approach this problem? $\endgroup$ – Soham Apr 30 '15 at 17:06
0
$\begingroup$

Would you know necklace with 8 white and 16 blue beads?

A blue red blue sequence would be replaced by a white bead.

$\endgroup$
  • 1
    $\begingroup$ I am not getting what you're trying to say. $\endgroup$ – Soham Apr 30 '15 at 17:52

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.