Generating function

From Wikipedia, the free encyclopedia

This article is about generating functions in mathematics. For generating functions in classical mechanics, see Generating function (physics).

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.

[edit] Definitions

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

— Herbert Wilf, Generatingfunctionology (1994)

[edit] 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.$

[edit] 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!}.$

[edit] Poisson generating function

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

[edit] 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.

[edit] Bell series

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

[edit] 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}.$

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.

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

[edit] Examples

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

[edit] Ordinary generating function

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

[edit] Exponential generating function

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

[edit] Bell series

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

[edit] Dirichlet series generating function

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

[edit] Another example

Generating functions can be created by extending simpler generating functions. For example, starting with

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

and replacing $x$ with $2 x$ , we obtain

$G(1;2x)=\frac{1}{1-2x} = 1+(2x)+(2x)^2+\cdots+(2x)^n+\cdots=G(2^n;x).$

[edit] A more detailed example — Fibonacci numbers

Consider the problem of finding a closed formula for the Fibonacci numbers F_n defined by F₀ = 0, F₁ = 1, and F_n = F_n−1 + F_n−2 for n ≥ 2. We form the ordinary generating function

$f = \sum_{n \ge 0} F_n x^n$

for this sequence. The generating function for the sequence (F_n−1) is xf and that of (F_n−2) is x²f. From the recurrence relation, we therefore see that the power series xf + x²f agrees with f except for the first two coefficients. Taking these into account, we find that

$f = xf + x^2 f + x . \,\!$

(This is the crucial step; recurrence relations can almost always be translated into equations for the generating functions.) Solving this equation for f, we get

$f = \frac{x} {1 - x - x^2} .$

The denominator can be factored using the golden ratio φ₁ = (1 + √5)/2 and φ₂ = (1 − √5)/2, and the technique of partial fraction decomposition yields

$f = \frac{1}{\sqrt{5}} \left (\frac{1}{1-\phi_1 x} - \frac{1} {1- \phi_2 x} \right ) .$

These two formal power series are known explicitly because they are geometric series; comparing coefficients, we find the explicit formula

$F_n = \frac{1} {\sqrt{5}} (\phi_1^n - \phi_2^n).$

[edit] Applications

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.

[edit] Other generating functions

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

[edit] See also

[edit] References

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

[edit] External links

Retrieved from "http://en.wikipedia.org../../../g/e/n/Generating_function.html"

Categories: Combinatorics | Exponentials

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Generating function

From Wikipedia, the free encyclopedia

Contents

[edit] Definitions

[edit] Ordinary generating function

[edit] Exponential generating function

[edit] Poisson generating function

[edit] Lambert series

[edit] Bell series

[edit] Dirichlet series generating functions

[edit] Polynomial sequence generating functions

[edit] Examples

[edit] Ordinary generating function

[edit] Exponential generating function

[edit] Bell series

[edit] Dirichlet series generating function

[edit] Another example

[edit] A more detailed example — Fibonacci numbers

[edit] Applications

[edit] Other generating functions

[edit] See also

[edit] References

[edit] External links

Views

Navigation

Search

In other languages