$$\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.3: Exponential Generating Functions

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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\;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!}. \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\;5}{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.