3.3: Exponential Generating Functions

There are other ways that a function might be said to generate a sequence, other than as what we have called a generating function. For example,

$$e^x = \sum_{n=0}^\infty {1\over n!} x^n \nonumber$$ is the generating function for the sequence $1,1,{1\over2}, {1\over 3!},\ldots$. But if we write the sum as

$$e^x = \sum_{n=0}^\infty 1\cdot {x^n\over n!},\nonumber$$

considering the $n!$ to be part of the expression $x^n/n!$, we might think of this same function as generating the sequence $1,1,1,\ldots$, interpreting 1 as the coefficient of $x^n/n!$. This is not a very interesting sequence, of course, but this idea can often prove fruitful. If

$$f(x) = \sum_{n=0}^\infty a_n {x^n\over n!}, \nonumber$$ we say that $f(x)$ is the exponential generating function for $a_0,a_1,a_2,\ldots$.

Example $\PageIndex{1}$

Find an exponential generating function for the number of permutations with repetition of length $n$ of the set $\{a,b,c\}$, in which there are an odd number of $a\,$s, an even number of $b\,$s, and any number of $c\,$s.

Solution

For a fixed $n$ and fixed numbers of the letters, we already know how to do this. For example, if we have 3 $a\,$s, 4 $b\,$s, and 2 $c\,$s, there are ${9\choose 3\;4\;2}$ such permutations. Now consider the following function:

$$\sum_{i=0}^\infty {x^{2i+1}\over (2i+1)!} \sum_{i=0}^\infty {x^{2i}\over (2i)!} \sum_{i=0}^\infty {x^{i}\over i!}. \nonumber$$ What is the coefficient of $x^9/9!$ in this product? One way to get an $x^9$ term is $${x^3\over 3!}{x^4\over 4!}{x^2\over 2!}={9!\over 3!\;4!\;2!}{x^9\over 9!} ={9\choose 3\;4\;2}{x^9\over 9!}. \nonumber$$ That is, this one term counts the number of permutations in which there are 3 $a\,$s, 4 $b\,$s, and 2 $c\,$s. The ultimate coefficient of $x^9/9!$ will be the sum of many such terms, counting the contributions of all possible choices of an odd number of $a\,$s, an even number of $b\,$s, and any number of $c\,$s.

Now we notice that $\sum_{i=0}^\infty {x^{i}\over i!}=e^x$, and that the other two sums are closely related to this. A little thought leads to

$$e^x + e^{-x} = \sum_{i=0}^\infty {x^{i}\over i!} + \sum_{i=0}^\infty {(-x)^{i}\over i!} = \sum_{i=0}^\infty {x^i + (-x)^i\over i!}. \nonumber$$ Now $x^i+(-x)^i$ is $2x^i$ when $i$ is even, and $0$ when $x$ is odd. Thus $$e^x + e^{-x} = \sum_{i=0}^\infty {2x^{2i}\over (2i)!}, \nonumber$$ so that $$\sum_{i=0}^\infty {x^{2i}\over (2i)!} = {e^x+e^{-x}\over 2}. \nonumber$$ A similar manipulation shows that $$\sum_{i=0}^\infty {x^{2i+1}\over (2i+1)!} = {e^x-e^{-x}\over 2}. \nonumber$$ Thus, the generating function we seek is $${e^x-e^{-x}\over 2}{e^x+e^{-x}\over 2} e^x= {1\over 4}(e^x-e^{-x})(e^x+e^{-x})e^x = {1\over 4}(e^{3x}-e^{-x}). \nonumber$$ Notice the similarity to Example 3.2.4.