Generating function

From Wikipedia, the free encyclopedia

(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, including ordinary generating functions, exponential generating functions, Lambert series, Bell series, and Dirichlet series; 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.

It is important to note that generating functions are not functions in the formal sense of a mapping from a domain to a codomain; the name merely stems from the historical study of the structures.

1 Definitions
2 Examples
3 Applications
4 Other generating functions
5 See also
6 References
7 External links

A generating function is a clothesline on which we hang up a sequence of numbers for display.

— Herbert Wilf, Generatingfunctionology (1994)

The ordinary generating function of a sequence a_n is

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

When the term 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 generalized 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.$

The exponential generating function of a sequence a_n is

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

The Poisson generating function of a sequence a_n is

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

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.

The Bell series of an arithmetic function f(n) and a prime p is

$f_p(x)=\sum_{n=0}^\infty f(p^n)x^n.$

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}.$

The Dirichlet series generating function is especially useful when a_n is a multiplicative function, when it has an Euler product expression in terms of the function's Bell series

$DG(a_n;s)=\prod_{p} f_p(p^{-s})\,.$

If a_n is a Dirichlet character then its Dirichlet series generating function is called a Dirichlet L-series.

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. See the main article generalized Appell polynomials for more information.

Main article: Examples of generating functions

A few brief examples follow.

Generating functions for the sequence of square numbers a_n = n² are:

$G(n^2;x)=\sum_{n=0}^{\infty}n^2x^n=\frac{x(x+1)}{(1-x)^3}$

$EG(n^2;x)=\sum _{n=0}^{\infty} \frac{n^2x^n}{n!}=x(x+1)e^x$

$f_p(x)=\sum_{n=0}^\infty p^{2n}x^n=\frac{1}{1-p^2x}$

$DG(n^2;s)=\sum_{n=1}^{\infty} \frac{n^2}{n^s}=\zeta(s-2)$

Generating functions are used to

Find recurrence relations for sequences – the form of a generating function may suggest a recurrence formula.
Find relationships between sequences – if the generating functions of two sequences have a similar form, then the sequences themselves are probably related.
Explore the asymptotic behaviour of sequences.
Prove identities involving sequences.
Solve enumeration problems in combinatorics.
Evaluate infinite sums.

Examples of polynomial sequences generated by more complex generating functions include:

Herbert S. Wilf, Generatingfunctionology (Second Edition) (1994) Academic Press. ISBN 0-12-751956-4.

Donald E. Knuth, The Art of Computer Programming, Volume 1 Fundamental Algorithms (Third Edition) Addison-Wesley. ISBN 0-201-89683-4. Section 1.2.9: Generating Functions, pp.87–96.

Ronald L. Graham, Donald E. Knuth, Oren Parashnik, Concrete Mathematics. A foundation for computer science (Second Edition) Addison-Wesley. ISBN 0-201-55802-5. Chapter 7: Generating Functions, pp. 320–380

Generating Functions, Power Indices and Coin Change at cut-the-knot
Generatingfunctionology (PDF)
Ignacio Larrosa Cañestro, León-Sotelo, Marko Riedel, Georges Zeller, Suma de números equilibrados, newsgroup es.ciencia.matematicas
Frederick Lecue; Riedel, Marko, et al., Permutation, Les-Mathematiques.net, in French, title somewhat misleading.

Retrieved from "http://en.wikipedia.org/wiki/Generating_function"

Categories: Combinatorics | Exponentials

Searching reference...

Reference

Sources

Generating function

From Wikipedia, the free encyclopedia

Contents

Top Matching Results

Sponsored Links
This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Searching reference...

Reference

Sources

Generating function

From Wikipedia, the free encyclopedia

Contents

Top Matching Results

Sponsored Links This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Sponsored Links
This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.