Combinatorics - No two together

Tags:
1. Oct 30, 2014

Yashbhatt

1. The problem statement, all variables and given/known data
In how many ways can m men and n women be arranged such that no two women are besides each other?
(m > n)

2. Relevant equations

3. The attempt at a solution
The given answer is m! x P(m + 1, n). I understood how the answer should be a multiple of m!. I also understood that there should be an n in P(m + 1, n). What I couldn't get was how do we get the m + 1 part?

2. Oct 30, 2014

RUber

Perhaps this is mathematically equivalent to something else that could make more intuitive sense. Have you tried computing for small examples? m = 3, n = 2?
You would have
mmwmw
mwmwm
wmwmm
wmmwm
mwmmw
wmmmw
as your permutations, then multiplied by the number of orderings.
Do a couple more and see if the math works out, maybe you will spot your own pattern.

3. Oct 30, 2014

haruspex

It doesn't say, but this seems to refer to arrangement in a straight line, not a circle.
I approach this class of problems by reducing to one that has no such constraint.
First, treat men as identical and women as identical. We can fix that up later by multiplying by the appropriate factorials.
Suppose you have a valid arrangement. The women in the line partition the set of men into subsets (how many?). What constraint is there on the size of each subset (it's not the same for all of them)? Where the constraint is >= 1, throw a man away. How many men are left? How many ways are there of carving them into the right number of partitions of >= 0 each?
To show the technique is valid, you need to see that there is a 1-1 mapping between solutions to the reduced problem and those to the original one. We have the mapping one way. To go the other, just insert one man into every partition that should have at least one.

4. Oct 31, 2014

Yashbhatt

A friend told me this approach : First, let us consider filling all the men. We will fill them with a gap between each one of them so that we can fill the women there. Now, if we fill them in such a way, there will be m - 1 gaps. Now, add two imaginary places at each end. So, now there are m + 1 places. Fill the women in those places and if there are any women on those imaginary gaps, shift them in and in this way we will reach the answer.

Is that correct?

5. Oct 31, 2014

haruspex

Yes, that's an excellent method - though I didn't understand the bit "if there are any women on those imaginary gaps, shift them in". What is meant by shifting them in? Seems to me the job is done.

6. Oct 31, 2014

Yashbhatt

It is to simplify things. Like after all those gaps are imaginary. So, if you have placed the first man on the first seat and then all others with a gap in between, you don't have to work what will be the case then. Just first arrange the women in the seats including the imaginary ones. If you place them on the imaginary ones, then there will be places in between which are empty because m + 1 > n. So, now shift them from the imaginary ones to the empty real ones.

7. Nov 1, 2014

PeroK

I don't follow this logic. The way I'd look at it is. First, you place the n men:

- M - M - M ... - M -

Each dash (-) represents a place where a woman could stand. There are (m+1) such places and n women, so $\binom{m+1}{n}$ possibilities.

Last edited: Nov 1, 2014
8. Nov 1, 2014

Yashbhatt

Yes. That is what I am trying to say.

And according to the question it is P(m + 1, n) and not P(n + 1, m).

9. Nov 1, 2014

PeroK

Yes, got n and m mixed up. Corrected now.