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 3.2.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.

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.

Exercises 3.2

Ex 3.2.1 Find the coefficient of $x^9/9!$ in the function of example 3.2.1. You may use Sage or a similar program.

Ex 3.2.2 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 an even number of $c\,$s.

Ex 3.2.3 Find an exponential generating function for the number of permutations with repetition of length $n$ of the set $\{a,b,c\}$, in which the number of $a\,$s is even and at least 2, the number of $b\,$s is even and at most 6, and the number of $c\,$s is at least 3.

Ex 3.2.4 In how many ways can we paint the 10 rooms of a hotel if at most three can be painted red, at most 2 painted green, at most 1 painted white, and any number can be painted blue or orange?

Ex 3.2.5 Recall from section 1.4 that the Bell numbers $B_n$ count all of the partitions of $\{1,2,\ldots,n\}$.

Let $\ds f(x)=\sum_{n=0}^\infty B_n\cdot {x^n\over n!}$, and note that $$ f'(x)=\sum_{n=1}^\infty B_n {x^{n-1}\over (n-1)!}= \sum_{n=0}^\infty B_{n+1}{x^{n}\over n!}= \sum_{n=0}^\infty \left(\sum_{k=0}^n {n\choose k}B_{n-k}\right) {x^{n}\over n!}, $$ using the recurrence relation 1.4.1 for $B_{n+1}$ from section 1.4. Now it is possible to write this as a product of two infinite series: $$ f'(x) = \left(\sum_{n=0}^\infty B_n\cdot {x^n\over n!}\right) \left(\sum_{n=0}^\infty a_n x^n\right) = f(x)g(x). $$ Find an expression for $a_n$ that makes this true, which will tell you what $g(x)$ is, then solve the differential equation for $f(x)$, the exponential generating function for the Bell numbers. From section 1.4, the first few Bell numbers are 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437. You can check your answer in Sage.