3.3: Exponential Generating Functions
( \newcommand{\kernel}{\mathrm{null}\,}\)
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, ex=∞∑n=01n!xn
ex=∞∑n=01⋅xnn!,
considering the n! to be part of the expression xn/n!, we might think of this same function as generating the sequence 1,1,1,…, interpreting 1 as the coefficient of xn/n!. This is not a very interesting sequence, of course, but this idea can often prove fruitful. If f(x)=∞∑n=0anxnn!,
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 as, an even number of bs, and any number of cs.
Solution
For a fixed n and fixed numbers of the letters, we already know how to do this. For example, if we have 3 as, 4 bs, and 2 cs, there are (9342) such permutations. Now consider the following function: ∞∑i=0x2i+1(2i+1)!∞∑i=0x2i(2i)!∞∑i=0xii!.
Now we notice that ∑∞i=0xii!=ex, and that the other two sums are closely related to this. A little thought leads to ex+e−x=∞∑i=0xii!+∞∑i=0(−x)ii!=∞∑i=0xi+(−x)ii!.