How many possible ways are there to seat down 20 men and 20 women on a bench of length 40, such that no two women are adjacent?
At first I was sure the answer was 20!*20!. Because we seat down the women first with spacing between them, and choose their placement. Then we seat down the men and choose their position. Turns out the answer is :
21*20!*20!
I dont understand why ?
On
If you first allocate the women on 20 predestined seats, then you have 20! possibilites to allocate them.
However, having an equidistant spacing of 1 seat between two women is only one in a few options. Let o be a woman, and x be a man:
oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox
This is your spacing. However,
oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxxo
also is a possible spacing. Now two men set besides each other, but that's okay.In fact, there are many other such spacings that are okay, which come out to , who would have guessed it, 21.
(The two equidistant spacings, the first where a woman is on the leftmost chair, the second where a man is on the leftmost chair. Then, for the seating with one "xx", you can swap that "xx" block with any other "x" block)
So, if you factor in the number of spacings to your calculation, you get the desired result: 21*20!*20!
Pick one single man (in $20$ ways).
Arrange the women in $20!$ ways and then the men in $19!$, putting them in between the women. Now this man can be sitting to the right of any of the $20$ women, or he can be at the rightmost corner of the bench, hence he has $21$ positions to go, making
$$21\times 20! \times 19! \times 20 = 21\times20!\times20!$$
The reason why the last man only has $21$ choices, is that if he were to be able to sit either $WXMW$ or $WMXW$, where $X$ is the last man, $W$ were the women already seated, and $M$ the man already in between them, then I would be counting repeated positions, because I could have taken $M$ as the last man to be seated and had $X$ in there already.