This site is supported by donations to The OEIS Foundation.

# Generating functions

(Redirected from Maclaurin series 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.