Solve using the Principle of Inclusion and Exclusion:How many ways can 5 boys and 4 girls be arranged such that no two girls stand next to each other? I've been trying to solve this problem with the principle of inclusion and exclusion (it's easy using the standard technique of seating the boys first and then the girls afterwards but I'm stumped using this particular technique (PIE)). Could someone please help me out?
This is what I've tried: 9! - 4C2×8!×2! + 4C3×7!×3! - 4C4×6!×4! = -17280
This gives a negative result which is obviously impossible.
Why doesn't this work? Surprisingly, if there are only 3 girls, the method above works like a charm. It breaks down though with 4.
Edit: By arrangements I mean linear arrangements. The 9 people are to stand in a straight line and then impose this condition.
 A: PIE is trickier here, because the "bad" situations are indexed by pairs of girls. I agree with initial two terms, $9!-\binom{4}2 8!\cdot 2!$. However, when adding back in the doubly subtracted terms, you would need to add back in all arrangements where each pair of pair of girls are both together. These pairs of pairs come in two types, either disjoint pairs or overlapping pairs, and would need to be counted separately. Things only get worse when you look at triple intersection, then all the way up to six-way intersections (EDIT: Actually, it's not that bad at all, see the other wonderful answer!).

Here is an easier way, still with inclusion-exclusion. First, count the arrangements where all boys are identical, as well as all girls. Then, multiply by $5!\cdot 4!$ at the end.
We are arranging $5$ B's and $4$ G's in a line. Let $E_1$ be the set of arrangements where the leftmost G has another G to its right, let $E_2$ be the arrangements where the second G from the left has a G to its right, and $E_3$ where the third G from the left has a G to its right. Using PIE, the number of valid arrangements of identical symbols is (where $AB$ is shorthand for $A\cap B$)
$$
\binom{9}4-|E_1|-|E_2|-|E_3|+|E_1 E_2|+|E_1 E_3|+|E_2 E_3|-|E_1 E_2 E_3|
$$
You can then show (how?) this is
$$
\binom94-\binom31\binom{8}{3}+\binom{3}2\binom{7}2-\binom{3}{3}\binom{6}1=15
$$
so the final answer is $5!\cdot 4!\cdot 15$.
A: Here is another solution using the in-and-out formula:
$$9!-4\cdot3\cdot8!+\left(4\cdot3\cdot2+\frac{4\cdot3\cdot2\cdot1}2\right)7!-4\cdot3\cdot2\cdot1\cdot6!$$
$$=362880-483840+181440-17280=\boxed{43200}$$
Explanation. $9!$ is the total number of arrangements, from which I subtract the number of bad arrangements, which are classified into $12$ overlapping types.
$N(AB)=8!$ is the number of arrangements in which Ann and Betty sit together in that order, with Ann on the left; so the second term is $-4\cdot3\cdot N(AB)=-4\cdot3\cdot8!$.
$N(ABC)=N(AB\cap BC)=7!$ is the number of arrangements in which Ann, Betty, and Carol sit together in that order from left to right; and $N(AB\cap CD)=7!$ is the number of arrangements where Ann and Betty sit together, and Carol and Dorothy sit together, with Ann on the left of Betty, and Carol on the left of Dorothy; so the third term is $4\cdot3\cdot2\cdot N(ABC)+\frac{4\cdot3\cdot2\cdot1}2\cdot N(AB\cap CD)$.
The fourth term is $-4\cdot3\cdot2\cdot1\cdot N(ABCD)$ where $N(ABCD)=6!$ is the number of arrangements where all four girls sit together in alphabetical order from left to right.
All other terms of the in-and-out formula are zero.
