Arrangements of three types of beads around a circle so that no two beads of the same color are adjacent

122 Views Asked by At

Suppose you have beads with colors and numbers on them. There are 8 colored white, 6 colored black, and 3 colored red. The white are numbered 1 to 8, the black numbered 1 to 6, and the red numbered 1 to 3. They are then arranged in a circle on the floor, such that no two of the same color are adjacent. How many arrangements are possible, if rotations of the beads are indistinguishable?

I tried the following calculation which is clearly false since it results in a non-integer:

First we count with position indices. If we place the white beads first at positions 1, 4, 6, 8, and so on, there are 8! ways to fill these positions. If position 2 is black, then position 3 is red, so there are 3 ways to fill position 3, and then 8! ways to fill the remaining 8 positions arbitrarily. We may make position 2 red and 3 black.

So I count $8!8!\cdot 2 \cdot 3$ ways to arrange this with indices. Since there are 17 positions, then every rotation is equivalent, and we get $8!8!\cdot 2\cdot 3/17$.

But I can't spot a logical mistake here, and I don't see another way to count the arrangements.


Oh I just spotted that the second counting of 8! is invalid since one may pick any color (not just white) for position 2. But even correcting for this we then would say there are $8!\cdot 3\cdot 6\cdot 2 \cdot 7! / 17$ arrangements, still not an integer.

2

There are 2 best solutions below

2
On BEST ANSWER

I think I realized the answer, which is that what I counted actually doesn't need to be divided by the number of rotations. Rather, it already makes one particular rotation canonical by placing the two non-white beads in positions 2 and 3.

So in fact $8!\cdot 3\cdot 6\cdot 2\cdot 7!$ is the solution.

0
On

Put down the white bead numbered $1$. We will use it as our reference point. The remaining white beads can be arranged in $7!$ ways as we proceed clockwise around the circle from the white bead numbered $1$.

Arranging the white beads in a circle creates eight spaces in which to place the black and red beads, one to the left of each white bead.

We must place black beads in six of those eight spaces, for otherwise we would not have enough red beads left to separate the blue beads by filling the remaining three spaces with red beads and still separate the adjacent black beads that are in the same space between two blue beads. We can choose which six spaces are filled with black beads in $\binom{8}{6}$ ways and arrange the black beads in those spaces in $6!$ ways as we proceed clockwise around the circle from the white bead numbered $1$.

Both of the remaining two spaces between two blue beads must be filled with red beads. That leaves one more red bead to place. To separate the red beads, it must be placed with one of the six black beads between two blue beads. There are six ways to choose the space in which that red bead goes and two ways to place it next to the black bead in that space, to the left or right of that black bead. Hence, there are $6 \cdot 2$ ways to select spaces for the red beads. The red beads can be arranged in $3!$ ways in the selected spaces as we proceed clockwise around the table from the white bead numbered $1$.

Hence, there are $$7!6!3!\binom{8}{6} \cdot 6 \cdot 2$$ ways to arrange eight distinct white beads, six distinct black beads, and three distinct red beads so that no two beads of the same color are adjacent.