Exponential generating functions

If we had wanted to be absolutely precise earlier in the chapter, we would have referred to the generating functions we studied as ordinary generating functions or even ordinary power series generating functions. This is because there are other types of generating functions, based on other types of power series. In this section, we briefly introduce another type of generating function, the exponential generating function. While an ordinary generating function has the form \(\sum_{n} a_n x^n\), an exponential generating function is based on the power series for the exponential function \(e^x\). Thus, the exponential generating function for the sequence \(\{a_n\colon n\geq 0\}\) is \(\sum_n a_n x^n/n!\). In this section, we will see some ways we can use exponential generating functions to solve problems that we could not tackle with ordinary generating functions. However, we will only scratch the surface of the potential of this type of generating function. We begin with the most fundamental exponential generating function, in analogy with the ordinary generating function \(1/(1-x)\) of .

In our study of ordinary generating functions earlier in this chapter, we considered examples where quantity (number of apples, ) mattered but order did not. One of the areas where exponential generating functions are preferable to ordinary generating functions is in applications where order matters, such as counting strings. For instance, although the bit strings \(10001\) and \(011000\) both contain three zeros and two ones, they are not the same strings. On the other hand, two fruit baskets containing two apples and three oranges would be considered equivalent, regardless of how you arranged the fruit. We now consider a couple of examples to illustrate this technique.

We can also use exponential generating functions when there are bounds on the number of times a symbol appears, such as in the following example.

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.