How many ways to arrange $8$ read beads and $32$ blue beads into a necklace such that at least $2$ blue beads between any $2$ red beads ?

Question

Zaraki 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 $2$ red beads. In how many ways can he do this ?

Part of me, my solution is $30667$ and my result comes from this calculation $$\frac{\binom{23}{7}- \binom{11}{3}}{8}+ \frac{\binom{11}{3}-\binom{5}{1}}{4}+\frac{\binom 51-1}{2}+1=30667.$$ Is my solution true ?

Answer 1

We can regard the necklace as consisting of $24$ items, RBB eight times and B sixteen times. If rotating a necklace counts as the same arrangement but reflection does not then we can use orbit counting on the group of $24$ rotations, catalogued below. $$\matrix{ \hbox{order}&24&12&8&6&4&3&2&1\cr \hbox{number}&8&4&4&2&2&2&1&1\cr \hbox{fixed points}&0&0&C(3,1)&0&C(6,2)&0&C(12,4)&C(24,8)\cr}$$ The number of arrangements is the average number of fixed points $$\frac{4C(3,1)+2C(6,2)+C(12,4)+C(24,8)}{24}=30667\ .$$

Answer 2

It may be of interest to relate this problem to cycle indices and the Polya Enumeration Theorem (PET). Suppose we distribute the eight red beads on the necklace first. Next we distribute two blue beads into every space between two red beads, leaving $32-2\times 8 = 16$ blue beads. The problem now becomes equivalent to distributing the remaining $16$ blue beads into the eight slots under rotation or rotation and reflection.

To compute the count under rotations we need the cycle index $Z(C_8)$ of the cyclic group on eight elements. We now enumerate the permutations in this cycle index. There is the identity, which contributes $a_1^8$. A rotation by a distance of four maps opposite slots to each other and creates two-cycles, giving $a_2^4.$ A rotation by a distance of two or six creates four-cycles, giving $2\times a_4^2.$ A rotation by a distance of $1,3,5$ or $7$ creates eight-cycles giving $4\times a_8.$

This gives the cycle index $$Z(C_8) = \frac{1}{8} (a_1^8 + a_2^4 + 2 a_4^2 + 4 a_8).$$

The desired value is given by $$[z^{16}] Z(C_8)\left(\frac{1}{1-z}\right).$$ This is $$\frac{1}{8} \left([z^{16}] \left(\frac{1}{1-z}\right)^8 + [z^{16}] \left(\frac{1}{1-z^2}\right)^4 + 2 [z^{16}] \left(\frac{1}{1-z^4}\right)^2 + 4 [z^{16}] \left(\frac{1}{1-z^8}\right)\right).$$ which yields $$\frac{1}{8} \left({16+7\choose 7} + {8+3\choose 3} + 2{4+1\choose 1} + 4{2+0\choose 0}\right) = 30667.$$

When reflections are included we have dihedral symmetry and we need the cycle index $Z(D_8)$ of the dihedral group on eight elements. The additional permutations are four reflections about an axis passing through the midpoint of opposite edges connecting two slots, giving $4\times a_2^4$ and four reflections about an axis passing through two opposite slots giving $4\times a_1^2 a_2^3.$ Hence the cycle index is

$$Z(D_8) = \frac{1}{2} Z(C_8) + \frac{1}{16} (4 a_2^4 + 4 a_1^2 a_2^3).$$

This yields for sixteen blue beads the count $$\frac{1}{2} 30667 + \frac{1}{16} \left(4 [z^{16}] \left(\frac{1}{1-z^2}\right)^4 + 4 [z^{16}] \left(\frac{1}{1-z}\right)^2 \left(\frac{1}{1-z^2}\right)^3 \right)$$ which is $$\frac{1}{2} 30667 + \frac{1}{16} \left(4 {8+3\choose 3} + 4 \sum_{q=0}^8 {q+2\choose 2} {16-2q+1\choose´1} \right) = 15581.$$

The sequences OEIS A032193 and OEIS A005514 are relevant here.

Remark. We can also apply Burnside directly to the cycle indices and bypass PET. E.g. for a permutation of cycle type $a_2^4$ to fix an assignment to the four cycles it is necessary that we choose a number $q$ of blue beads for each the four two-cycles and then place twice that number $q$ of beads on the four two-cycles with $q$ beads in each of the two slots on a two cycle.

Choosing a pair has generating function $$\frac{1}{1-z^2}$$ and the total contribution is

$$[z^{16}] \frac{1}{1-z^2} \frac{1}{1-z^2} \frac{1}{1-z^2} \frac{1}{1-z^2}.$$

Similarly an assignment for a permutation of cycle type $a_4^2$ that is fixed by this shape of permutation means that we have to choose a number $q$ of blue beads for each of the two cycles and then place four times that number on each cycle with $q$ beads in each of the slots on the four-cycle. This gives

$$[z^{16}] \frac{1}{1-z^4} \frac{1}{1-z^4}.$$

This can be continued and it is essentially the mechanism by which PET is proved starting from Burnside.

There are many more related links at MSE Meta on Burnside/Polya.