This site is supported by donations to The OEIS Foundation.

Generating functions

From OeisWiki

(Redirected from Generating function)
Jump to: navigation, search

A generating function is a formal power series of some given form that generates (enumerates) a sequence.

Contents

Ordinary generating functions

An ordinary generating function (OGF, ogf or o.g.f.,) i.e. a power series generating function, is a formal power series of the form

G_{\{a_n\}}(x) \equiv \sum_{n=0}^{\infty} a_n \, x^n, \,

which generates (enumerates) the sequence \scriptstyle \{a_n\}_{n=0}^{\infty} \,.

The ordinary generating function of the simplest sequence of positive integers, the all-1's sequence, is

G_{\{n^0\}}(x) = G_{\{1^n\}}(x) = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \,

generates (enumerates) the sequence \scriptstyle \{a_n\}_{n=0}^{\infty}\, equal to

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...}.

By generating function, one typically refers to ordinary generating function.

Exponential generating functions

An exponential generating function (EGF, egf or e.g.f.,) i.e. a Maclaurin series generating function, is a formal power series of the form

E_{\{a_n\}}(x) \equiv \sum_{n=0}^{\infty} a_n \, \frac{x^n}{n!}, \,

which generates (enumerates) the sequence \scriptstyle \{a_n\}_{n=0}^{\infty} \,.

The exponential generating function of the simplest sequence of positive integers, the all-1's sequence, is

E_{\{n^0\}}(x) = E_{\{1^n\}}(x) = \sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x \,

generates (enumerates) the sequence \scriptstyle \{a_n\}_{n=0}^{\infty}\, equal to

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...},

hence the term exponential generating function.

Logarithmic generating functions?

A logarithmic generating function (LGF, lgf or l.g.f.,) would be a formal power series of the form

L_{\{a_n\}}(x) \equiv \sum_{n=1}^{\infty} a_n \, \frac{(-1)^{n+1} \, x^n}{n}, \,

which generates (enumerates) the sequence \scriptstyle \{a_n\}_{n=1}^{\infty} \,.

Note that we can't generate an \scriptstyle a_0 \, term since \scriptstyle n \,, obviously, cannot be 0.

The logarithmic generating function of the simplest sequence of positive integers, the all-1's sequence, is

L_{\{n^0\}}(x) = L_{\{1^n\}}(x) = \sum_{n=1}^{\infty} \frac{(-1)^{n+1} \, x^n}{n} = \log(1+x) \,

generates (enumerates) the sequence \scriptstyle \{a_n\}_{n=1}^{\infty}\, equal to

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...}.

Hyperbolic logarithmic generating functions?

A hyperbolic logarithmic generating function would be a formal power series of the form

LH_{\{a_n\}}(x) \equiv \sum_{n=1}^{\infty} a_n \, \frac{x^n}{n}, \,

which generates (enumerates) the sequence \scriptstyle \{a_n\}_{n=1}^{\infty} \,.

Note that we can't generate an \scriptstyle a_0 \, term since \scriptstyle n \,, obviously, cannot be 0.

The hyperbolic logarithmic generating function of the simplest sequence of positive integers, the all-1's sequence, is

LH_{\{n^0\}}(x) = LH_{\{1^n\}}(x) = \sum_{n=1}^{\infty} \frac{x^n}{n} = \log(\tfrac{1}{1-x}) \,

generates (enumerates) the sequence \scriptstyle \{a_n\}_{n=1}^{\infty}\, equal to

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...},

(hence might be called hyperbolic logarithmic generating function by analogy with the term exponential generating function).

Logarithmic derivative of ordinary generating functions

The logarithmic derivative of ordinary generating function (LGDOGF or lgdogf) for a sequence \scriptstyle \{a_n\}_{n=0}^{\infty} \, is a function \scriptstyle f(x) \, s.t.

G_{\{a_n\}}(x) \equiv \sum_{n=0}^{\infty} a_n \, x^n = \exp\bigg(\int{f(x) dx}\bigg) \,

is the ordinary generating function of \scriptstyle \{a_n\}_{n=0}^{\infty} \,.

Logarithmic derivative of exponential generating functions

The logarithmic derivative of exponential generating function (LGDEGF or lgdegf) for a sequence \scriptstyle \{a_n\}_{n=0}^{\infty} \, is a function \scriptstyle f(x) \, s.t.

E_{\{a_n\}}(x) \equiv \sum_{n=0}^{\infty} a_n \, \frac{x^n}{n!} = \exp\bigg(\int{f(x) dx}\bigg) \,

is the exponential generating function of \scriptstyle \{a_n\}_{n=0}^{\infty} \,.

Dirichlet generating functions

A Dirichlet generating function (Dirichlet g.f.,) i.e. a Dirichlet series generating function, is a formal power series of the form[1]

D_{\{a_n\}}(s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s}, \,

which generates (enumerates) the sequence \scriptstyle \{a_n\}_{n=1}^{\infty} \,.

Note that we can't generate an \scriptstyle a_0 \, term since \scriptstyle n \,, obviously, cannot be 0.

The Dirichlet generating function of the simplest sequence of positive integers, the all-1's sequence, is

D_{\{n^0\}}(s) = D_{\{1^n\}}(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \zeta(s) \, [2]

where \scriptstyle \zeta(s) \, is the zeta function, generates (enumerates) the sequence \scriptstyle \{a_n\}_{n=1}^{\infty} \, equal to

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...},

(hence might have been called zeta generating functions by analogy with the term exponential generating function).

The Dirichlet generating function is very well suited for arithmetic functions (number-theoretic functions) since Euler's zeta function encapsulates information about the prime factorization of the natural numbers.

For example, since the reciprocal of Euler's zeta function is obtained by Möbius inversion

\frac{1}{\zeta(s)} = \sum_{n=1}^{\infty} \frac{\mu(n)}{n^s}, \,

where \scriptstyle \mu(n) \, is the Möbius function, it implies that, \scriptstyle \frac{1}{\zeta(s)} \, is the Dirichlet generating function of the Möbius function \scriptstyle \mu(n) \, for all positive integers.

Continued fraction generating functions

See examples for double factorial.

Multivariate generating functions

One can define generating functions in several variables, for series with several indices. These are referred to as multivariate generating functions (bivariate, trivariate, etc.).

Bivariate generating functions

Pascal's triangle bivariate generating function

For instance, since \scriptstyle (1+x)^n \, is the generating function for binomial coefficients for a fixed \scriptstyle n \,, one may ask for a bivariate generating function that generates the binomial coefficients \scriptstyle \binom{n}{k} \, for all \scriptstyle n \, and \scriptstyle k \,.

To do this, consider \scriptstyle (1+x)^n \, as itself a series (in \scriptstyle n \,), and find the generating function in \scriptstyle y \, that has these as coefficients. Since the generating function for \scriptstyle a^n \, is just \scriptstyle \frac{1}{1-ay} \,, the generating function for the binomial coefficients is

G_{\{\binom{n}{k}\}}(x, y) = \frac{1}{1-(1+x)y} = \sum_{n=0}^{\infty} (1+x)^n ~ y^n = \sum_{n=0}^{\infty} \sum_{k=0}^{n} \binom{n}{k} ~ x^k y^n \,

See also

Notes

  1. Note that since these are formal power series, it doesn't matter whether \scriptstyle s \, is considered real or complex.
  2. Sondow, Jonathan and Weisstein, Eric W., Riemann Zeta Function, From MathWorld — A Wolfram Web Resource.

External links

Personal tools