A monkey is sitting at a simplified keyboard that only includes the keys “a”, “b”, “c”, and “d”.
The monkey presses the keys at random.
How many sequences are there of length eight that use at most three of the different keys?
I am looking on how to approach this. I have read other posts here with similar problems but some of them have formulas that I have not yet learned.
On
It seems like this should yield to an inclusion-exclusion approach. We observe that there are $3^8$ words in the language $\{a, b, c\}^8$. We get something close to the right answer by multiplying this by $4$, for the four different three-letter subsets of $\{a, b, c, d\}$.
However, by so doing, we double-count the words in the two-letter languages. For instance, the words in $\{a, b\}^8$ appear in both $\{a, b, c\}^8$ and $\{a, b, d\}^8$. To account for this, we must subtract out one of those copies: $2^8$ for $\{a, b\}^8$, and therefore $6 \times 2^8$ for the six different two-letter subsets.
Finally, this subtraction over-subtracts the words in the one-letter languages. For instance, the words in $\{a\}^8$ were added three times in the first count, but subtracted three times in the second count, and therefore they need to be added back once. But there is only one word in $\{a\}^8$, and altogether $4$ words in any of the one-letter languages.
We therefore arrive at the final count
$$ 4 \times 3^8 - 6 \times 2^8 + 4 \times 1^8 = 24712 $$
which is verified by direct enumeration.
First we choose the three letters we can use. Then there are $8$ positions. This gives $3^8$ possible strings, multiplied by $4$ ways that we can choose the three letters.
But wait, we counted the same outcomes more than once.
In particular, we counted the two unique letters case twice, and we counted the case with one unique letter three times.
Luckily, it is easier to calculate these probabilities.
The case with one unique letter is simply $4$.
The case with at least two unique letters is ${4 \choose 2} 2^8$, but we have to subtract the one letter case to get exactly two letters. Namely, we count each one letter case three times, so we subtract $12$.
All in all, this gives
$4 \cdot 3^8 - ({4 \choose 2} 2^8 - 12) - 2(4) = 24712$.