How many words of length $n ≥ 4$ in the alphabet ${1, 2, 3}$ contain at least two $1$’s, at least two $2$’s, and at least two $3$’s?
My approach involves the incluson-exclusion principle. If you let $$S=\{\text{all words of length }n\}\\ A_i=\{\text{all words of length }n \text{ that do not contain two }i\text{'s}\},$$ where $1\leq i\leq3$, then our desired number is $$|S-(\bigcup_{i=1}^3A_i)|$$ I am currently trying to figure out what $|A_i|, |A_i\cup A_j|$, and $|A_i\cup A_j \cup A_k|$are to evaluate this expression. Here's my thoughts: $$|A_i|=2^n+n2^{n-1}$$ because the word can either have 0 or 1 $i$. If you have zero $i$'s, then each of the $n$ letters in the word have two options. If you have one $i$ for which you can place in any of the $n$ places, and each of the $n-1$ terms have two options. I am unsure how to compute the others. Any help would be amazing!
Inclusion-exclusion yields: \begin{align} &\quad\binom{3}{0}3^n\\ &-\binom{3}{1}\left(\binom{n}{0}2^{n-0}+\binom{n}{1}2^{n-1}\right)\\ &+\binom{3}{2}\left(\binom{n}{0}1^{n-0}+2\binom{n}{1}1^{n-1}+2\binom{n}{2}1^{n-2}\right)\\ &-\binom{3}{3}\left(\binom{3}{0}[n=0]+\binom{3}{1}[n=1]+2\binom{3}{2}[n=2]+3!\binom{3}{3}[n=3]\right) \\ &= 3^n\\ &-3\left(2^n+n2^{n-1}\right)\\ &+3\left(1+2n+n(n-1)\right)\\ &-\left([n=0]+3[n=1]+6[n=2]+6[n=3]\right) \\ &= 3^n -3\cdot 2^n-3n2^{n-1} +3+3n+3n^2 -\left([n=0]+3[n=1]+6[n=2]+6[n=3]\right) \end{align} If $n \ge 4$, this reduces to $$3^n-3\cdot 2^n-3n2^{n-1}+3+3n+3n^2,$$ which correctly evaluates to $0$ for $n\in\{4,5\}$ and $90=\binom{6}{2,2,2}$ for $n=6$.
This is OEIS sequence A224541.