How many words can be written with $aabbbccdd$ such that no two equal letters are adjacent? I'm trying to count this using the principle if inclusion-exclusion. I've done the following:


*

*Counting the number of permutations of $aabbbccdd$.



  
*
  
*$9!$
  



*

*Counting the number of permutations of $aabbbccdd$ without repetitions.




  
*$\displaystyle\frac{9!}{2!3!2!2!}$ 
  



*

*Now I guess I need need to count the number of permutations in which all letters are together which is $4!$.




  
*$\displaystyle\frac{9!}{2!3!2!2!}-4!$
  



*

*Now counting the number of permutations in which $a,c,d$ are adjacent, I guess that this number is $\displaystyle \frac{3\cdot 7!}{3!2!2!}$.




  
*$\displaystyle\frac{9!}{2!3!2!2!}-4!-\frac{3\cdot 7!}{3!2!2!}$
  



*

*Now counting the number of permutations in which we have permutations of 2 $b$'s together and then the number of permutations which have $3$ $b$'s together, I have $3\cdot 2/2!$, then $\displaystyle\frac{3 \cdot 7!}{2!2!2!}+\frac{6!}{2!2!2!}$




  
*$\displaystyle\frac{9!}{2!3!2!2!}-4!-\frac{3\cdot 7!}{3!2!2!}-\frac{3 \cdot 7!}{2!2!2!}-\frac{6!}{2!2!2!}$
  



*

*Now I know that are intersections in there. But I'm unable to think about something to count them, I guess that I should add the number of intersections to the result:




  
*$\displaystyle \frac{9!}{2!3!2!2!}-\left( 4!-\frac{3\cdot 7!}{3!2!2!}-\frac{3 \cdot 7!}{2!2!2!}-\frac{6!}{2!2!2!}+ \cap_n \right)$
  

Is this correct? If so, how can I count the intersections? I guess that the actual formula would be expressed as:

$$\displaystyle \frac{9!}{2!3!2!2!} \cap (4! \cup \frac{3\cdot 7!}{3!2!2!} \cup \frac{3 \cdot 7!}{2!2!2!} \cup \frac{6!}{2!2!2!})$$

 A: We begin by writing arbitrary words containing only $a$, $a$, $c$, $c$, $d$, $d$.
There are ${6!\over2!2!2!}=90$ such words .
$6$ of these words contain the forbidden pairs $a^2$, $c^2$, and $d^2$. We then need the three $b$'s to separate these pairs. Makes $6$.
There are ${4!\over2!}=12$ words containing $a^2$, $c^2$, and $d$, $d$ in any order.  In $6$ of these the $d$'s are paired as well. It follows that there are $3\cdot(12-6)=18$ words containing exactly two forbidden pairs. For each such word we need two $b$'s to separate the forbidden pairs, and there are $5$ slots left for the third $b$. Makes $18\cdot 5=90$.
There are ${5!\over2!2!}=30$ words containing $a^2$, and $c$, $c$, $d$, $d$ in any order.  $2\cdot6$ of these words contain exactly one of $c^2$ and $d^2$, and another $6$ contain both $c^2$ and $d^2$. It follows that there are $3\cdot(30-12-6)=36$ words containing exactly one forbidden pair. We need one $b$ to separate this pair, and there are $6$ slots left for the remaining two $b$'s. Makes $36\cdot{6\choose2}=540$.
There are $90-6-18-36=30$ words containing no forbidden pair. This allows for $7$ slots where the $b$'s can be written in. Makes $30\cdot{7\choose3}=1050$.
Adding up the obtained counts gives a grand total of $$N=1686$$ allowed words from $a$, $a$, $b$, $b$, $b$, $c$, $c$, $d$, $d$.
A: Use the principle of inclusion and exclusion, iterated for the tripplet and the three pairs.
$$\left(\tfrac{9!}{3!\;2!^3}-\tfrac{8!\;2}{2!^3}+\tfrac{7!}{2!^3}\right)
-\tbinom{3}{1}\left(\tfrac{8!}{3!\;2!^2}-\tfrac{7!\;2}{2!^2}+\tfrac{6!}{2!^2}\right)
+\tbinom{3}{2}\left(\tfrac{7!}{3!\;2!}-\tfrac{6!\;2}{2!}+\tfrac{5!}{2!}\right)
-\left(\tfrac{6!}{3!}-5!\;2+4!\right)$$


*

*$\frac{9!}{3!\;2!^3}$ counts all the permutations of the multiset.

*$-\frac{8!\; 2}{\;2!^2}$ over excludes the permutation where two b are adjacent.

*$+\frac{7!}{2!^3}$ reincludes permutations where all three b are adjacent

*$-{3\choose 1}\left(\frac{8!}{3!\;2!^2}-\frac{7!\;2}{2!^2}+\frac{6!}{2!^2}\right)$ excludes (as the above) for where also one pair of a, c, or d are together

*Then we reinclude where also two pair of those three are together.

*Finally rexcluding where also all three of those are together/
