# Counting permutations with one limitation

Here's a question I came across:

count the number of permutations of 10 men, 10 women and one child, with the limitation that a man will not sit next to another man, and a woman will not sit next to another woman

What I tried was using the inclusion-exclusion principle but it got way to complicated. I don't have the right answer, but I know it should be simple (it was a 5 points question in an exam I was going through).

Any ideas? Thanks!

-

Generally speaking, women and men must alternate. If it weren't for the child, there would be only two ways to do this. The child creates opportunities to switch the parity of the alternation. If the child is at one of the ends or there is an odd number of adults to either side of the child, then there are two possible gender assignments for the adults; whereas if there is an even number of adults to either side of the child, the parity of the gender alternation can be chosen independently on either side, so there are four possible gender assignments in this case. The total is thus

$$12\cdot2+9\cdot4=60\;.$$

If the adults are considered distinguishable, this needs to multiplied by $10!^2$ for the permutations of the women and the permutations of the men, for a total of $60\cdot10!^2=790091366400000$.

-

We see that the possible such arrangements fall into cases:

1. We can replace the $C$ by a $M$ or $W$ and the arrangement is still valid
2. We can't replace the $C$ by a $M$ or $W$ and keep the arrangement valid.

In the first case, once we do the replacement, we have only one valid arrangement: $MWM\cdots WM$ (dually, $WMW\cdots MW$) and so we see that there are 11 such arrangements once we remember that some $M$ (or $W$) is actually C, so 11 in each subcase for a total of 22.

In the second case, each such arrangement is $MWMW\cdots MW$ or $WMWM\cdots WM$ with a $C$ added somewhere that isn't one of the ends. This gives us 19 possible places to add a $C$ in each subcase, or 38 total arrangements in this case.

So there are 60 ways to arrange the $M$s, $W$s, and $C$.

If the adults are distinguishable, we've forgotten that order matters. So we need to multiply by all the ways to arrange the 10 $M$s and 10 $W$s. But that's just $10!$ for each, so our final answer is $60(10!)^2$.

-