Number of Sequence 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?
 A: 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)$$
A: 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$.
A: 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.$$ 
