What is the probability that next to every woman sits at least one man

Question

There are $3$ men and women and $6$ seats next to each other in a line (seat 1 is not adjacent to seat 6). The men and women all randomly take a seat. What is the probability that next to every woman sits at least one man.

I got the solution by going through every possibility. The probability should be $50$%, but now I wonder how to do this more mathematically. Can someone help me?

Answer 1

Line up the men and consider the possible spaces next to them:

$$*M*M*M*$$

There are two ways to have the women sit so that each woman sits next to at least one man:

A. There are no two women next to each other. This means that they occupy $3$ of the $4$ positions as indicated by the $*$'s. So, that ${4 \choose 3}=4$ possibilities for that kind of seating.

B. Two women sit next to each other. These two cannot sit at the either end, and so must be sitting in one of the two $*$'s between the men, leaving $3$ positions for the third woman. So: $2 \cdot 3 = 6$ possible arrangements like that.

Of course, the three women cannot sit next to each other, and so these are the only $4+6=10$ possibilities where each woman sits next to at least one man. Since there are ${6 \choose 3}=20$ possible ways to seat the three men and women without any constraints, that means the probability is

$$\frac{10}{20}=\frac{1}{2}=50\%$$

This method can be extended to higher $n$, E.g. let's take $4$ men and $4$ women. Now we have ${5 \choose 4} = 5$ ways where no two women are sitting next to each other, $3 \cdot {4 \choose 2} = 3 \cdot 6 = 18$ ways for one pair of women and $2$ isolated ones, and ${3 \choose 2}=3$ ways for the women to sit in two pairs, for a total of $26$ ways where each women sits next to at least one man. This is out of ${8 \choose 4} = 70$, so the probability there is $\frac{26}{70}=\frac{13}{35}$

For any $n$ in general, there is probably some clever way to find a general formula ... using generating functions maybe? I'm not any good with those ...

Answer 2

How is it possible for there to be a woman who is not sitting next to a man? There are four disjoint cases:

1. Seats 1 and 2 are occupied by women. There are $3\cdot 2 \cdot 4!$ ways this can happen.
2. Seats 5 and 6 are occupied by women. Again there are $3\cdot 2 \cdot 4!$ ways this can happen.
3. Seats 2, 3, and 4 are occupied by women. There are $3!\cdot3!$ ways this can happen.
4. Seats 3, 4, and 5 are occupied by women. There are $3!\cdot 3!$ ways this can happen.

So the probability of failure is $$ \frac{3\cdot 2 \cdot 4!\cdot 2 + 3!\cdot 3!\cdot 2}{6!} = \frac12. $$