8.6: Exponential generating functions
- Page ID
- 97912
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_nx^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:n \geq 0\}\) is \(\sum_n a_nx^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 Example 8.1.
Consider the constant sequence \(1,1,1,1,….\) Then the exponential generating function for this sequence is
\(E(x) = \displaystyle \sum_{n=0}^{\infty} \dfrac{x^n}{n!}\).
From calculus, you probably recall that this is the power series for the exponential function \(e^x\), which is why we call this type of generating function an exponential generating function. From this example, we can quickly recognize that the exponential generating function for the number of binary strings of length \(n\) is \(e^{2x}\) since
\(e^{2x} = \displaystyle \sum_{n=0}^{\infty} \dfrac{(2x)^n}{n!} = \sum_{n=0}^{\infty} 2^n \dfrac{x^n}{n!}\).
In our study of ordinary generating functions earlier in this chapter, we considered examples where quantity (number of apples, etc.) 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.
Suppose we wish to find the number of ternary strings in which the number of 0s is even. (There are no restrictions on the number of 1s and 2s.) As with ordinary generating functions, we determine a generating function for each of the digits and multiply them. For 1s and 2s, since we may have any number of each of them, we introduce a factor of \(e^x\) for each. For an even number of 0s, we need
\(1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dfrac{x^6}{6!} + \cdot \cdot \cdot = \displaystyle \sum_{n=0}^{\infty} \dfrac{x^{2n}}{(2n)!}\).
Unlike with ordinary generating functions, we cannot represent this series in a more compact form by simply substituting a function of \(x\) into the series for \(e^y\). However, with a small amount of cleverness, we are able to achieve the desired result. To do this, first notice that
\(e^{-x} = 1 - x + \dfrac{x^2}{2!} - \dfrac{x^3}{3!} + \cdot \cdot \cdot = \displaystyle \sum_{n=0}^{\infty} \dfrac{(-1)^nx^n}{n!}\).
Thus, when we add the series for \(e^{−x}\) to the series for \(e^x\) all of the terms with odd powers of \(x\) will cancel! We thus find
\(e^x + e^{-x} = 2+2 \dfrac{x^2}{2!} + 2 \dfrac{x^4}{4!} + \cdot \cdot \cdot\),
which is exactly twice what we need. Therefore, the factor we introduce for 0s is \((e^x+e^{-x})/2\).
Now we have an exponential generating function of
\(\dfrac{e^x+e^{-x}}{2}e^xe^x = \dfrac{e^{3x}+e^x}{2} = \dfrac{1}{2}(\displaystyle \sum_{n=0}^{\infty} \dfrac{3^nx^n}{n!} + \sum_{n=0}^{\infty} \dfrac{x^n}{n!})\).
To find the number of ternary strings in which the number of 0s is even, we thus need to look at the coefficient on \(x^n/n!\) in the series expansion. In doing this, we find that the number of ternary strings with an even number of 0s is \((3^n+1)/2\).
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.
How many ternary strings of length \(n\) have at least one 0 and at least one 1?
- Solution
-
To ensure that a symbol appears at least once, we need the following exponential generating function
\(x+\dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdot \cdot \cdot = \displaystyle \sum_{n=1}^{\infty} \dfrac{x^n}{n!}\).
You should notice that this is almost the series for \(e^x\), except it's missing the first term. Thus, \(\sum_{n=1}^{\infty} x^n/n! = e^x-1\). Using this, we now have
\((e^x-1)(e^x-1)e^x = e^{3x}-2e^{2x}+e^x\)
as the exponential generating function for this problem. Finding the series expansion, we have
\(\displaystyle \sum_{n=0}^{\infty} \dfrac{3^nx^n}{n!} - 2 \sum_{n=0}^{\infty} \dfrac{2^nx^n}{n!} + \sum_{n=0}^{\infty} \dfrac{x^n}{n!}\).
Now we can answer the question by reading off the coefficient on \(x^n/n!\), which is \(3^n - 2 \cdot 2^n +1\).
Before proceeding to an additional example, let's take a minute to look at another way to answer the question from the previous example. To count the number of ternary strings of length n with at least one 0 and at least one 1, we can count all ternary strings of length n and use the principle of inclusion-exclusion to eliminate the undesirable strings lacking a 0 and/or a 1. If a ternary string lacks a 0, we're counting all strings made up of 1s and 2s, so there are \(2^n\) strings. Similarly for lacking a 1. However, if we subtract \(2 \cdot 2^n\), then we've subtracted the strings that lack both a 0 and a 1 twice. A ternary string that has no 0s and no 1s consists only of 2s. There is a single ternary string of length \(n\) satisfying this criterion. Thus, we obtain \(3^n−2 \cdot 2^n+1\) in another way.
Alice needs to set an eight-digit passcode for her mobile phone. The restrictions on the passcode are a little peculiar. Specifically, it must contain an even number of 0s, at least one 1, and at most three 2s. Bob remarks that although the restrictions are unusual, they don't do much to reduce the number of possible passcodes from the total number of \(10^8\) eight-digit strings. Carlos isn't convinced that's the case, so he works up an exponential generating function as follows. For the seven digits on which there are no restrictions, a factor of \(e^{7x}\) is introduced. To account for an even number of 0s, he uses \((e^x+e^{−x})/2\). For at least one 1, a factor of \(e^x−1\) is required. Finally, \(1+x+x^2/2!+x^3/3!\) accounts for the restriction of at most three 2s. The exponential generating function for the number of \(n\)-digit passcodes is thus
\(e^{7x} \dfrac{e^x + e^{-x}}{2}(e^x - 1) (1+x+\dfrac{x^2}{2!}+ \dfrac{x^3}{3!})\).
Dave sees this mess written on the whiteboard and groans. He figures they'll be there all day multiplying and making algebra mistakes in trying to find the desired coefficient. Alice points out that they don't really need to find the coefficient on \(x^n/n!\) for all \(n\). Instead, she suggests they use SageMath to just find the coefficient on \(x^8/8!\).
// code
Since \(8!=40320\), this tells them that there are \(33847837\) valid passcodes for the mobile phone. A quick calculation shows that Bob was totally off base in claiming that there was no significant reduction in the number of possible strings to use as a passcode. The total number of valid passcodes is only 33.85% of the total number of eight-digit strings!
Exponential generating functions are useful in many other situations beyond enumerating strings. For instance, they can be used to count the number of n-vertex, connected, labeled graphs. However, doing so is beyond the scope of this book. If you are interested in learning much more about generating functions, the book generatingfunctionology by Herbert S. Wilf is available online at http://www.math.upenn.edu/~wilf/DownldGF.html.