Number of different necklaces with $4$ beads, s.t. W$\ge$ B$\ge $ R.

combinatoricsnecklace-and-bracelets

It is stated that to form a 4-beads necklace with white, black, and red beads, s.t. $W \ge B \ge R,$
where the number of white, black, and red beads is denoted by W, B, and R respectively.

The text is repeated below.

$$\begin{array}{ccccc}
\hline
W&B&R& Number\\
\hline
4&0 &0& 1\\
\hline
3&1&0&1\\
\hline
2&2&0&2\\
\hline
2&1&1&3\\
\hline
\end{array}$$

In each type we may permute the colors, which gives altogether $3 · 1 + 6 · 1 + 3 · 2 + 3 · 3 = 24$ necklaces. Of course, what we really want to know is the general result for $n$ beads and $r$ colors.

Note: am using below for my analysis, notation of w, b, and r for white, black and red bead respectively.

Please vet:

  • The third case of W, B, R $= 2,2,0$ respectively has $2$ ways given by:
    First place two black beads of the same color. Then, have six ways given by:
    $wwbb, bbww, wbbw, wbwb, wbbw, bwbw.$
    Doubt #1: But, am not clear why divide by $3$ to get $6/3= 2.$

  • The last case of W, B, R $= 2,1,1$ respectively has $3$ inequivalent ways. Have two choices, given by first placing black and red beads in any order (as for a necklace, br$=$rb). Hence, three places to keep two white beads. This gives
    $3C2= 3$ arrangements (inequivalent ways of constructing necklace) given by: wwrb, rwwb, wrwb.

Doubt #2:
How the permutation of beads of distinct colors gives $3·1 + 6·1 + 3·2 + 3·3?$
Definitely the problem wants to only permute among different colored beads, while taking the beads of the same color as indistinguishable, else even the case of W$=4$ would have $4!= 24$ permutations.

So, the first case of W$=4$ can have only one possible permutation.
While, the second case should have $3$ places possible for the black bead, as $3$ places possible among the three white beads.
But, that seems wrong as all the white beads are indistinguishable.
So, there should be only one way.

Request how to derive the number of permutations.

Best Answer

There are $4!$ ways of arranging four distinct beads in a row. However, we only care about their relative order when they are arranged in a circle. Therefore, there are four linear arrangements that correspond to each circular arrangement of four distinct beads. For instance, the four linear arrangements at left in the figure below correspond to the single circular arrangement at right in the figure below (imagine taking the bead at the start of a row and moving it to the end of the row to form the next row) since the relative order does not change when we join the ends of a row to form a circle.

circular permutation of distinct beads

Since each circular permutation corresponds to four linear permutations, there are $$\frac{4!}{4} = 6$$ distinct circular permutations of four beads. Another way to see this is that when we arrange one blue bead, one green bead, one red bead, and one yellow bead in a circle, we can use the blue bead as our reference point. Relative to the blue ball, there are $3! = 6$ ways to arrange the remaining three beads as we proceed clockwise around the circle.

Let's consider what happens when we do the same thing for two black beads and two white beads. Clearly, there are only two possible circular arrangements since either beads of the same color (shade?) are adjacent or they alternate.

As you realized, there are $\binom{4}{2} = 6$ possible linear arrangements of two black beads and two white beads.

Imagine placing the beads on a string. There are four places we can cut the string between successive beads in order to form a linear arrangement. If we do this for the case where the two black beads are adjacent and the two white beads are adjacent, we get four distinct linear arrangements: bbww, bwwb, wbbw, wwbb. If we do this for the case in which the black and white beads alternate, we again get four linear arrangements, only two of which are distinguishable: bwbw, wbwb, bwbw, wbwb. That is why there are six distinguishable linear arrangements rather than eight.

circular permutations of two black and two white beads

There are two ways we could account for this:

  • If we divide the $\binom{4}{2}$ distinguishable linear arrangements by $4$, we do not get an integer. This is because dividing by $4$ counts the four linear arrangements corresponding to the case in which the two black beads are adjacent and the two white beads are adjacent once, but only counts the two distinguishable linear arrangements in which the black and white beads alternate $2/4 = 1/2$ times. We want to count that circular arrangement once, so we must add $1/2$ to the total, which gives $$\frac{1}{4}\binom{4}{2} + \frac{1}{2} = 2$$ as expected.
  • There are four places we could cut the string to form a linear arrangement in each case, giving a total of $\binom{4}{2} + 2 = 8$ ways we could cut the strings of our two necklaces. We add two to the number of distinguishable linear arrangements to account for the two repetitions of the linear arrangements bwbw and wbwb in the case when the black and white beads alternate. With that adjustment, we can now divide by $4$ to obtain the number of circular permutations, which is $$\frac{\binom{4}{2} + 2}{4} = 2$$

For the case with two white beads, one black bead, and one red bead, there are $$\binom{4}{2}2! = 12$$ possible linear arrangements since we must choose two of the four positions for the white beads, then arrange the black bead and red bead in the remaining two positions. Since each circular arrangement of these beads corresponds to four linear arrangements of the beads, as shown in the figure below, there are $$\frac{12}{4} = 3$$ distinct circular arrangements.

circular arrangements of two white balls, one black ball, and one red ball

As for the total, we have to choose the color(s) of the beads in the necklace and multiply by the number of possible arrangements for each choice of colors.

Four beads of one color are used: There are three ways to choose the color (black, white, or red) and one possible arrangement of four beads of that color, giving $3 \cdot 1$ such arrangements.

Three balls of one color and one ball of a different color are used: There are three ways to select the color which is used three times and two ways to select the color that will be used once from the remaining two colors. Hence, there are $3 \cdot 2 = 6$ ways of selecting the colors. For each choice, there is one possible arrangement of three beads of one color and one bead of another color in a circle. Hence, there are $6 \cdot 1$ such arrangements.

Two balls each of two colors are used: There are $\binom{3}{2} = 3$ ways of selecting the two colors to be used and two ways to arrange two beads of each color in a circle. Hence, there are $3 \cdot 2 = 6$ such arrangements.

Two balls of one color and one ball each of the other two colors: There are three ways of selecting the color that will be used twice. For each such choice, there are three ways of arranging two beads of one color and one bead each of the other two colors in a circle. Hence, there are $3 \cdot 3 = 9$ such arrangements.

Total: Since the four cases above are mutually exclusive and exhaustive, the number of necklaces with four beads we can form given white, black, and red beads is $$3 \cdot 1 + 6 \cdot 1 + 3 \cdot 2 + 3 \cdot 3 = 24$$ as claimed.

Related Question