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 $\{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 $\{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 $\{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 $\{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 $\{a_{n}\}_{n=1}^{\infty }\,$ .

Note that we can't generate an $a_{0}\,$ term since $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 $\{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 $\{a_{n}\}_{n=1}^{\infty }\,$ .

Note that we can't generate an $a_{0}\,$ term since $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 $\{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 $\{a_{n}\}_{n=0}^{\infty }\,$ is a function $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 $\{a_{n}\}_{n=0}^{\infty }\,$ .

## Logarithmic derivative of exponential generating functions

The logarithmic derivative of exponential generating function (LGDEGF or lgdegf) for a sequence $\{a_{n}\}_{n=0}^{\infty }\,$ is a function $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 $\{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

$D_{\{a_{n}\}}(s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}},\,$ which generates (enumerates) the sequence $\{a_{n}\}_{n=1}^{\infty }\,$ .

Note that we can't generate an $a_{0}\,$ term since $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)\,$ where $\zeta (s)\,$ is the zeta function, generates (enumerates) the sequence $\{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 $\mu (n)\,$ is the Möbius function, it implies that, ${\frac {1}{\zeta (s)}}\,$ is the Dirichlet generating function of the Möbius function $\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 $(1+x)^{n}\,$ is the generating function for binomial coefficients for a fixed $n\,$ , one may ask for a bivariate generating function that generates the binomial coefficients ${\binom {n}{k}}\,$ for all $n\,$ and $k\,$ .

To do this, consider $(1+x)^{n}\,$ as itself a series (in $n\,$ ), and find the generating function in $y\,$ that has these as coefficients. Since the generating function for $a^{n}\,$ is just ${\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}\,$ 