How many words can be written with $aabbbccdd$ such that no two equal letters are adjacent?

Question

I'm trying to count this using the principle if inclusion-exclusion. I've done the following:

• Counting the number of permutations of $aabbbccdd$.

1. $9!$

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

2. $\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!$.

3. $\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!}$.

4. $\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!}$

5. $\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:

6. $\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!})$$

Answer 1

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/

Answer 2

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$.