2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ see this $\endgroup$ – RE60K Nov 6 '14 at 6:38
3
$\begingroup$

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!$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Dunka Nov 6 '14 at 6:42
  • $\begingroup$ Yes, that's right. $\endgroup$ – Sherlock Holmes Nov 6 '14 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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