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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G_{\{a_n\}}(x) \equiv \sum_{n=0}^{\infty} a_n \, x^n, \,}

which generates (enumerates) the sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \{a_n\}_{n=0}^{\infty} \,} .

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G_{\{n^0\}}(x) = G_{\{1^n\}}(x) = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \,}

generates (enumerates) the sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E_{\{a_n\}}(x) \equiv \sum_{n=0}^{\infty} a_n \, \frac{x^n}{n!}, \,}

which generates (enumerates) the sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \{a_n\}_{n=0}^{\infty} \,} .

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E_{\{n^0\}}(x) = E_{\{1^n\}}(x) = \sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x \,}

generates (enumerates) the sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L_{\{a_n\}}(x) \equiv \sum_{n=1}^{\infty} a_n \, \frac{(-1)^{n+1} \, x^n}{n}, \,}

which generates (enumerates) the sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \{a_n\}_{n=1}^{\infty} \,} .

Note that we can't generate an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle a_0 \,} term since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \,} , obviously, cannot be 0.

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle LH_{\{a_n\}}(x) \equiv \sum_{n=1}^{\infty} a_n \, \frac{x^n}{n}, \,}

which generates (enumerates) the sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \{a_n\}_{n=1}^{\infty} \,} .

Note that we can't generate an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle a_0 \,} term since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \{a_n\}_{n=0}^{\infty} \,} is a function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle f(x) \,} s.t.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \{a_n\}_{n=0}^{\infty} \,} is a function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle f(x) \,} s.t.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D_{\{a_n\}}(s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s}, \,}

which generates (enumerates) the sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \{a_n\}_{n=1}^{\infty} \,} .

Note that we can't generate an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle a_0 \,} term since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \,} , obviously, cannot be 0.

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D_{\{n^0\}}(s) = D_{\{1^n\}}(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \zeta(s) \,}

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \zeta(s) \,} is the zeta function, generates (enumerates) the sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{1}{\zeta(s)} = \sum_{n=1}^{\infty} \frac{\mu(n)}{n^s}, \,}

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \mu(n) \,} is the Möbius function, it implies that, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \frac{1}{\zeta(s)} \,} is the Dirichlet generating function of the Möbius function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle (1+x)^n \,} is the generating function for binomial coefficients for a fixed Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \,} , one may ask for a bivariate generating function that generates the binomial coefficients Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \binom{n}{k} \,} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \,} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle k \,} .

To do this, consider Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle (1+x)^n \,} as itself a series (in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \,} ), and find the generating function in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle y \,} that has these as coefficients. Since the generating function for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle a^n \,} is just Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \frac{1}{1-ay} \,} , the generating function for the binomial coefficients is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 \,}

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.