Seating ArrangementsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/