How many ways can I arrange four girls and five boys in a line such that three or more boys are never together?

Question

How many ways can I arrange four girls and five boys in a line such that three or more boys are never together?

I was thinking of removing the permutations with three or more boys together from the total permutations (9!).

Here's what I've done till now: For picking three boys, we have ${5 \choose 3} \cdot 3! \cdot 7!$ (The 3! is there because the boys are distinguishable.) Now, the case of four and five boys are actually accounted for in this situation - the other six elements (2 remaining boys and 4 girls) can arrange themselves in such a way that 4 or 5 boys are together. However, the flaw in my logic persists when there is a double counting - if the names of the boys were A B C D and E, if A B and C were picked and D is to the right of C, it counts the same as B C D being picked with A to the right.

Answer 1

Yes, enumerating the complement is a good idea. Three boys can be chosen in $5\cdot 4 \cdot 3$ and there are $9-2=7$ ways to arrange them together. The remaining $6$ places can be filled in $6!$ ways. So far we have $$A_3:=(5\cdot 4 \cdot 3)\cdot 7 \cdot 6!$$

Similarly for four boys or five boys together we have $$A_4:=(5\cdot 4 \cdot 3\cdot 2)\cdot 6 \cdot 5!\quad\text{and}\quad A_5:=(5\cdot 4 \cdot 3\cdot 2\cdot 1)\cdot 5 \cdot 4! $$ Unfortunately, for $A_3$ and $A_4$ some of the arrangements are counted more than once. If an arrangement has exactly 4 boys together then $A_3$ counts it twice. If an arrangement has exactly 5 boys together then $A_3$ counts it three times. So the complement has cardinality $$A_3−(A_4−2A_5)−2A_5=A_3-A_4=216000.$$ Hence the desired number of ways is $$9!-216000=146880.$$

P.S. We assume that the four girls and the five boys are distinguishable.

Answer 2

If none of the five boys stand together, the pattern must be $bgbgbgbgb$, which can be assigned in $5!4!=120\cdot24=2880$ ways.

If exactly two boys stand together, start with $-bg-bg-bg-b-$, put the final $g$ in any of the $5$ open spaces, and, finally, replace one of the $4$ $b$'s with a $bb$. All this can be done in $5\cdot4=20$ ways. Then multiply by $5!4!=2880$ ways, for a (sub)total of $57{,}600$ ways.

Finally, if two pairs of boys stand together, start with $-bg-bg-b-$, next either put both of the final $2$ $g$'s in any of the $4$ open spaces or pick two open spaces and put one $g$ in each, and then replace $2$ of the $3$ $b$'s with a $bb$. This can be done in $(4+{4\choose2}){3\choose2}=(4+6)\cdot3=30$ ways. Then multiply by $5!4!=2880$ as before, for a (sub)total of $86{,}400$ ways.

All in all we have

$$5!4!(1+20+30)=120\cdot24\cdot51=146{,}880$$

lineups.

I don't see any way to get the answer in a substantially easier fashion. (Note, Robert Z's approach ultimately uses two subtractions, whereas mine requires three additions, including the $4+6$). In particular, the fact that the final answer is divisible by $17$ suggests it can't be gotten to in one fell swoop. If I'm wrong about this, I'd like to see a single-swoop approach.

My thanks to Robert Z for calling attention to calling attention to an error in my original answer (see the edit history for what I initially did wrong).