-1
$\begingroup$

How many different necklaces can be formed with $6$ white and $5$ red beads?

Since total number of beads is $11$ according to me it should be $\dfrac{11!}{6!5!}$ but correct answer is $21$. How does that come?

$\endgroup$
  • $\begingroup$ since the necklace is "circular" there are many repeated similar combinations in $\dfrac{11!}{6!5!}$ $\endgroup$ – Dylan Zammit Mar 14 '18 at 7:19
  • 1
    $\begingroup$ By my reckoning, the answer is $26$. $\endgroup$ – Lord Shark the Unknown Mar 14 '18 at 8:54
  • $\begingroup$ @LordSharktheUnknown I get $26$ for a bracelet, which is invariant under both rotation and reflection. However, by convention, necklaces are only invariant under rotation. $\endgroup$ – N. F. Taussig Mar 14 '18 at 13:02
  • 1
    $\begingroup$ @N.F.Taussig Then in that case, the answer is 42. $\endgroup$ – Lord Shark the Unknown Mar 14 '18 at 13:12
0
$\begingroup$

First consider $$\dfrac{11!}{5!6!}$$ as you have done. Now since the necklace is "circular" you must divide by the number of beads to remove the repeated arrangements, that is:$$\dfrac{11!}{5!6!11}$$

Also, the necklace can be flipped over, thus twice as many combinations had been counted so far, so you must divide by 2. That is:$$\dfrac{11!}{5!\cdot6!\cdot11 \cdot 2}=21$$

$\endgroup$
  • $\begingroup$ But some necklaces are preserved by the "flipping over" operation. $\endgroup$ – Lord Shark the Unknown Mar 14 '18 at 7:24
  • $\begingroup$ Are you referring to the cases where the beads are "symmetrical"...such as: rrwwwrr ? $\endgroup$ – Dylan Zammit Mar 14 '18 at 7:28
  • 2
    $\begingroup$ Exactly, one needs some (slightly) non-trivial application of Burnside's lemma. $\endgroup$ – Lord Shark the Unknown Mar 14 '18 at 7:35
  • 3
    $\begingroup$ According to en.wikipedia.org/wiki/Necklace_(combinatorics), the convention in combinatorics is that a "necklace" cannot be flipped over. If it can be flipped, it is called a "bracelet". $\endgroup$ – awkward Mar 14 '18 at 13:03

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.