[Discrete Math] Circular Permutations

[Servo888]

"Six men and 6 females are to be seated around a circular table. Every person must be sitting opposite of another person of the same sex. How many different seatings are possible?"

* Ok here's my logic, If you have 12 people, and just want to seat them, you can do so in 11! ways...

* So if you sit 3 men anywhere, then opposite you can sit the rest of the men... I think this would be like P(12 3)...

* Then you just seat the women in the rest of the seats; 5! ways...

So total ways, would be something along the lines of P(12 3) + 5!. I don't think that's right, so that's why I'm here asking for help.

 

[Servo888]

Ok, it's not P(12 3) + 5!.

It should be P(6 3); so we permute 3 people into the first 6 chairs; that means each person will have the same sex across from them. Then we just permute 6 women and men, so 6! + 6!, divide by the number of chairs to get rid of duplicates; so we should get something like...

(P(6 3) + 6! + 6!) / 12

 

[Hurkyl]

Well, you're a lot closer than the first time!

You seem to be making a systematic error. Suppose you have a drawer with b blue socks, and y yellow socks. How many ways can you pick a blue sock and a yellow sock? Do you get the right answer when b=y=1? Or when b=1 and y=0?

we permute 3 people into the first 6 chairs; that means each person will have the same sex across from them.

(As an aside, notice that you've broken the circular symmetry by picking a particular chair to be first! That's why you have to divide by 12 later)

From your clarification, it doesn't sound like you're selecting people, or permuting anything! It sounds like you simply selected three of the first six chairs to be men and three of them to be women. So the number of ways to do this is not 6!/3!.


Anyways, this is what you've done:

(1) You've picked a chair to be first.
(2) Amongst the first 6 chairs (counting clockwise?), you've decided three of them have men.
(3) Now that you know where the men are sitting, seat them.
(4) Now that you know where the women are sitting, seat them.

This is easy to count (once you remember how to combine the numbers), but is it right? You need to know two things:

(A) If you carry out those 4 steps, are you sure you get a legal arrangement of the people?
(B) Suppose you already have an arrangement of people. Are you sure that you count this arrangement exactly 12 times?

If you can say yes to those questions, then you can be sure you have the right answer! (Once you get the arithmetic right)