This site is supported by donations to The OEIS Foundation.
Generating functions
From OeisWiki
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
which generates (enumerates) the sequence .
The ordinary generating function of the simplest sequence of positive integers, the all-1's sequence, is
generates (enumerates) the sequence 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
which generates (enumerates) the sequence .
The exponential generating function of the simplest sequence of positive integers, the all-1's sequence, is
generates (enumerates) the sequence 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
which generates (enumerates) the sequence .
Note that we can't generate an term since , obviously, cannot be 0.
The logarithmic generating function of the simplest sequence of positive integers, the all-1's sequence, is
generates (enumerates) the sequence 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
which generates (enumerates) the sequence .
Note that we can't generate an term since , obviously, cannot be 0.
The hyperbolic logarithmic generating function of the simplest sequence of positive integers, the all-1's sequence, is
generates (enumerates) the sequence 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 is a function s.t.
is the ordinary generating function of .
Logarithmic derivative of exponential generating functions
The logarithmic derivative of exponential generating function (LGDEGF or lgdegf) for a sequence is a function s.t.
is the exponential generating function of .
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]}
which generates (enumerates) the sequence .
Note that we can't generate an term since , obviously, cannot be 0.
The Dirichlet generating function of the simplest sequence of positive integers, the all-1's sequence, is
- ^{[2]}
where is the zeta function, generates (enumerates) the sequence 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
where is the Möbius function, it implies that, is the Dirichlet generating function of the Möbius function 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 is the generating function for binomial coefficients for a fixed , one may ask for a bivariate generating function that generates the binomial coefficients for all and .
To do this, consider as itself a series (in ), and find the generating function in that has these as coefficients. Since the generating function for is just , the generating function for the binomial coefficients is
See also
Notes
- ↑ Note that since these are formal power series, it doesn't matter whether is considered real or complex.
- ↑ Sondow, Jonathan and Weisstein, Eric W., Riemann Zeta Function, From MathWorld — A Wolfram Web Resource.
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)
- 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)
- Wikipedia, Generating function
- Herbert S. Wilf, generatingfunctionology, 2^{nd} ed., 1994.