Number of $n-$letter words over a $3-$letter alphabet $\{a,b,c\}$ using each letter at least once

Question

There has been a similar question before for a fixed length. However I need a solution for an arbitrary length. There was an answer for arbitrary length using generating functions, however since it is rather complicated and unintuitive for me, I was wondering if it is possible to achieve a solution without using generating functions.

My idea would be to count the number of words of length n, namely $3^n$ and subtract something that accounts for the requirement that each letter must be used at least once. Specifically we have $3$ letters that are fixed and $3^{n-3}$ letters that are free. So my solution is $3! \cdot 3^{n-3}$ for $n \geq 3$, which gives wrong results. Where is my error?

Answer 1

We can use the inclusion-exclusion principle to solve this question.

The number of words with maximum three letters equals $3^n$. However, we need to remove combinations that include exactly two unique letters, or one unique letter only.

In the former case, there are three ways of selecting two letters, and $2^n$ possible combinations. However, these also include the cases in which only a single letter appears; we need to remove those again.

In the latter case, there are only three possible combinations (each letter simply appears $n$ times).

Overall, we find that the number of words of length $n$ equals:

$$3^n - \left[{3 \choose 2} 2^n - 2 {3 \choose 2} 1^n \right] - {3 \choose 1} 1^n = 3^n - 3 \cdot 2^n + 3$$

Answer 2

Number of words with maximum 3 letters = $ 3^n$

Number of words with maximum 2 letters = $ 2^n$

How can you choose 2 letters out of $3 : \binom{3}{2} = 3$

Adjust the occurrences of all a's, all b's all c's that are counted twice when choosing 2 letters out of $3$ above: $3$

Hence the number of words with all 3 letters appearing at least once is $ 3^n - 3* 2^n + 3$

Answer 3

To generalize further, the number of $n$-letter words over a $k$-letter alphabet with each letter in the alphabet appearing at least once can be expressed using Stirling Numbers of the Second Kind as

$$\left\{\begin{matrix}n\\k\end{matrix}\right\}k!$$

We first decide how to partition the $n$ positions in the word into $k$ non-empty parts, exactly what stirling numbers of second kind are used to count, and then decide which letter it was who occupied each part in $k!$ ways.

Note: This is not fundamentally different than the inclusion-exclusion approaches used in other answers as inclusion-exclusion is one of the common ways of deriving the values for stirling numbers of second kind (though it is not the only way, recursion is also possible for instance), it merely rewrites it in fewer characters.

As for "So my solution is $3!\cdot 3^{n-3}$ for $n\geq 3$, which gives wrong results. Where is my error" The value of $3!\cdot 3^{n-3}$ counts the number of strings such that very specifically among the first three characters in the string each letter appeared. You only counted strings like ABCAAACCB, CBACABACB, and BACCCCCCC. You failed to count strings where among the first three characters you had repeats like AAABBBCCC, ABABABCAA, etc...

Answer 4

Here's a more direct application of inclusion-exclusion, where the three properties to be avoided are: letter $a$ is missing, letter $b$ is missing, letter $c$ is missing: $$\sum_{k=0}^3 (-1)^k \binom{3}{k}(3-k)^n = \binom{3}{0}3^n - \binom{3}{1}2^n + \binom{3}{2}1^n - \binom{3}{3}0^n = 3^n - 3\cdot 2^n + 3 - [n=0]$$ For $n=0$, this formula gives the correct value $3^0 - 3\cdot 2^0 + 3 - [n=0]=1-3+3-1=0$. More generally, for an alphabet of size $m$, the formula is $$\sum_{k=0}^m (-1)^k \binom{m}{k}(m-k)^n$$ Another interpretation is the number of surjective functions from an $n$-set onto an $m$-set.