In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series.
Every sequence in principle has a generating function of each type (except that Lambert and Dirichlet series require indices to start at 1 rather than 0), but the ease with which they can be handled may differ considerably.
Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem.
He applied this mathematical tool to several problems in Combinatory Analysis and the Theory of Numbers.A generating function is a device somewhat similar to a bag.
One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers.
[3] Another benefit of exponential generating functions is that they are useful in transferring linear recurrence relations to the realm of differential equations.
and its derivatives can readily be shown to satisfy the differential equation EF″(x) = EF′(x) + EF(x) as a direct analogue with the recurrence relation above.
The main article provides several more classical, or at least well-known examples related to special arithmetic functions in number theory.
We see that for non-identically zero convolution families, this definition is equivalent to requiring that the sequence have an ordinary generating function of the first form given above.
Moreover, we can use matrix methods (as in the reference) to prove that given two convolution polynomial sequences, ⟨ fn(x) ⟩ and ⟨ gn(x) ⟩, with respective corresponding generating functions, F(z)x and G(z)x, then for arbitrary t we have the identity
By squaring the initial generating function, or by finding the derivative of both sides with respect to x and making a change of running variable n → n + 1, one sees that the coefficients form the sequence 1, 2, 3, 4, 5, ..., so one has
so that we can form the analogous generating functions over the integral mth powers generalizing the result in the square case above.
The differentiation–multiplication operation of the second identity can be repeated k times to multiply the sequence by nk, but that requires alternating between differentiation and multiplication.
For integers m ≥ 1, another useful formula providing somewhat reversed floored arithmetic progressions — effectively repeating each coefficient m times — are generated by the identity[16]
for all large enough n ≥ n0 and where the ĉi(n) are fixed finite-degree polynomials in n. In other words, the properties that a sequence be P-recursive and have a holonomic generating function are equivalent.
The reverse can also hold; often the radius of convergence for a generating function can be used to deduce the asymptotic growth of the underlying sequence.
Multivariate generating functions arise in practice when calculating the number of contingency tables of non-negative integers with specified row and column totals.
Expansions of (formal) Jacobi-type and Stieltjes-type continued fractions (J-fractions and S-fractions, respectively) whose hth rational convergents represent 2h-order accurate power series are another way to express the typically divergent ordinary generating functions for many special one and two-variate sequences.
The particular form of the Jacobi-type continued fractions (J-fractions) are expanded as in the following equation and have the next corresponding power series expansions with respect to z for some specific, application-dependent component sequences, {abi} and {ci}, where z ≠ 0 denotes the formal variable in the second power series expansion given below:[21]
The next table provides examples of closed-form formulas for the component sequences found computationally (and subsequently proved correct in the cited references[22]) in several special cases of the prescribed sequences, jn, generated by the general expansions of the J-fractions defined in the first subsection.
In particular, suppose that we seek the total number of ways (denoted Un) to tile a 3-by-n rectangle with unmarked 2-by-1 domino pieces.
Let the auxiliary sequence, Vn, be defined as the number of ways to cover a 3-by-n rectangle-minus-corner section of the full rectangle.
Thus by performing algebraic simplifications to the sequence resulting from the second partial fractions expansions of the generating function in the previous equation, we find that U2n + 1 ≡ 0 and that
Multiplication of generating functions, or convolution of their underlying sequences, can correspond to a notion of independent events in certain counting and probability scenarios.
Similarly, the number of ways to pay n ≥ 0 cents in coin denominations of values in the set {1, 5, 10, 25, 50} (i.e., in pennies, nickels, dimes, quarters, and half dollars, respectively) is generated by the product
In particular, this sequence has the combinatorial interpretation as being the number of ways to insert parentheses into the product x0 · x1 ·⋯· xn so that the order of multiplication is completely specified.
provides an overview of the congruences for these numbers derived strictly from properties of their generating function as in Section 4.6 of Wilf's stock reference Generatingfunctionology.
We repeat the basic argument and notice that when reduces modulo 2, these finite product generating functions each satisfy
Similarly, we can reduce the right-hand-side products defining the Stirling number generating functions modulo 3 to obtain slightly more complicated expressions providing that
There are also integral formulas for converting between a sequence's OGF, F(z), and its exponential generating function, or EGF, F̂(z), and vice versa given by