The problem asks the following:
In how many ways can you using de digits 1, 2, 3 form numbers of 5 digits, such that each number contains at least 3 different digits?
While this can be solved using multinomial coefficients (and probably some others ways as well), the point here is to try to use generating functions as to practice this concept.
The solution goes as follows.
Note that in all of the cases a digit $a$ ($a \in \{1, 2, 3\}$) is used once, twice or trice. We can see this combinatorial problem as the combination of three individual ordered counting problems, of which each counting problem is linked to a different digit $a$.
As an example, the ordered counting problem that is linked to the digit $1$ has only three possible outcomes, being "$1$", "$11$" and "$111$". Thus, we have one row for each of the lengths 1, 2 and 3 (and no rows for the other lengths). This exponential generating function is therefore
$$
f(x) = x + \frac{x^2}{2!} + \frac{x^3}{3!}.
$$
The generating function that belongs to the combination of these three ordered counting problems is
$$
g(x) = \left( x + \frac{x^2}{2!} + \frac{x^3}{3!} \right)^3.
$$
While we could now find the answer by looking at the coefficient of $\frac{x^5}{5!}$, this is quite error prone and messy.
An alternative way of finding this coefficient is to write the last generating function as
$$
g(x) = \left( \sum^{\infty}_{k=1}\frac{x^k}{k!} \right)^3
$$
instead. Now is
$$
e^x = \sum^{\infty}_{k=0}\frac{x^k}{k!}
$$
such that
$$
g(x) = (e^x – 1)^3 = e^{3x} – 3e^{2x} + 3e^x – 1.
$$
The coefficient of $\frac{x^5}{5!}$ here, is of course $3^5 – 3 \cdot 2^5 + 3 = 150.\space\space\space \blacksquare$
With a lot of effort I managed to understand it all, except the part following the "of course", of course… Probably it is because I do not understand the $e^x$ exponential generating function very well. Can someone please break down how we get from the 2nd last step to the last step?
Best Answer
We have $$\begin{align} g(x) &= e^{3x} - 3e^{2x} + 3e^x - 1 \\ &= \sum_{n=0}^{\infty} \frac{1}{n!} 3^n x^n -3 \sum_{n=0}^{\infty} \frac{1}{n!} 2^n x^n +3 \sum_{n=0}^{\infty} \frac{1}{n!} x^n -1 \end{align}$$ so the coefficient of $x^5$ in the first summation is $$ \frac{1}{5!} 3^5$$ in the second summation, $$-3 \cdot \frac{1}{5!} 2^5$$ and in the third summation, $$3 \cdot \frac{1}{5!}$$
Add these up and multiply by $5!$ to get the coefficient of $x^5/5!$ in $g(x)$.