Associated Topics || Dr. Math Home || Search Dr. Math

### Seating Arrangements

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

Hello,

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,

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

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

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.

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.

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/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search