How many words of length $n$ over the alphabet $\Sigma = \{a, b, c\}$ exist in which each letter appears at least once?

Question

Let $\Sigma = \{a,b,c\}$ and $ n \in \mathbb N$. How many words of length $n$ over the alphabet $\Sigma$ exist in which each letter appears at least once?

I know how to computation for words without the restriction that each letter appears at least once. So my specific difficulty is how to handle the restriction

Answer 1

Let $(f_n)$ be the desired sequence. You can use exponential generating functions to find the answer too. Note that $$ F(x)=(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dotsb)^3 =\sum_{n=0}^{\infty}\left(\sum_{k_1+k_2++k_2=n;\, k_i>0} \binom{n}{k_1, k_2, k_3}\right) \frac{x^n}{n!} =\sum_{n=0}^{\infty} f_n \frac{x^n}{n!}. \tag{1} $$

But we also have that $$ F(x)=(e^x-1)^3=e^{3x}-3e^{2x}+3e^{x}-1=-1+\sum_{n=0}^{\infty} \left( 3^n-3\times2^n+3 \right)\frac{x^{n}}{n!} $$ In particular $$ f_n= \begin{cases} 0 & \text{if $n=0$;}\\ 3^n-3\times2^n+3 & \text{if $n>0$.} \end{cases} $$

Answer 2

You can do this by inclusion-exclusion. Count all the words, remove those that don't use $a$ and those that don't use $b$, and those that don't use $c$, then for every pair add back the number that don't use any of the pair. Finally subtract of the possibility that does not use any letters at all (this only affects the value for $n=0$).

That's $3^n-3\times2^n+3\times1-0^n$, sequence starts $(0,0,0,6,36,150,540,1806,5796,18150,\ldots)$.