Introduction to generating functions

Overview

The main idea here is that we're going to work in the ring of formal power series. A ring, recall, is just a certain type of algebraic structure. For us, all we need to concern ourselves with right now is that the sum of two power series is a power series and that the product of two power series is a power series. Every power series has an additive inverse (almost trivially), and some have multiplicative inverses (which will be discussed in later sections). The most important thing to remember is that we consider these power series as elements of a certain ring. As such, we are not concerned with the convergence of any power series (yet). There will come a time and place to discuss these ideas (as we will want to sum certain sequences and pick off certain terms, both of which demand us "plugging in values for x"), but for now, we'll just interpret them formally.

As a brief example, note that the expression $\sum _{n\geq 0}n!x^{n}$ does not have a positive radius of convergence (converges only when x = 0), but it is still a perfectly good element of our ring of formal power series.

Types of generating functions

Ordinary generating functions

Given a sequence $\left\{a_{n}\right\}$, the ordinary generating function of $\left\{a_{n}\right\}$ f(x) is the formal power series

$f(x)=\sum _{n\geq 0}a_{n}x^{n}.$

If f(x) is the ordinary generating function for the sequence $\left\{a_{n}\right\}$, we often write

$f(x)\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{ops}}\ \left\{a_{n}\right\}$

We don't often concern ourselves with the convergence of these series; we interpret them strictly in a formal sense.

For an example, recall from calculus that the function $f(x)={\dfrac {1}{1-x}}$ has power series representation

${\dfrac {1}{1-x}}=1+x+x^{2}+\cdots =\sum _{n\geq 0}x^{n}.$

The sequence of coefficients of the powers of x in the above power series is the sequence that is constantly 1. Hence, we have that

${\dfrac {1}{1-x}}\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{ops}}\ \{1\}_{n\geq 0}.$

Exponential generating functions

Another type of generating function, the exponential generating function is similar to the ordinary generating function, but with a twist. If f(x) is the exponential generating function for the sequence $\left\{a_{n}\right\}$, we write

$f(x)\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{egf}}\ \left\{a_{n}\right\},$

and this means that the function f(x) has power series representation

$f(x)=\sum _{n\geq 0}a_{n}{\dfrac {x^{n}}{n!}}.$

We saw above that the function ${\dfrac {1}{1-x}}$ is the ordinary generating function for the sequence that is constantly 1; but for what sequence is it the exponential generating function?

Note that for all n, we have

${\dfrac {1}{1-x}}=\sum _{n\geq 0}x^{n}=\sum _{n\geq 0}n!{\dfrac {x^{n}}{n!}}.$

If we set $\left\{a_{n}\right\}=\left\{n!\right\}$, we have that

${\dfrac {1}{1-x}}=\sum _{n\geq 0}n!{\dfrac {x^{n}}{n!}}$,

so we can write

${\dfrac {1}{1-x}}\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{egf}}\ \left\{n!\right\}_{n\geq 0}.$

So what is the exponential generating function of the sequence that is constantly 1? Recall that e^x has the power series representation

$e^{x}=1+x+{\dfrac {x^{2}}{2!}}+{\dfrac {x^{3}}{3!}}+{\dfrac {x^{4}}{4!}}+\cdots =\sum _{n\geq 0}{\dfrac {x^{n}}{n!}}$,

so we have

$e^{x}\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{egf}}\ \{1\}_{n\geq 0}.$

This should give you a feel as to why the name for such a generating function is "exponential" generating function.

Continuation

This lesson continues on the page titled calculus of generating functions.

See also

• Wikipedia:generating functions
• generating functions