math lessons - Generating function

(Redirected from Exponential generating function)

In mathematics a generating function is a formal power series whose coefficients encode information about a sequence a_n that is indexed by the natural numbers.

There are various types of generating functions - definitions and examples are given below. Every sequence has a generating function of each type. The particular generating function that is most useful in a given context will depend upon the nature of the sequence and the details of the problem being addressed.

Generating functions are often expressed in closed form as functions of a formal argument x. Sometimes a generating function is evaluated at a specific value of x. However, it must be remembered that generating functions are formal power series, and they will not necessarily converge for all values of x.

Contents

1 Definitions

1.1 Ordinary generating function
1.2 Exponential generating function
1.3 Lambert series
1.4 Dirichlet series generating functions
1.5 Polynomial sequence generating functions

2 Examples

2.1 Ordinary generating function
2.2 Exponential generating function
2.3 Dirichlet series generating function

Definitions

A generating function is a clothesline on which we hang up a sequence of numbers for display. -- Herbert Wilf, generatingfunctionology (1994)

Ordinary generating function

The ordinary generating function of a sequence a_n is

$G(a_n;x)=\sum_{n=0}^{\infty}a_nx^n.$

When generating function is used without qualification, it is usually taken to mean an ordinary generating function.

If a_n is the probability mass function of a discrete random variable, then its ordinary generating function is called a probability-generating function.

The ordinary generating function can be generalised to sequences with multiple indexes. For example, the ordinary generating function of a sequence a_m,n (where n and m are natural numbers) is

$G(a_{m,n};x,y)=\sum_{m,n=0}^{\infty}a_{m,n}x^my^n.$

Exponential generating function

The exponential generating function of a sequence a_n is

$EG(a_n;x)=\sum _{n=0}^{\infty} a_n \frac{x^n}{n!}.$

Lambert series

The Lambert series of a sequence a_n is

$LG(a_n;x)=\sum _{n=1}^{\infty} a_n \frac{x^n}{1-x^n}.$

Note that in a Lambert series the index n starts at 1, not at 0.

Dirichlet series generating functions

Dirichlet series are often classified as generating functions, although they are not strictly formal power series. The Dirichlet series generating function of a sequence a_n is

$DG(a_n;s)=\sum _{n=1}^{\infty} \frac{a_n}{n^s}.$

Dirichlet series generating functions are especially useful for multiplicative functions, when they have an Euler product expression. If a_n is a Dirichlet character then its Dirichlet series generating function is called a Dirichlet L-series.

Polynomial sequence generating functions

The idea of generating functions can be extended to sequences of other objects. Thus, for example, polynomial sequences of binomial type are generated by

$e^{xf(t)}=\sum_{n=0}^\infty {p_n(x) \over n!}t^n$

where p_n(x) is a sequence of polynomials and f(t) is a function of a certain form. Sheffer sequences are generated in a similar way.