[Math] Circular Permutations. Difference between clockwise and anti-clockwise permutations.

combinatoricscontest-mathpermutations

Please tell me the total number of permutations possible of the beads in a necklace where all the beads are distinct. The necklace consists of n distinct beads.

Answer as per me: the answer is $(n-1)!\:$, as the clockwise and anti-clockwise arrangements are different.

Answer given in various online courses: The clockwise arrangement of the necklace shown is B1-B2-B3-B4. Since the necklace can be flipped, the total permutations = (n-1)!/2. Reason: After flipping the necklace, the anti-clockwise arrangement is the same again i.e. B1-B2-B3-B4.
The link to these online courses are:

1) https://www.askiitians.com/iit-jee-algebra/permutations-and-combinations/circular-permutations.aspx

2) https://www.youtube.com/watch?v=6BoAwmUlfqs>

The 2nd link is a video lecture in the language of Hindi. Start this video from 13:05 minutes, so as to avoid the unnecessary things.

Can you tell me which one is correct with an appropriate explanation.

Best Answer

It's only when one allows the necklace to be flipped over that division by 2 is needed. If one keeps the necklace say on a table and only rotates it (no fair picking necklace up in space) it's the $(n-1)!$ answer.

Related Solutions

[Math] Problem with concepts of circular permutation.

The "ring" question asks "how many ways are there to put 6 people in a ring", where two "ways" are identical if each individual has the same left and right neighbours.

The "table" question asks "how many ways are there to put 6 people at a table", where two "ways" are identical if each individual has the same left and right neighbours and the same place at the table.

It is easy to see that since the possible rotations are 6, the answer to the first question will be 6 times the answer to the second question, and indeed 6! = 6 x 5!.

Concerning the "necklace" problem, the difference from the "ring" problem is that you cannot put people upside down without noticing - while you can to so with a necklace, obtaining a pattern which is symmetric. So the number of combination is halved, because two symmetric combinations are considered as one.

[Math] In how many ways can 5 boys and 3 girls be seated in a row such that no two girls are together

You're overcounting the number of ways "at least two" girls can sit together, because for example

 Boy1 Boy2 Girl1 Girl2 Girl3 Boy3 Boy4 Boy5

is produced twice: Once considering Girl1 Girl2 as the unit, and once considering Girl2 Girl3 as the unit. This means that you're subtracting too large a number from $8!$, leading to a too small final result.

What you're doing is an inclusion-exclusion count, and for those you generally need to keep adding correction terms with alternating signs for ever more special cases.

An easier way to count is to start by finding all the allowed "gender sequences", without respect to which boys and girls are where. Afterwards you can multiply by $5!3!$ do distribute the actual children on the chairs.

To count the gender sequence, start by considering the three girl positions. The two first of them need to have at least one boy immediately to the right, so we have

  ... G B ... G B ... G ...

Now we have to distribute the three remaining B positions in among the four parts noted .... That's a stars-and-bars problem with $\binom{3+4-1}{3}$ possible outcomes.

So the total count you're looking for is $$ \binom{6}{3} \cdot 5!\cdot 3! $$

Best Answer

Related Solutions

[Math] Problem with concepts of circular permutation.

[Math] In how many ways can 5 boys and 3 girls be seated in a row such that no two girls are together

Related Question