3.3: Exponential Generating Functions
- Page ID
- 7154
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\).
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.