# Solving permutation problem the harder way

I am trying to do the following problem using a harder method, I am confident that this could be done, but failed to find any clue where had I made the mistake.

4 boys and 5 girls are to form a line. Find the number of permutations in which no two girls stand next to each other?

Easy way: G B G B G B G B G, so $5!\times 4!=2880.$

Harder way: First I would like to calculate the number of permutation where there are at least 2 girls stand next to each other. We do this by cases. Then we subtract it from the total permutation of $9!$ .

With all the cases, we need to permute the boys first (4!) then the girls. So we "fill" the girls into the following blanks _B_B_B_B_

Case 1: 5 girls stand next to each other.
There are $4!\times{}_5P_5\times5=14400$ ways.

Case 2: 4 girls stand next to each other and 1 girl left separated.
There are $4!\times{}_5P_4\times5\times{}_4P_1=57600$ ways.

Case 3: 3 girls stand next to each other and the remaining 2 girls stand separated from each other.
There are $4!\times{}_5P_3\times5\times{}_4P_2=86400$ ways.

Case 4: 2 girls stand next to each other, another 2 girls stand next to each other (but not next to the former 2) and 1 girls left alone.
There are $4!\times{}_5P_2\times5\times{}_3P_2\times4\times{}_3P_1=172800$ ways.

Case 5: 2 girls stand next to each other, another 3 girls stand next to each other.
There are $4!\times{}_5P_2\times5\times4\times{}_3P_3=57600$ ways.

Case 6: 2 girls stand next to each other and the remaining 3 girls stand separated from each other.
There are $4!\times{}_5P_2\times5\times{}_4P_3=57600$ ways.

But if we take the sum from all the cases, we get $14400+57600+86400+172800+57600+57600=446400$, which is more than $9!=362880$.

I am wondering whether I have dealt with the cases inappropriately or whether I have made any miscalculations.

Any inputs are greatly appreciated. Many thanks!

1. Permute the boys 4!
2. Choose 2 girls from 5 then arrange them ${}_5P_2$
3. Put the 2 girls into 5 gaps between boys, there are 5 possibilities
4. Choose 2 girls from remaining 3 then arrange them ${}_5P_3$
5. Put the 2 girls into 4 gaps between boys, there are 4 possibilities left
6. Arrange the remaining 1 girl then arrange them into 3 remaining gaps ${}_3P_1$

-

Your solution is fine, except in Case 4. In that case, there are only half as many ways, since the two groups of two girls together can be interchanged.

You might have a simpler way to count this case, but one way to do this is to multiply the following:

1) number of ways to arrange the boys: 4!

2) number of ways to choose the 3 gaps for the girls: $5 \choose 3$

3) number of ways to choose the gap for the one girl: $3 \choose 1$

4) number of ways to arrange two girls in the first gap for two: P(5,2)

5) number of ways to arrange two girls in the second gap for two: P(3,2)

-
(By the way, you counted these cases better than I did.) – user84413 Aug 19 '13 at 0:39
Thank you for your solution :) Yes, you are right, it seems that I have counted twice as many. But I still have some difficulties understanding your $5 \choose 3$ and $3 \choose 1$. Would you mind explain it a bit more? I have also added some explanations for my line of thought, I am wondering where had I carelessly doubled the counting? Many thanks. – user71346 Aug 19 '13 at 9:41
(Sorry for the delay in replying.) Since there are 5 gaps created by the boys and there are 3 groups of girls to place in the gaps, there are $5\choose3$ ways to choose the gaps for the girls. Then there are $3\choose1$ ways to select the gap for the single girl. – user84413 Aug 19 '13 at 20:12
(You could instead choose the two gaps for the pairs of girls first, and then choose one gap for the remaining girl.) The reason your answer is twice as large as you want is that if you arrange two girls and then put them in a gap, and then arrange two more girls and put them in a different gap, performing these two steps in the reverse order results in the same arrangement. – user84413 Aug 19 '13 at 20:22
Wow, great. Thanks for your explanation. Now I know where did I make the mistake and could understand your method as well. Thanks very much ! – user71346 Aug 22 '13 at 2:23