Seating Arrangements

Date: 05/16/97 at 15:59:47
From: Helmut Lerche
Subject: Combinatorics

Hello, 

Could you please help me with the following problem:

m men and w women sit down at a round table. How many possible ways 
are there for them to sit when the men are not distingished from 
themselves and also the women are not distinguished from themselves, 
but the sex of the *right* and of the *left* neighbor is important?

Thank you very much for your help,
Helmut Lerche

Date: 07/17/2001 at 15:32:53
From: Martin Wohlemuth
Subject: On Seating Arrangements

Dear Dr. Math,

The following link should answer this question:

  Sequence A047996 - Sloane's On-Line Encyclopedia of Integer Sequences
  http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A047996   

The formula given there isn't handsome at all. The values for m + f < 12 
are listed. It shows how hard the question really is.

Kind regards,
Martin Wohlgemuth

Date: 07/17/2001 at 18:11:03
From: Doctor Anthony
Subject: Re: On Seating Arrangements

Thanks for your comments on the question of circular permutations. I
have studied the subject in some detail, in particular the use of
Burnside's lemma in the solution of these problems. An example of this
is shown below.

We have 18 gems; 6 of them are red, 6 are blue, 6 are green. If we make
a necklace with these 18 gems, how many different necklaces can 
be made?

If there is a single bead of one colour to act as a reference the
problem is easy, but without that we need to use Burnside's lemma and
deal with group action and symmetries of the dihedral group D36. 
(D36 gives the symmetries of a regular 18-sided figure both in rotation
and reflection.)

Burnside's lemma states in effect that the number of distinct 
configurations is equal to the sum of all the group actions that keep
the colours fixed divided by the order of the group (36 in this case).

There are 18 rotational symmetries, and for the reflection symmetries
there are 9 diameters passing through the gap between two beads at each
end and 9 diameters that bisect a bead at either end.

Rotational symmetries that keep the colours fixed (for this particular 
colour scheme of 6 red, 6 blue, 6 green) are the identity and rotation 
through 3, 6, 9, 12, 15 beads. We can make up a table of all the group 
actions that keep the colours fixed.

For example if a rotation through 3 beads is to keep colours fixed,
then we must have repeating groups of 3 beads round the necklace, each
group of 3 with the same colour scheme and each of the red, blue, green
colours represented. The number of such schemes would be 3!

Similarly, for a rotation through 6 beads that keeps colours fixed we
must have a repeating pattern of 6 beads with 2 beads of each colour. 
The colour scheme for the 6 beads could occur in 6!/[2!2!2!] ways.

I will leave you to see that the other rotations are represented as
shown in the table below.

Reflections about a diameter through gaps between two beads requires 
3 red, 3 blue, 3 green on either side of the diameter, and these 9 can
be arranged in 9!/[3!3!3!] ways. The diameter could also rotate into 
9 positions before reflection takes place.

Reflections about a diameter passing through 2 beads requires that the
2 beads be the same colour, i.e. 2 red, 2 blue, or 2 green; you will
then have 8 beads on either side of the diameter with 3 of one colour,
3 of a second colour, and 2 of the same colour as the beads on the
diameter. So for this reflection we get 3 x 8!/[3!3!2!] possible
arrangements.

 Element            Number of configurations
---------           ------------------------- 
Identity            18!/(6!6!6!)   since I fixes everything
r^3                 3!
r^6                 6!/(2!2!2!)
r^9                 9!/(3!3!3!)
r^12 = (r^6)^{-1}   6!/(2!2!2!)
r^15 = (r^3)^{-1}   3!
refl. 1             9!/(3!3!3!)
refl. 2             3 x 8!/(3!3!2!)  

So the sum total of the actions is

17153136 + 6 + 90 + 1680 + 90 + 6 + 9 * 1680 + 9 * 1680 = 17185248.
                                    |          | 
This factor 9 is there because there are 9 possible axes for 
reflections, each leaving the bracelet invariant as the axis of
reflection is moved round to the 9 possible positions.

Applying Burnside, the number of nonequivalent configurations will be

     17185248
    ----------  =  477368
        36

So altogether there are 477368 different necklaces that could be made
from the 18 beads coloured in the way described.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/