$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.2: Exponential Generating Functions

• • Contributed by David Guichard
• Professor (Mathematics) at Whitman College

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

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$$ 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!},$$

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!},$$ 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\;5}$$ 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!}.$$ 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\;5}{x^9\over 9!}.$$ 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 $$\ds \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!}.$$ 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)!},$$ so that $$\sum_{i=0}^\infty {x^{2i}\over (2i)!} = {e^x+e^{-x}\over 2}.$$ A similar manipulation shows that $$\sum_{i=0}^\infty {x^{2i+1}\over (2i+1)!} = {e^x-e^{-x}\over 2}.$$ 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}).$$ Notice the similarity to example 3.1.5.