Citizendia

This article is about generating functions in mathematics. For generating functions in classical mechanics, see Generating function (physics). Generating functions which arise in Hamiltonian mechanics are quite different from Generating functions in mathematics For Signalling molecule, see Epidermal growth factor. Epidermal growth factor or EGF is a Growth factor that plays an important role in the regulation of Cell growth, Proliferation, and

In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics, formal power series are devices that make it possible to employ much of the analytical machinery of Power series in settings that do not In Mathematics, a sequence is an ordered list of objects (or events In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an

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. In Mathematics, the domain of a given function is the set of " Input " values for which the function is defined In Mathematics, the codomain, or target, of a function f: X → Y is the set

Contents

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 an 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. Herbert Saul Wilf (born 1931) is a Mathematician, specializing in Combinatorics.

If an is the probability mass function of a discrete random variable, then its ordinary generating function is called a probability-generating function. In Probability theory, a probability mass function (abbreviated pmf) is a function that gives the probability that a discrete Random variable In Probability theory, a Probability distribution is called discrete if it is characterized by a Probability mass function. In Probability theory, the probability-generating function of a Discrete random variable is a Power series representation (the Generating function

The ordinary generating function can be generalized to sequences with multiple indexes. For example, the ordinary generating function of a sequence am,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 an is

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

Poisson generating function

The Poisson generating function of a sequence an is

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

Lambert series

The Lambert series of a sequence an 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. In Mathematics, a Lambert series, named for Johann Heinrich Lambert, is a series taking the form S(q=\sum_{n=1}^\infty a_n \frac {q^n}{1-q^n}

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.

Dirichlet series generating functions

Dirichlet series are often classified as generating functions, although they are not strictly formal power series. In Mathematics, the Bell series is a Formal power series used to study properties of arithmetical functions In Number theory an arithmetic function or arithmetical function is a Function defined on the set of Natural numbers (i In Mathematics, a Dirichlet series is any series of the form \sum_{n=1}^{\infty} \frac{a_n}{n^s} where s and The Dirichlet series generating function of a sequence an is

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

The Dirichlet series generating function is especially useful when an 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 an is a Dirichlet character then its Dirichlet series generating function is called a Dirichlet L-series. Outside number theory the term multiplicative function is usually used for Completely multiplicative functions This article discusses number theoretic multiplicative In Number theory, an Euler product is an Infinite product expansion indexed by Prime numbers p, of a Dirichlet series. In Number theory, Dirichlet characters are certain Arithmetic functions which arise from Completely multiplicative characters on the units of In mathematics a Dirichlet L -series, named in honour of Johann Peter Gustav Lejeune Dirichlet, is a function of the form L(s\chi = \sum_{n=1}^\infty

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 pn(x) is a sequence of polynomials and f(t) is a function of a certain form. In Mathematics, a Polynomial sequence, ie a sequence of Polynomials indexed by { 0 1 2 3. Sheffer sequences are generated in a similar way. In Mathematics, a Sheffer sequence is a Polynomial sequence, i See the main article generalized Appell polynomials for more information. In Mathematics, a Polynomial sequence \{p_n(z \} has a generalized Appell representation if the Generating function for the Polynomials

Examples

Main article: Examples of generating functions

When working with generating functions, it is important to recogise the expressions of some fundamenal sequences. The following examples are in the spirit of George Pólya, who advocated learning mathematics by doing and re-capitulating as many examples and proofs as possible

Ordinary generating functions

The most fundamental of all is the constant sequence 1,1,1,1,. . . , whose ordinary generating function is

\sum_{n\in\mathbf{N}}X^n={1\over1-X}.

The right hand side expression can be justified by multiplying the power series on the left by X − 1, and checking that ther result is the constant power series 1, in other words that all coefficients vanish, except the one of X0. (Moreover there can be no other power series with this property, since a power series ring like Z[[X]] is an integral domain. In Abstract algebra, a branch of Mathematics, an integral domain is a Commutative ring with an additive identity 0 and a multiplicative identity 1 such ) The right hand side therefore designates the inverse of X − 1 in the ring of power series.

Expressions for the ordinary generating of other sequences are easily derived for this one. For instance for the geometric series 1,a,a2,a3,. In Mathematics, a geometric series is a series with a constant ratio between successive terms. . . for any constant a one has

\sum_{n\in\mathbf{N}}a^nX^n={1\over1-aX},

and in particular

\sum_{n\in\mathbf{N}}(-1)^nX^n={1\over1+X}.

On can also introduce regular "gaps" in the sequence by replacing X by some power, of X, so for instance for the sequence 1,0,1,0,1,0,1,0,. . . . one gets the generating function

\sum_{n\in\mathbf{N}}X^{2n}={1\over1-X^2}.

Computing the square of the initial generating function, one easily sees that the coefficients form the sequence 1,2,3,4,5,. . . , so one has

\sum_{n\in\mathbf{N}}(n+1)X^n={1\over(1-X)^2},

and the third power has as coefficients the triangular numbers 1,3,6,10,15,21,. A triangular number is the sum of the n Natural numbers from 1 to n. . . whose term n is the binomial coefficient \tbinom{n+2}2, so that

\sum_{n\in\mathbf{N}}\tbinom{n+2}2 X^n={1\over(1-X)^3}.

Since \tbinom{n+2}2=\frac12{(n+1)(n+2)} =\frac12(n^2+3n+2) one can find the ordinary generating function for the sequence 0,1,4,9,16,. In Mathematics, the binomial coefficient \tbinom nk is the Coefficient of the x   k term in the Polynomial . . of square numbers by linear combination of the preceding sequences;

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

Exponential generating function

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

Bell series

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

Dirichlet series generating function

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

Applications

Generating functions are used to

Other generating functions

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

See also

References

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic