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

${\displaystyle G_{\{a_{n}\}}(x)\equiv \sum _{n=0}^{\infty }a_{n}\,x^{n},\,}$

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

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

${\displaystyle G_{\{n^{0}\}}(x)=G_{\{1^{n}\}}(x)=\sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}\,}$

generates (enumerates) the sequence ${\displaystyle \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

${\displaystyle E_{\{a_{n}\}}(x)\equiv \sum _{n=0}^{\infty }a_{n}\,{\frac {x^{n}}{n!}},\,}$

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

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

${\displaystyle E_{\{n^{0}\}}(x)=E_{\{1^{n}\}}(x)=\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}=e^{x}\,}$

generates (enumerates) the sequence ${\displaystyle \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

${\displaystyle L_{\{a_{n}\}}(x)\equiv \sum _{n=1}^{\infty }a_{n}\,{\frac {(-1)^{n+1}\,x^{n}}{n}},\,}$

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

Note that we can't generate an ${\displaystyle \scriptstyle a_{0}\,}$ term since ${\displaystyle \scriptstyle n\,}$, obviously, cannot be 0.

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

${\displaystyle 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 ${\displaystyle \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

${\displaystyle LH_{\{a_{n}\}}(x)\equiv \sum _{n=1}^{\infty }a_{n}\,{\frac {x^{n}}{n}},\,}$

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

Note that we can't generate an ${\displaystyle \scriptstyle a_{0}\,}$ term since ${\displaystyle \scriptstyle n\,}$, obviously, cannot be 0.

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

${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \scriptstyle \{a_{n}\}_{n=0}^{\infty }\,}$ is a function ${\displaystyle \scriptstyle f(x)\,}$ s.t.

${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \scriptstyle \{a_{n}\}_{n=0}^{\infty }\,}$ is a function ${\displaystyle \scriptstyle f(x)\,}$ s.t.

${\displaystyle 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 ${\displaystyle \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]

${\displaystyle D_{\{a_{n}\}}(s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}},\,}$

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

Note that we can't generate an ${\displaystyle \scriptstyle a_{0}\,}$ term since ${\displaystyle \scriptstyle n\,}$, obviously, cannot be 0.

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

${\displaystyle D_{\{n^{0}\}}(s)=D_{\{1^{n}\}}(s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\zeta (s)\,}$ [2]

where ${\displaystyle \scriptstyle \zeta (s)\,}$ is the zeta function, generates (enumerates) the sequence ${\displaystyle \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

${\displaystyle {\frac {1}{\zeta (s)}}=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n^{s}}},\,}$

where ${\displaystyle \scriptstyle \mu (n)\,}$ is the Möbius function, it implies that, ${\displaystyle \scriptstyle {\frac {1}{\zeta (s)}}\,}$ is the Dirichlet generating function of the Möbius function ${\displaystyle \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 ${\displaystyle \scriptstyle (1+x)^{n}\,}$ is the generating function for binomial coefficients for a fixed ${\displaystyle \scriptstyle n\,}$, one may ask for a bivariate generating function that generates the binomial coefficients ${\displaystyle \scriptstyle {\binom {n}{k}}\,}$ for all ${\displaystyle \scriptstyle n\,}$ and ${\displaystyle \scriptstyle k\,}$.

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

${\displaystyle 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 ${\displaystyle \scriptstyle s\,}$ is considered real or complex.