[Math] 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

combinatoricsdiscrete mathematics

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.

Best Answer

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

Related Solutions

[Math] How many ways are there for 8 men and 5 women to stand in a line so that no two women stand next to each other

For this type of problem first consider the position of the men, then the position of the women.In general first consider the the group with more people.

How many possible ways are there to arrange eight men in a row? It will be $ ^8P_8 = 8! = 40320$

Now as no two women stand next to each other,we can imagine the situation as

                   * M * M * M * M * M * M * M * M *

Hence, we need to find how many ways we can arrange $5$ women in the $9$ possible (as shown above) places,this is actually $ ^9P_5 = 9*8*7*6*5 = 15120$

Now applying the fundamental law of counting (precisely product rule), total number of possible arrangements satisfying both constraints is: $15120 * 40320 = 609638400$ which is your required/desired answer.

[Math] A dance class consists of 22 students, 10 women and 12 men. If 5 men and 5 women are to be chosen and then paired off, how many results are possible

I believe that the problem is that you're counting multiple times. If the couples were ordered (first couple, second couple, etc.) then it would be correct. In this case, though, you can simply go down the list of men and ask yourself "How many different women can I pair with this man?"

Best Answer

Related Solutions

[Math] How many ways are there for 8 men and 5 women to stand in a line so that no two women stand next to each other

[Math] A dance class consists of 22 students, 10 women and 12 men. If 5 men and 5 women are to be chosen and then paired off, how many results are possible

Related Question