Definition:Generating Function
Definition
Let $A = \sequence {a_n}$ be a sequence in $\R$.
Then $\ds \map {G_A} z = \sum_{n \mathop \ge 0} a_n z^n$ is called the generating function for the sequence $A$.
The mapping $\map {G_A} z$ is defined for all $z$ for which the power series $\ds \sum_{n \mathop \ge 0} a_n z^n$ is convergent.
The definition can be modified so that the lower limit of the summation is $b$ where $b > 0$ by assigning $a_k = 0$ where $0 \le k < b$.
Parameter
Let $\map {G_A} z$ be a generating function for the sequence $A$.
The variable $z$ is a bound variable, known as the parameter of $\map {G_A} z$.
Extraction of Coefficient
Let $\map G z$ be the generating function for the sequence $S = \sequence {a_n}$.
The coefficient of $z^n$ extracted from $\map G z$ is the $n$th term of $S$, and can be denoted:
- $\sqbrk {z^n} \map G z := a_n$
Doubly Subscripted Sequence
Let $A = \sequence {a_{m, n} }$ be a doubly subscripted sequence in $\R$ for $m, n \in \Z_{\ge 0}$.
Then $\ds \map {G_A} {w, z} = \sum_{m, \, n \mathop \ge 0} a_{m n} w^m z^n$ is called the generating function for the sequence $A$.
Also denoted as
When the sequence is understood, the notation $\map G z$ can be used for its generating function.
Different authors may use different symbols for $G_A$, for example:
- $\map {f_A} z$
- $\map U s$
- $\map A x$
- $\map {\mathrm f} t$
The symbol used for the parameter varies.
$x$ is often used instead.
In the field of probability theory $s$ tends to be the symbol of choice.
Some authors use $\zeta$, and some use $t$.
Also known as
A generating function is also known as an enumerating series, particularly in problems of combinatorics.
Also see
- Results about generating functions can be found here.
Historical Note
Generating functions were introduced by Abraham de Moivre to solve the general problem of linear recurrences.
James Stirling then extended this theory in his Methodus Differentialis of $1730$, by using differentiation and integration.
Then Leonhard Paul Euler began extending their use to new fields such as combinatorics.
Pierre-Simon de Laplace took the technique into the field of probability theory in his $1812$ work Théorie Analytique des Probabilités
Many others since have developed the technique further.
- A generating function is a clothesline on which we hang up a sequence of numbers for display.
- -- 1990: Herbert S. Wilf: generatingfunctionology
Sources
- 1956: G. Pólya: On Picture-Writing (Amer. Math. Monthly Vol. 63: pp. 689 – 697) www.jstor.org/stable/2309555
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {3-4}$ Generating Functions: Definition $\text {3-3}$
- 1986: Geoffrey Grimmett and Dominic Welsh: Probability: An Introduction ... (previous) ... (next): $\S 4.1$: Generating functions
- 1994: Herbert S. Wilf: generatingfunctionology (2nd ed.)
- 1994: Ronald L. Graham, Donald E. Knuth and Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science (2nd ed.) $\S 1.2$
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.8$: Fibonacci Numbers
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.9$: Generating Functions: $(1)$
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): generating function
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): generating function