2
$\begingroup$

This is not a home work question, I'm preparing for an entrance test.

The number of different necklaces you can form with $2$ black and $6$ white beads is?

My approach: We can place the white beads in the necklace in $1$ way because they all are white. Then the black beads can again be placed anywhere in $1$ way, once a black bead is placed it now acts like a reference, and I can place the last black bead either next to the first black, or with a gap of $1,2,3$ white beads, giving me $4$ combinations as, wbbwwwww, wbwbwwww, wbwwbwww, wbwwwbww.

Is there any other better approach for this? I tried to follow this way, How many different necklaces can be formed with $6$ white and $5$ red beads? but I am getting fractional values,
$$\frac{7!}{6! \cdot 2! \cdot 2}$$
Why is it happening this way? Can't we use this formula logic in all cases?

$\endgroup$
  • $\begingroup$ Are the beads of the same colour identical? $\endgroup$ – Dbchatto67 Apr 14 at 6:46
  • $\begingroup$ Yes beads of same colour can be assumed to be identical $\endgroup$ – Csj Apr 14 at 7:09
  • $\begingroup$ Welcome to MathSE. This tutorial explains how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Apr 14 at 11:15
  • $\begingroup$ Thanks I will make a note of this link! $\endgroup$ – Csj Apr 14 at 17:26
1
$\begingroup$

You are correct that there are four necklaces consisting of $2$ black and $6$ white beads since the two black beads may be separated by $0$, $1$, $2$ or $3$ white beads.

necklaces_formed_with_two_black_and_six_white_beads

We can form a necklace by arranging the eight beads in a row and joining the ends. If we place a black bead at the left end, there are seven ways of placing the other black bead.

rows_of_black_and_white_beads

However, since there are two indistinguishable black beads, we have counted each such necklace twice, with one exception - the middle row - since rows $j$ and $7 - j$ produce the same necklace when the ends are joined. Since the middle row has only been counted once, we must add $1$ before dividing by $2$, otherwise we would count it $1/2$ times. Hence, there are $$\frac{7 + 1}{2} = 4$$ necklaces that can be formed from $2$ black and $6$ white beads.

Notice that the middle row corresponds to the symmetrical necklace at the bottom right above in which the black beads are opposite each other.

Alternatively, we can choose two of the eight positions in the circle for the black beads in $\binom{8}{2}$ ways. If we then divide by $8$ to account for rotations that preserve the relative order of the beads, we obtain $$\frac{1}{8}\binom{8}{2} = \frac{1}{8} \frac{8!}{2!6!} = \frac{7!}{2!6!}$$ which is not an integer. The reason for this is the symmetrical necklace at the bottom right above. It only has four distinguishable rotations, so we have counted it $4/8 = 1/2$ times. Adding $1/2$ to our calculation above to account for this yields $$\frac{7!}{2!6!} + \frac{1}{2} = \frac{7}{2} + \frac{1}{2} = 4$$ as above.

$\endgroup$
  • $\begingroup$ Thanks a lot for this lucid explanation. I get the entire thing but I have a small doubt. In some cases we consider the flipping of the necklace and divide the results by 2, logically I can see that it's not applicable here because there are just 4 ways possible, but why flipping is not applicable in this case? $\endgroup$ – Csj Apr 14 at 17:25
  • 1
    $\begingroup$ Necklaces are invariant with respect to rotation. Bracelets are invariant with respect to rotation and reflection. You may be talking about bracelets. If all the beads are different, the number of bracelets can be found by dividing the number of necklaces by $2$. If there are other symmetries, it is not that simple. $\endgroup$ – N. F. Taussig Apr 14 at 20:12
1
$\begingroup$

Fix a necklace $N$ as the vertices of an octagon. Via rotating, we can assume that the top bead is black. Draw a line between the black beads. This divides the necklace into two white bead subsets. Reflecting along the line if necessary, we can assume the smaller subset $L_N$ (maybe both are equal, that is no issue) is at the left of the top vertex. Now, the amount of beads of the left determine the necklace because this process is reversible, and knowing the amount of white beads of a side determines the other. Hence each necklace is a selection for $L_N$. Note that we can't have $|L_N| > 3$ because this would be the 'large' subset. Hence we have four possible cases corresponding to $|L_N| = 0,1,2,3$.

If you need a formal answer, one could define the necklaces as the equivalence classes of $8$-uples of $\{B,W\}$ modulo rotation, and then give a bijection with $\{0,1,2,3\}$ by assigning each necklace $N$ its corresponding subset $L_N$.

If you are interested and know the basics of group actions, the Pólya Enumeration Theorem is a result in combinatorics which counts the possible necklaces one can form for a certain amount of beads and colors.

$\endgroup$
  • $\begingroup$ I assume you meant as the vertices of an octagon, which has eight vertices. A hexagon has only six vertices. $\endgroup$ – N. F. Taussig Apr 14 at 9:16
  • $\begingroup$ Whoops! Fixed, thanks. $\endgroup$ – Guido A. Apr 14 at 18:24

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.