Suppose I have 11 beads. 4 of them are red and 3 of them are blue. The remaining 4 are all distinct (so just say labelled 1 to 4).

If these beads were in a straight line, then computing the number of permutations is fairly simple. It is $\dfrac{11!}{4!3!}$.

Now suppose they are on a necklace. Would the answer be as simple as just $\dfrac{10!}{4!3!}$, where we reduced one element from the numerator due to first having a fixed bead as a 'point of reference', as we usually do for circular arrangements?

I feel that it is not just this simple, and that we've opened a whole new can of worms by having identical beads.

If that is the case, what is wrong with the logic above, and why does the degree of complexity change so vastly with a simple change in the arrangements (straight line vs circular)?

  • $\begingroup$ You have, as there would now be identical permutations stemming from non-trivial rotations of various permutations. $\endgroup$
    – miradulo
    May 1 '15 at 17:00
  • $\begingroup$ Can you please elaborate more on that? I can roughly see where you're getting at, but a more detailed response would really be great in helping me understand the mechanics of this. $\endgroup$
    – Trogdor
    May 1 '15 at 17:05
  • 1
    $\begingroup$ If i had time at the moment I would, I will return to this question later and provide you with a detailed answer regarding Polya enumeration should someone have not already done so by then. $\endgroup$
    – miradulo
    May 1 '15 at 17:09
  • $\begingroup$ Polya enumeration here is very simple because $11$ is prime. $\endgroup$ May 1 '15 at 19:47

Assume that the beads are all ordered, so the necklace is in a fixed position. Then there are $\frac{11!}{3!4!}$ colorings.

However each coloring is identical to the five other colorings obtained by rotating the collar by one bead, two bead.... five beads. Note that all of these rotations have to be different because of the primality of $11$. If two of them where equal then all of them would have to be equal, but if all the rotations are equal then all the beads would have to be equal which goes against the problem's hypothesis.

Hence there are $\frac{11!}{3!4!6}$ different types of collars. This is equal to $46200$


You need to divide by 2 because you can flip the necklace over @Gamamal. This is the catch which distinguishes questions concerning arrangements in a circle as opposed to arrangements on a necklace.


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.