0
$\begingroup$

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 ?

$\endgroup$

marked as duplicate by Sharkos, RGS, Rohan, N. F. Taussig combinatorics Jan 25 '18 at 21:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Maybe a simpler presentation of the same solution: First arrange the men, $20!$ ways. There are now $21$ places where we can insert a woman, but there are only $20$ women. So choose places for the women (in $\binom{21}{20}=21$ ways) and arrange the $20$ women (in $20!$ ways). $\endgroup$ – bof Jan 25 '18 at 11:19
  • $\begingroup$ Indeed cleaner @bof . $\endgroup$ – RGS Jan 25 '18 at 11:20
-1
$\begingroup$

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!

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.