Number of colourings of the necklace.

Question

I want to count the number of ways to color beads of a necklace green and red, such that two adjacent beads cannot both be red. The necklace cannot be turned or reflected, the beads are labelled.

Initially, I tried for a fixed number of red beads.

Let there be $n$ beads in total, $r$ of which are red, so $n-r$ are green. Every bead can have a red bead to its right, so the places for red beads are $n-r$. Hence, the number of possibilities is $$ \binom{n-r}{r}$$

Summing up for all the numbers of red beads, we get $$ \sum_r \binom{n-r}{r} = F_{n+1} $$ However, this is not correct, mainly because for $ n = 5 $, and $r = 1$, the result is $4$ instead of $5$. Writing $\binom{n-r+1}{r}$ doesn't fix the situation.

How can these colorings be correctly counted?

Answer 1

Your argument counts the solutions for beads in a straight line so we can solve this problem in 2 parts by first looking at beads in a straight line and then worrying about beads in a loop.

It is easy to see (using your logic or recursion) that if there are n beads that are in a straight line and do not loop around at the end the number of combinations is a Fibonacci number ($F_{n+1}$). Your argument works fine but a simpler proof is what follows:

For n=1 there are 2 ways, for n=2 there are 3 ways, and in general the first bead is either red followed by a green or green so we sum the previous 2 cases. For example, for n = 3 we can either start with green which gives us 3 situations for the remaining 2 or start with red which forces a green after, leaving us with 2 possibilites for the remaining bead. So the total is 5 possibilites or 3+2. This is the Fibonacci sequence of course, 2, 3, 5, 8, 13... If we use $F_0 =1$ and $F_1=1$ then the n beads case has $ F_{n+1}$ solutions.

Now for a necklace, notice that, any individual bead can either be green which reduces to n-1 beads with no loop ($F_n$ solutions) or be red and a green on either side of it which reduces to n-3 with no loop ($F_{n-2}$ solutions). So in general, the number of solutions when $n\gt3$ is $F_n + F_{n-2}$.

Answer 2

For $5$ beads of which $1$ is red there is only $1$ way to color the necklace when considering each 'bead slot' of the necklace as indistinguishable.

We can think of it this way: for every red bead, there is exactly one adjacent clump of green beads to the left (or right, just pick one WLOG). I am choosing to think of it this way because when you get to the 'last' red bead, a group to the right of it will actually be part of the first clump of green beads since the necklace loops around.

Proceeding with this line of thinking, we have $r$ clumps of green beads, $x_1, x_2, ..., x_r$ where each clump must contain $1$ or more green beads, (otherwise at least one pair of red beads will be adjacent) and $\sum_{i=1}^rx_i=n-r$. The number of ways this can be done is just Theorem $1$ of Stars and Bars: $${n-r-1}\choose{r-1}$$

For $n=5, r=1$, this gives us ${3}\choose{0}$ or $1$.

If you are considering each slot of the necklace as unique, this becomes a different problem and requires a different approach, I think TheJack's answer addresses this case.

Answer 3

I want to answer this question using a special form of generating functions called Smirnov words. Look at Analytic combinatorics example $III.24$.

Lets find the number of arrangementss in a line such that no two consecutive red beads allowed, but no restriction over green beads. In our case, the generating function for the number of Smirnov words over our alphabet (i.e red and green strings) is equal to $$\bigg(1- \frac{x}{1+x}-\frac{\frac{x}{1-x}}{1+\frac{x}{1-x}}\bigg)^{-1}=1+2x+3x^2+5x^3+8x^4+13x^5+21x^6+34x^7+..+144x^{10}+..$$

As you realize it match with Fibonacci numbers. However, this generating functions counts the cases in a straight line ,and so it includes some cases that breaks the rule when this line become a circle.

The rule breakers are the strings which starts and ends with red beads. So, if we discard these rule breakers, we can reach the correct numbers.

The rule breakers strings are those which starts with rg and ends with gr in a desired Smirnov words, because when these Smirnov words are made a circle,the reds will merge and break the rule. When i come to the reason why we also put "g" after and before our red beads is that if we just calculate the number of Smirnov words of length $n-2$, then it would also count those which starts and ends with red beads. So, it would cause $r,r,...,r,r$, but we do not want it. We just want those which obeys the rule but starts and ends with red beads.

. Now ,lets assume that we want to calculate the number of rule breaker strings of size $7$. Then, we should find the number of Smirnov words of length $3$ calculated above. After that , subtract those rule breakers from the total ,i.e $34$.

Example: Lets calculate the number of necklaces of size $5$:

Step $1-)$ Find the coefficient of $x^5$ in the generating function of desired Smirnov words, which is $13$

Step $2-)$ Find the coefficient of $x^{5-4}$ in the generating function of desired Smirnov words, which is $2$

Step $3-)$ Subtract those rule breakers from the total, so $13-2=11$.

We found that there are $11$ necklace that do not contain two consecutive reds

• g,g,g,g,g

• r,g,g,g,g

• g,r,g,g,g

• g,g,r,g,g

• g,g,g,r,g

• g,g,g,g,r

• r,g,r,g,g

• r,g,g,r,g

• g,r,g,r,g

• g,r,g,g,r

• g,g,r,g,r

Example 2: Lets calculate the number of necklaces of size $6$:

Step $1-)$ Find the coefficient of $x^5$ in the generating function of desired Smirnov words, which is $21$

Step $2-)$ Find the coefficient of $x^{5-4}$ in the generating function of desired Smirnov words, which is $3$

Step $3-)$ Subtract those rule breakers from the total, so $21-3=18$.

We found that there are $18$ necklace that do not contain two consecutive reds

• gggggg

• rggggg

• grgggg

• ggrggg

• gggrgg

• ggggrg

• gggggr

• rgrggg

• rggrgg

• rgggrg

• grgggr

• grggrg

• grgrgg

• ggrggr

• ggrgrg

• gggrgr

• grgrgr

• rgrgrg

NOTE: Our solution works because of the beads are labelled. If they are not, then we needs Burnsides' lemma to get rid of overcounting.