Ternary strings with each element occurring at least once

Question

It was asked of me to count all ternary strings with size $n$, such that each element $\{a,b,c\}$ occurs at least once in the string. Exercise specific, it was when $n=5$, but I'm looking on building a recurrence relation now.

I approached the problem by counting with labeled distribution i.e. $\frac{n!}{n_1!n_2!n_3!}$, for all possible $n_k$'s in $n=5$, which are either with $2$ repetitions and $1$ single letter, or $3$ repetitions and $2$ single letters. So for $5$ elements, it's $3 \cdot \frac{5!}{3!} + 3 \cdot \frac{5!}{2!2!}$. I'm not sure if I'm correct, because I'm not sure if I'm taking all cases into consideration.

Another way I thought of would be counting all the strings with only $2$ elements and subtract them from the number of all strings which is $3^5$, for this case.

I'll now be looking into in how to build a recurrence relation, and check my previous solution. I haven't found the same question in this forum. Any insight is appreciated!

P.S. This was an exam question. I am now checking my answers.

Answer 1

There are three ways to fill each of the $n$ positions without restriction, so there are $3^n$ ternary strings of length $n$. From these, we must subtract those cases in which fewer than three letters are used in the string.

There are $3$ ways to exclude one of the letters from the string and $2^n$ ways to fill the $n$ positions with the remaining two letters. However, if we subtract $3 \cdot 2^n$ from $3^n$, we will have subtracted too much since we will have subtracted the three strings in which two letters are excluded twice, once for each way we could have excluded one of the two missing letters. Since we only want to subtract such strings once, we must add them back. Therefore, by the Inclusion-Exclusion Principle, the number of ternary strings of length $n$ in which each letter appears at least once is $$3^n - \binom{3}{1}2^n + \binom{3}{2}1^n = 3^n - 3 \cdot 2^n + 3$$

Answer 2

The inclusion-exclusion principle is the standard way to go. Let $A$ be the set of ternary strings containing no $a$, and similarily define $B$ and $C$. Then we're interested in the size of $A\cup B\cup C$ (or more precisely, the size of the complement of $A\cup B\cup C$).

The size of any of $A, B, C$ is $2^n$, since they're sets of binary strings (e.g. $A$ is the set of all binary strings using $b, c$).

The size of any of $A\cap B, A\cap C, B\cap C$ is $1^n = 1$, since they are sets of unary strings (e.g. $A\cap B$ contains the one string $ccc\cdots c$).

The size of $A\cap B\cap C$ is $0^n$ (which is $0$ for $n\geq 1$ and $1$ for $n = 0$), since that's the set of strings of length $n$ using no letters.

Finally, assuming $n\geq 1$, the inclusion-exclusion principle says $$ |A\cup B\cup C| = |A| + |B| + |C| -|A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|\\ = 3\cdot 2^n - 3 $$ The complement of this union, in other words the set of ternary strings containing at least one of each letter, then has $$ 3^n-(3\cdot 2^n-3) $$ elements.

This is already generalised to string length $n$, and it also (relatively) easily generalises to using an alphabet of $k$ letters: you add the size of all possible intersections using an odd number of the sets, and subtract all possible intersections using an even number of the sets. There are in total $2^k-1$ different such combinations, though, so the calculation gets very long even for relatively small $k$ (for $a, b, c,\ldots,j$, there are $1023$ terms).

Answer 3

Another way to get it. The strings of length $n-1$ not containing $a$ will be $2^{n-1}$. Of these, one will contain only $b$ and one only $c$.

So the number of strings of length $n$ which become "eligible" by having the first $a$ in position $n$ are $2^{n-1}-2$, and $3(2^{n-1}-2)$ are the strings which become "eligible" at step $n$.

If we denote by $S(n)$ the required number of strings of length $n$ with at least one $a$,one$b$ and one $c$, then this will be given by the new-comers at step $n$, plus those obtained by adding any of the three characters to the previous $S(n-1)$ strings, thus $$ \left\{ \matrix{ S(2) = 0 \hfill \cr S(3) = 3! = 6 \hfill \cr S(n) = 3\left( {2^{\,n - 1} - 2} \right) + 3S(n - 1) \hfill \cr} \right. $$

You can check that $$ S(n) = 3^{\,n} - \left( {3 \cdot \left( {2^{\,n} - 2} \right) + 3} \right) $$ which means Total N. of strings minus N. of strings with two or one characters.