# How many ways are there for eight men and five women to stand in a line so that no two women stand next to each other?

How many ways are there for eight men and five women to stand in a line so that no two women stand next to each other?

I started off by arranging the men into a line so we have $M_1,M_2,M_3,....,M_8$

Then I noticed the following locations for a woman (indicated by $a$) $aM_1aM_2aM_3aM_4aM_5aM_6aM_7aM_8a$ There are $9$ locations where I can put a woman, which would give me $\binom{9}{5}$ different choices. The answer my book gave is $609,638,400$. I'm wondering where I went wrong.

• see this – RE60K Nov 6 '14 at 6:38

While your intuition is correct in that we have a factor of $\binom{9}{5}$, you must also remember that you are simply choosing the places for the women to occupy- they haven't been occupied yet. You now have to order them so that the women are distributed amongst these 5 places, done in 5! ways. Also, the men have to be ordered first, before you insert the women into 5 of the 9 locations.
So it should be $8! \cdot \binom{9}{5} \cdot 5!$
• Ahhh so I should think of it as a 3 step task. Step 1: Organize men, which can be done in $8!$ ways. Step 2: Find all the positions the 5 women can occupy $\binom{9}{5}$. Step 3: Find out how many ways we can put 5 women into those places $5!$. By rule of product the task can be accomplished $8!* \binom{9}{5}*5!$ ways. Do I have it right? – Dunka Nov 6 '14 at 6:42