Circular Permutations

In general, the number of ways of arranging n objects around a round table is (n-1)!

An easier way of thinking is that we "fix" the position of a particular person at the table. Then the remaining n -1 persons can be seated in (n-1)! ways. Done!

Thus the number of ways of arranging n persons along a round table so that no person has the same two neighbours is(n-1)!/2

Similarly in forming a necklace or a garland there is no distinction between a clockwise and anti clockwise direction because we can simply turn it over so that clockwise becomes anti clockwise and vice versa. Hence the number of necklaces formed with n beads of different colours = (n-1)!/2

Illustrative Examples

Example

In how many ways can 3 men and 3 women be seated at a round table if

1. no restriction is imposed
2. each woman is to be between two men
3. two particular women must sit together
4. two particular women must not sit together
5. all women must sit together
6. there is exactly one person between two particular women?

Solution

1. Total six persons can be seated at a round table in 5! = 120 ways.
2. Three men can be seated first at the round table in 2! = 2 ways.
   Then the three women can be seated in 3 gaps in 3! = 6 ways.
   Hence the required number of ways = 2 x 6 = 12
3. Temporarily treating two particular women as one big fat woman, five persons can be seated at a round table in 4! = 24 ways. However these two women can be arranged within themselves in 2! = 2 ways.
   Hence the required number of arrangements = 24 x 2 = 48
4. As out of total 120 arrangements, there are 48 ways in which these two women sit together, the required number of arrangements = 120 -48 = 72
5. Temporarily treating three women as one person, four persons can be arranged at round table in 3! = 6 ways. Further, these 3 women can be arranged among themselves in 3! = 6 ways.
   Hence the required number of arrangements is 6 x 6 = 36
6. Temporarily leave aside two particular women. The remaining 4 persons can be seated in 3! = 6 ways. Now these two particular women may be seated "around" any of 4 persons, and further the two can be arranged within themselves in 2 ways.
   Hence the required number of arrangements is 24 x 2 = 48

Example

1. A cat invites 3 rats and 4 cockroaches for dinner. How many seating arrangements are possible along a round table? Assume that animals of a species all look alike, though they will be deeply offended at this assumption.
2. If m indistinguishable men from Mars and n indistinguishable women from Venus sit around a round table, how many possible seating arrangements are there?

Solution

1. "Fix" the position of the cat. Now remaining 3 rats and 4 cockroaches can be seated in 7!/(3! 4!) = 35 ways.
2. Important. You may think that the formula (m -n -1)!/[m! n!] should work in such cases. Try putting m = 3, n = 3, you get 5!/[3! 3!] = 10/3, which is a fraction! In general, there is no formula for circular permutations where all items are repeated. However, even if a single item is there which is not repeated, we can "fix" its position and then find permutations of all remaining items.

Exercise

1. In how many ways can 7 boys be seated at a round table so that two particular boys are
   (i) next to each other
   (ii) separated?
2. In how many ways can 4 ladies and 4 gentlemen be seated at a round table so that all ladies sit together?
3. 6 person sit around a table. In how many ways can they sit so that no person has the same neighbors?
4. How many different necklaces can be made with 6 beads
   (i) of different colors
   (ii) of same color?
5. Find the number of ways in which 5 men and 4 women can be seated round a table so that no two women are together.
6. In how many ways can 7 men and 7 women be seated round a table so that no two women are together?
7. In how many ways may six Hindus and six Muslims sit round a table so that no two Hindus sit together?
8. Three boys and three girls go out for dinner. A shy boy does not want to sit with any girl and a shy girl does not want any boy as a neighbour. How many seating arrangements are possible?
9. A round table conference is to be held between 20 delegates. How many seating arrangements are possible if two particular delegates are
   (i) always to sit together
   (ii) never to sit together
   (iii) always separated by exactly one person?
10. Indian cricket team sits down for dinner at a round table. In how many arrangements is Saurav flanked by Sachin and Dravid?
11. (i) How many ways can a necklace be formed from 2 red and 2 blue beads?
    (ii) Two twin brothers are married to two twin sisters. In how many ways can they sit at a round table?
12. How many different garlands can be made from 6 marigolds and 2 roses?

Answers