Register to reply

Combinations/Permutations of Seating at a Circular Table

by annpaulveal
Tags: circular, seating, table
Share this thread:
annpaulveal
#1
Mar23-13, 04:39 PM
P: 15
1. The problem statement, all variables and given/known data

In how many ways can a group of 9 women and 6 men be seated at a circular table if no two men can be seated next to each other?


2. Relevant equations



3. The attempt at a solution

I have come up with a solution, but I'm unsure if my reasoning is correct...

First, I started with the 9 women. They can be arranged in 8! ways / 9 rotations = 4480 options.

Then, I drew a picture of a 12-person table, placing a man between each woman. This is where I think I may have done something wrong. The men can be placed in 5! ways, divided by 12 for rotations = 10 options.

Finally, I drew a picture of the 15-person table. The three remaining women can be placed in 36 different places, with three possibilities existing between each female/male pair. This can be calculated as 36 choose 3, divided by 15 rotations = 476 options.

The final answer would be all three options multiplied together, so 4480(10)(476).

As I said, I have a feeling that I did something wrong, so I would really appreciate some suggestions to get me back on track :)
Phys.Org News Partner Science news on Phys.org
Law changed to allow 'unlocking' cellphones
Microsoft sues Samsung alleging contract breach
Best evidence yet for coronal heating theory detected by NASA sounding rocket
mfb
#2
Mar23-13, 04:46 PM
Mentor
P: 11,631
I would not consider rotations for men and women separately - the circular symmetry just applies to the whole table, not to both genders separately. You can divide the total number by 15 afterwards, this should be easier.
The three remaining women can be placed in 36 different places, with three possibilities existing between each female/male pair.
But you already fixed the relative woman orientation!

I would begin with the men/women-combinations first, placing 3 women somewhere between existing men/women-pairs, and care about the individual men/women and the circular table afterwards.
annpaulveal
#3
Mar23-13, 04:51 PM
P: 15
Okay, so you're saying I should start with a 12-person table, where the men and women can both be arranged in 5! ways, and then multiply this by 36 choose 3 for the three remaining women, and finally divide this by 15?

So, [(5!)(5!)(36 choose 3)] / 15?

haruspex
#4
Mar23-13, 06:49 PM
Homework
Sci Advisor
HW Helper
Thanks
P: 9,657
Combinations/Permutations of Seating at a Circular Table

Are the positions around the table distinct? I.e. if one arrangement is a rotation of another, are these counted separately?
mfb
#5
Mar23-13, 07:00 PM
Mentor
P: 11,631
@haruspex: I think "circular table" implies that the positions are not distinct.

@annpaulveal: Why 5!? You have 15 distinct chairs to fill (imagine a line of 15 chairs, for example), they will lose their identity afterwards. And I don't think your new idea works.
vela
#6
Mar23-13, 07:52 PM
Emeritus
Sci Advisor
HW Helper
Thanks
PF Gold
P: 11,692
Quote Quote by annpaulveal View Post
Okay, so you're saying I should start with a 12-person table, where the men and women can both be arranged in 5! ways, and then multiply this by 36 choose 3 for the three remaining women, and finally divide this by 15?

So, [(5!)(5!)(36 choose 3)] / 15?
Forget about how to arrange the individual women and men for right now. First figure out how many seating arrangements there are for the 6 men.

There are two ways I can think of to do this:
  1. You have the 12 individuals at the 12-person table, and now you want to move them to the 15-person table without changing their order. How many ways can you do this?
  2. Instead of concentrating on arranging the people, look at the 3 empty seats that will be left over. How many ways can you choose where the 3 empty seats go?
haruspex
#7
Mar23-13, 09:39 PM
Homework
Sci Advisor
HW Helper
Thanks
P: 9,657
Quote Quote by mfb View Post
@haruspex: I think "circular table" implies that the positions are not distinct.
Perhaps, but I think that makes the problem quite hard. Even if the positions are distinct, circular gives a different answer from a straight line, so that may be the point of specifying circular.
haruspex
#8
Mar23-13, 09:44 PM
Homework
Sci Advisor
HW Helper
Thanks
P: 9,657
I'm going to persist with the 'distinct positions' interpretation for now.
Try thinking of it in terms of which women get a man seated to their left.
annpaulveal
#9
Mar24-13, 09:26 AM
P: 15
Quote Quote by haruspex View Post
Are the positions around the table distinct? I.e. if one arrangement is a rotation of another, are these counted separately?
No, arrangements that are rotations of another are considered alike and should not be counted twice.
haruspex
#10
Mar24-13, 04:19 PM
Homework
Sci Advisor
HW Helper
Thanks
P: 9,657
Quote Quote by annpaulveal View Post
No, arrangements that are rotations of another are considered alike and should not be counted twice.
In that case it's somewhat messy. (I don't see that as implied by the text in the OP. Is this additional information?) You have to consider various cases. I found it easiest to think in terms of groups of two or more women seated together. There are three possibilities for the groupings. Then think through how these groupings may be arranged around the table relative to each other. (I assume reflections are distinct.)
Fwiw, if seats were to be distinct, the answer is ##\left(^{w}_m\right)+\left(^{w-1}_{m-1}\right)##.
vela
#11
Mar24-13, 06:25 PM
Emeritus
Sci Advisor
HW Helper
Thanks
PF Gold
P: 11,692
Quote Quote by vela View Post
There are two ways I can think of to do this:
  1. You have the 12 individuals at the 12-person table, and now you want to move them to the 15-person table without changing their order. How many ways can you do this?
  2. Instead of concentrating on arranging the people, look at the 3 empty seats that will be left over. How many ways can you choose where the 3 empty seats go?
I've realized you need to keep the men-women pairs together. So you really have 6 pairs at the first table, and you need to seat them at the 15-seat table. This is what mfb said way back at the beginning.

It may help you to look at a case where it's easy to count by hand. For example, say you have two men and four women. You should be able to convince yourself the only ways you can arrange them are:

mWmWWW
mWWmWW
mWWWmW

Any other arrangement around a circular table would have the two men sitting next to each other. You don't need to include arrangements where a woman is very first because those arrangements are simply one of the above shifted cyclicly to the right. There are 2! ways to seat the men into the two m spots, and 4! ways to seat the women in the four W spots. In total, you have 2243 ways to seat the group at the table without the men sitting next to each other.

So how do you come up with 3, the number of arrangements? In terms of pairs, you can look at the arrangements as

(MW)(MW)WW
(MW)W(MW)W
(MW)WW(MW)

Can you come up with an expression that counts these?
haruspex
#12
Mar25-13, 12:28 AM
Homework
Sci Advisor
HW Helper
Thanks
P: 9,657
Quote Quote by vela View Post
mWmWWW
mWWmWW
mWWWmW
According to the additional information that rotational symmetries are to be factored out, the first and third of those are the same.
vela
#13
Mar25-13, 04:23 AM
Emeritus
Sci Advisor
HW Helper
Thanks
PF Gold
P: 11,692
Oy. OK, I'll leave this problem to you guys.
jashua
#14
Mar25-13, 12:50 PM
P: 43
Think that you place 9 women around the circular table. As the question requires the number of circular permutations, there are (9-1)! ways to place 9 women. Now there are 9 spaces to place 6 men such that none of these 6 men sit next to each other. Then, just find the number of ways to place 6 men into these 9 spaces. After that simply by using the product rule, you should be able to find the result
haruspex
#15
Mar26-13, 01:59 AM
Homework
Sci Advisor
HW Helper
Thanks
P: 9,657
Quote Quote by jashua View Post
Think that you place 9 women around the circular table. As the question requires the number of circular permutations, there are (9-1)! ways to place 9 women.
I believe the women are to be considered indistinguishable from each other, the men indistinguishable from each other, and the seats indistinguishable beyond relative position (i.e. rotations of the arrangements are to be counted only once). All we care about is the pattern of Ms and Ws, like beads on a necklace.
mfb
#16
Mar26-13, 05:31 AM
Mentor
P: 11,631
Quote Quote by haruspex View Post
I believe the women are to be considered indistinguishable from each other, the men indistinguishable from each other
I would be surprised by that. For distinguishable persons, I found a solution (it is not in this thread, but somewhere else). For indistinguishable persons, it is a bit easier, you can simply count the (few) possible cases.


Register to reply

Related Discussions
Q in permutations and Combinations Precalculus Mathematics Homework 1
Permutations and Combinations Precalculus Mathematics Homework 12
Probability Involving Combinations of Classroom Seating Precalculus Mathematics Homework 1
Permutations/combinations help General Math 2
Counting Seating Arrangments of Couples at a Round Table Calculus & Beyond Homework 6