This site is supported by donations to The OEIS Foundation.

# Generating functions

(Redirected from Generating function)

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

## 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 \,$

1. Note that since these are formal power series, it doesn't matter whether $\scriptstyle s \,$ is considered real or complex.