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? [duplicate]

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 ?

marked as duplicate by Sharkos, RGS, Rohan, N. F. Taussig combinatorics StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jan 25 '18 at 21:39

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.

• 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). – bof Jan 25 '18 at 11:19
• Indeed cleaner @bof . – RGS Jan 25 '18 at 11:20

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