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!
No comments:
Post a Comment