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 neighbors 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
Example
In how many ways can 3 men and 3 women be seated at a round table if- no restriction is imposed
- each woman is to be between two men
- two particular women must sit together
- two particular women must not sit together
- all women must sit together
- there is exactly one person between two particular women?
Solution
- Total six persons can be seated at a round table in 5! = 120 ways.
- 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 - 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 - 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
- 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 - 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
- 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.
- 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
- "Fix" the position of the cat. Now remaining 3 rats and 4 cockroaches can be seated in 7!/(3! 4!) = 35 ways.
- 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.
EmoticonEmoticon