Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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 is the generating function for the sequence 1,1,12,13!,. But if we write the sum as

ex=n=01xnn!,

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!, we say that f(x) is the exponential generating function for a0,a1,a2,.

Example 3.3.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 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!. What is the coefficient of x9/9! in this product? One way to get an x9 term is x33!x44!x22!=9!3!4!2!x99!=(9342)x99!. That is, this one term counts the number of permutations in which there are 3 as, 4 bs, and 2 cs. The ultimate coefficient of x9/9! will be the sum of many such terms, counting the contributions of all possible choices of an odd number of as, an even number of bs, and any number of cs.

Now we notice that i=0xii!=ex, and that the other two sums are closely related to this. A little thought leads to ex+ex=i=0xii!+i=0(x)ii!=i=0xi+(x)ii!. Now xi+(x)i is 2xi when i is even, and 0 when x is odd. Thus ex+ex=i=02x2i(2i)!, so that i=0x2i(2i)!=ex+ex2. A similar manipulation shows that i=0x2i+1(2i+1)!=exex2. Thus, the generating function we seek is exex2ex+ex2ex=14(exex)(ex+ex)ex=14(e3xex). Notice the similarity to Example 3.2.4.


This page titled 3.3: Exponential Generating Functions is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?