Number of Sequence

Question

Find the number of sequences of length $n$ consisting of the letters $a,b,c$ in which each letter occurs at least once.

My Approach: select 3 positions from $n$ positions and arrange the letters ${n\choose 3} 3!$ ways and arrange the remaining places in $3^{n-3}$ ways, resulting in a total of $3^{n-3}{n\choose 3}3!$ sequences.

Why is my approach giving me the wrong answer?

Answer 1

Let $X$ be the set of all words in $\{a,b,c\}$ of length $n$, and let $X_a,X_b,X_c$ be the set of all words in $X$ that do not contain the letter $a,b,c$, respectively.

Then you want to find $|X\setminus(X_a\cup X_b\cup X_c)|$.

Inclusion-exclusion to the rescue:

$$\begin{align}|X\setminus(X_a\cup X_b\cup X_c)|=&|X|\\ &-(|X_a|+|X_b|+|X_c|)\\ &+(|X_a\cap X_b|+|X_a\cap X_c|+|X_b\cap X_c|)\\ &-|X_a\cup X_b\cup X_c| \end{align}$$

Each of these values is easier to compute.

---

The generating function approach is to note that the value we seek, $f(N)$, satisfies:

$$\sum_{n=0}^{\infty} \frac{f(n)}{n!}x^n = (e^x-1)^3=e^{3x}-3e^{2x}+3e^x-1$$

and expand the right side out.

The generating function approach is nice for alternate questions. If there is no condition on $a$, and at least one $b$ and two $c$s, then you'd get the generating function:

$$e^x(e^x-1)(e^x-1-x)=e^{3x}-e^{2x}(x+2)+e^{x}(x+1)$$

So the coefficient of $x^n$, when $n>0$, is $$\frac{3^n}{n!} - \frac{2^{n+1}}{n!}-\frac{2^{n-1}}{(n-1)!}+\frac{1}{n!}+\frac{1}{(n-1)!}$$

So the count is $n!$ times this, or:

$$3^n-2^{n+1}-n2^{n-1}+1+n=3^n-2^{n-1}(4+n)+(n+1)$$

Answer 2

Suppose letter $a$ is repeated $1 \leq k \leq n-2$ times, letter $b$ is repeated $1 \leq j \leq n - k-1$ times, and letter $c$ is repeated $n - k - j$ times. The possible number of sequences of length $n$ with this letter frequency is

$$ \underbrace{ \left( \begin{array}{c} n\\ k \end{array} \right) }_{\text{choices of $a$}} \underbrace{ \left( \begin{array}{c} n - k\\ j \end{array} \right) }_{\text{choices of $b$}} $$ Note that since all remaining locations are filled by $c$ we do not have to consider it in our count. To get the total number of sequences of length $n$, you simply sum up these counts

$$ \sum_{k=1}^{n-2}\,\sum_{j=1}^{n-k-1} \left( \begin{array}{c} n\\ k \end{array} \right) \left( \begin{array}{c} n - k\\ j \end{array} \right) $$

Using the formula for a binomial series this expression can be simplified to show that the total number of sequences of length $n$ is $3^n - 3\cdot 2^n + 3$ for all integers $n\geq 3$.

Answer 3

I'd like to point out the relation to Stirling numbers, which immediately yields $${n\brace 3} \times 3!$$ where the three sets of the set partition represent the positions where the letters $a,b$ and $c$ appear. This is

$$3! \times n! [z^n] \frac{(\exp(z)-1)^3}{3!} \\ = n! [z^n] (\exp(3z) - 3\exp(2z) + 3\exp(z)-1) \\ = 3^n -3 \times 2^n + 3.$$