Combinatorics - No two together

[Yashbhatt]

Homework Statement

In how many ways can m men and n women be arranged such that no two women are besides each other?
(m > n)

Homework Equations

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?

 

[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.

 

[haruspex]

In how many ways can m men and n women be arranged such that no two women are besides each other?
(m > n)

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.

 

[Yashbhatt]

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.

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?

 

[haruspex]

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?

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.

 

[Yashbhatt]

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.

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.

 

[PeroK]

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.

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.

 

[Yashbhatt]

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 (n+1) such places and m women, so $\binom{n+1}{m}$ possibilities.

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).

 

[PeroK]

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).

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