Suppose we have five $a$'s, five $b$'s, and five $c$'s. In how many ways can we form a $15$-letter word such that there are at least three $ab$'s?

Question

Suppose we have five $a$'s, five $b$'s, and five $c$'s. In how many ways can we form a $15$-letter word such that there are at least three $ab$'s, meaning at least three of the $a$'s are each immediately followed by a $b$?

Answer 1

Let $A_{i}$ be the set of such arrangements where an "a" occurs at possition $i$ and a "b" occurs at poition $i+1$ then

$$|A_i|=\frac{13!}{4!^25!}$$

is the number of arrangements of the remaining 13 letter in remaining spaces.

Also

$$|A_{i_1}\cap A_{i_2}|=\frac{11!}{3!^25!}$$ $$|A_{i_1}\cap A_{i_2}\cap A_{i_3}|=\frac{9!}{2!^25!}$$ $$|A_{i_1}\cap A_{i_2}\cap A_{i_3}\cap A_{i_4}|=\frac{7!}{1!^25!}$$ $$|A_{i_1}\cap A_{i_2}\cap A_{i_3}\cap A_{i_4}\cap A_{i_5}|=\frac{5!}{0!^25!}$$

Now we need to use the following inclusion-exclusion formula

$$C_{\ge n}=S_n - \binom{n}{n-1}S_{n+1} + \binom{n+1}{n-1}S_{n+2} - \ldots + (-1)^{r-n}\binom{r-1}{n-1}S_{n+r}$$

for the number of elements belonging to at least $n$ of $r$ sets with

$$S_{k}=\sum_{i_1\le i_2\le\cdots\le i_k}|A_{i_1}\cap\ldots\cap A_{i_k}|$$

and any $k$ adjacent pairs of "ab" may occur at $k$ pairs of positions in $\binom{14-k+1}{k}$ ways. Because there are $14$ adjacent pairs of positions and we must pick $k$ of these such that no two are themselves adjacent, hence

$$S_{3}=\binom{12}{3}\frac{9!}{2!^25!}$$ $$S_{4}=\binom{11}{4}\frac{7!}{1!^25!}$$ $$S_{5}=\binom{10}{5}\frac{5!}{0!^25!}$$

so our required result is

$$C_{\ge 3}=S_{3}-\binom{3}{2}S_{4}+\binom{4}{2}S_{5}=126\,252$$