Date: Tue, 4 Feb 1997 12:55:27 -0600 (CST)
Subject: Circular Permutations

Name: Ed
Who is asking: Teacher
Level: All

Question:
I have an understanding of simple problems involving circular permutations but do not understand them when they start to have restrictions. Is there any advice you can give for these more complicated permutations. Below are two specific examples.

Ex 1: In how many ways can 4 married couples seat themselves around a circular table if:
a) spouses sit opposite each other
b) men and women alternate

Ex2. Mom and dad and their 6 children (3 boys and 3 girls) are to be seated at a table. How many ways can this be done if mom and dad sit together and the males and females alternate?

Thanks EV


Hi Ed
In these "circular permutation" problems the usual interpretation is that the initial positions at the table are indistinguishable. In the examples you have if I imagine that the 8 people are "labeled" P1, P2,...,P8 then the arrangement


and

are identical. This is why we say that there are n! ways to arrange n people in a line and only (n-1)! way to arrange n people arround a table.

For example in 1a) suppose that the first woman takes one of the indistinguishable positions at the table, then her spouse must take the seat opposite. There are now six empty chairs, each distinguishable by its position relative to the first woman. The second woman can choose any of these six chairs, each choice giving a different configuration. Once she chooses a chair her spouse must occupy the seat opposite her. There are now four empty chairs so the next woman has four choices for her chair. Her spouse is then seated and the remaining woman now has two choices for her position. Thus there are 6x4x2=48 ways the four couples can seat themselves around the table.

1b)
In this problem suppose that a man is seated first and then the rest of the party are seated around the table starting on his left. The position immediately to his left must be filled by a woman so there are 4 choices. The next position can be filled by any of the 3 remaining men, the next by any of the 3 remaining women, the next by any of the 2 remaining men and so on. Altogether we get 4x3x3x2x2x1x1=144 ways to arrange the couples around the table so that men and women alternate.

It is interesting to note that since the number of couples is even there is no arrangement that satisfies both (a) and (b).

In problem 2 again the positions are indistinguishable so seat one of the adults, say the mom, anywhere and then the dad has two choices for his position, either to her left or to her right. Now go around the table seating the children starting with the empty seat beside dad. There are 3 choices for the girl to occupy this seat. Then seat a boy beside her with a choice of the 3 boys. Continuing around the table there are 2 choices for the girl in the next seat, 2 for the next boy and so on. Altogether you can seat the family in 2x3x3x2x2x1x1=72 ways.

In the Resource Room there are a couple of resources that you might find useful also. They are Donuts and Do Loops and Thoughts on teaching Permutations, Combinations and the Binomial theorem.

Cheers
Penny