Generating functions

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

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

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

External links

• François Bergeron and Simon Plouffe, Computing the generating function of a series given its first few terms, Experimental Mathematics, Project Euclid.
• Simon Plouffe, MÉMOIRE DE MAÎTRISE: APPROXIMATIONS DE SÉRIES GÉNÉRATRICES ET QUELQUES CONJECTURES, 1992.
• Simon Plouffe, OEIS conjectured formulas. (a list of conjectured formulas for generating functions of OEIS sequences, for 37619 unique sequences out of 184755 processed sequences, a hit rate of 20.36 %, and more than 124800 expressions, as of Feb 17 2011)^{[dead link]}
• Simon Plouffe, Percentage of sequences automatically detected in the OEIS database. (33826 formulas for generating functions, out of 185000 sequences, a percentage of 18.26% of success, as of Feb 11 2011)^{[dead link]}
• Wikipedia, Generating function
• Herbert S. Wilf, generatingfunctionology, 2^nd ed., 1994.