# Understand step in a combinatorial problem using exponential generating functions

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$$

$$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?

• Well... writing the answer as $3^5-3\cdot 2^5+3$ is unrelated to anything you've talked about so far apart from the original problem statement. It is not the type of output you'd see from one of the proposed generating functions. Rather it is the way you'd write the answer had you approached from inclusion-exclusion. There are $3^5$ five-digit numbers using your three digits if we don't care., so we subtract the "bad" outcomes where one of the digits wasn't used, so we subtract $3\cdot 2^5$, but we subtracted too much, so we add back the number where two of the digits weren't used, so $+3$ – JMoravitz Aug 28 '19 at 13:50
• Knowing that the answer should be $3^5-3\cdot 2^5+3$ using the inclusion-exclusion method of finding the answer, and knowing that the answer should be the same as if we used a generating function approach, we know that the coefficient of $x^5/5!$ should be the same... i.e. should also be $150$. – JMoravitz Aug 28 '19 at 13:51

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)$$.
• Where does $3^n$ and $2^n$ come from? Is this for example for $3^n$ its summation by calculating the result of $\left ( \sum^{\infty}_{n=0} \frac{1}{n!} x^n \right)^3$ ? – glendc Aug 28 '19 at 16:30
• @glendc To find the series for $e^{3x}$, just subtitute $3x$ for $x$ in $e^x = \sum_{n=0}^{\infty} (1/n!) x^n$, and then note that $(3x)^n = 3^n x^n$. – awkward Aug 28 '19 at 16:51
• That does make sense. However it does confuse me. Does that mean that denoting this exponential generating function as $e^x$ is just an alternative/special way of writing $e(x)$? And why is that done? It is the first time I see an object variable being linked to a function like that. – glendc Aug 28 '19 at 19:40
• It seems that on this mathonline wikidot page they do note the function using $E(x)$ a syntax I am more familiar with, to than say that it is equal to the notation $e^x$. I suppose the syntax does make sense given that they we are talking about exponential generating functions. I do not understand however why it is called exponential in this case. – glendc Aug 28 '19 at 20:34
• @glendc You can read about the function $e^x$, alternatively written $\exp(x)$, on this Wikipedia page: en.wikipedia.org/wiki/Exponential_function. Also, most calculus books include a section on $e^x$, because it is important in calculus. – awkward Aug 28 '19 at 23:30