In mathematics a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function (see integral transformations) or weighted sums over the higher-order derivatives of these functions (see derivative transformations).
Given a sequence, , the ordinary generating function (OGF) of the sequence, denoted , and the exponential generating function (EGF) of the sequence, denoted , are defined by the formal power series:
In this article, we use the convention that the ordinary (exponential) generating function for a sequence is denoted by the uppercase function / for some fixed or formal when the context of this notation is clear. Additionally, we use the bracket notation for coefficient extraction from the Concrete Mathematics reference which is given by . The main article gives examples of generating functions for many sequences. Other examples of generating function variants include Dirichlet generating functions (DGFs), Lambert series, and Newton series. In this article we focus on transformations of generating functions in mathematics and keep a running list of useful transformations and transformation formulas.
Extracting arithmetic progressions of a sequence
Series multisection provides formulas for generating functions enumerating the sequence given an ordinary generating function where , , and . In the first two cases where , we can expand these arithmetic progression generating functions directly in terms of :
More generally, suppose that and that denotes the primitive root of unity. Then we have the following formula,See Section 1.2.9 in Knuth's The Art of Computer Programming (Vol. 1). often known as the root of unity filter:
For integers , another useful formula providing somewhat reversed floored arithmetic progressions are generated by the identitySolution to exercise 7.36 on page 569 in Graham, Knuth and Patashnik.
Powers of an OGF and composition with functions
The exponential Bell polynomials, , are defined by the exponential generating functionSee section 3.3 in Comtet.
The next formulas for powers, logarithms, and compositions of formal power series are expanded by these polynomials with variables in the coefficients of the original generating functions.See sections 3.3–3.4 in Comtet.See section 1.9(vi) in the NIST Handbook. The formula for the exponential of a generating function is given implicitly through the Bell polynomials by the EGF for these polynomials defined in the previous formula for some sequence of .
Reciprocals of an OGF (special case of the powers formula)
The power series for the reciprocal of a generating function, , is expanded by
If we let denote the coefficients in the expansion of the reciprocal generating function, then we have the following recurrence relation:
Powers of an OGF
Let be fixed, suppose that , and denote . Then we have a series expansion for given by
and the coefficients satisfy a recurrence relation of the form
Another formula for the coefficients, , is expanded by the Bell polynomials as
where denotes the Pochhammer symbol.
Logarithms of an OGF
If we let and define , then we have a power series expansion for the composite generating function given by
where the coefficients, , in the previous expansion satisfy the recurrence relation given by
and a corresponding formula expanded by the Bell polynomials in the form of the power series coefficients of the following generating function:
Faà di Bruno's formula
Let denote the EGF of the sequence, , and suppose that is the EGF of the sequence, . Faà di Bruno's formula implies that the sequence, , generated by the composition , can be expressed in terms of the exponential Bell polynomials as follows:
Integral transformations
OGF ⟷ EGF conversion formulas
We have the following integral formulas for which can be applied termwise with respect to when is taken to be any formal power series variable:See page 566 of Graham, Knuth and Patashnik for the statement of the last conversion formula.
Notice that the first and last of these integral formulas are used to convert between the EGF to the OGF of a sequence, and from the OGF to the EGF of a sequence whenever these integrals are convergent.
The first integral formula corresponds to the Laplace transform (or sometimes the formal Laplace–Borel transformation) of generating functions, denoted by , defined in.See Appendix B.13 of Flajolet and Sedgewick. Other integral representations for the gamma function in the second of the previous formulas can of course also be used to construct similar integral transformations. One particular formula results in the case of the double factorial function example given immediately below in this section. The last integral formula is compared to Hankel's loop integral for the reciprocal gamma function applied termwise to the power series for .
Example: A double factorial integral for the EGF of the Stirling numbers of the second kind
The single factorial function, , is expressed as a product of two double factorial functions of the form
where an integral for the double factorial function, or rational gamma function, is given by
for natural numbers . This integral representation of then implies that for fixed non-zero and any integral powers , we have the formula
Thus for any prescribed integer , we can use the previous integral representation together with the formula for extracting arithmetic progressions from a sequence OGF given above, to formulate the next integral representation for the so-termed modified Stirling number EGF as
which is convergent provided suitable conditions on the parameter .Refer to the proof of Theorem 2.3 in Math.NT/1609.02803.
Example: An EGF formula for the higher-order derivatives of the geometric series
For fixed non-zero defined such that , let the geometric series over the non-negative integral powers of be denoted by . The corresponding higher-order derivatives of the geometric series with respect to are denoted by the sequence of functions
for non-negative integers . These derivatives of the ordinary geometric series can be shown, for example by induction, to satisfy an explicit closed-form formula given by
for any whenever . As an example of the third OGF EGF conversion formula cited above, we can compute the following corresponding exponential forms of the generating functions :
Fractional integrals and derivatives
Fractional integrals and fractional derivatives (see the main article) form another generalized class of integration and differentiation operations that can be applied to the OGF of a sequence to form the corresponding OGF of a transformed sequence. For we define the fractional integral operator (of order ) by the integral transformationSee section 1.15(vi)–(vii) in the NIST Handbook.
which corresponds to the (formal) power series given by
For fixed defined such that , we have that the operators . Moreover, for fixed and integers satisfying we can define the notion of the fractional derivative satisfying the properties that
and
for
where we have the semigroup property that only when none of is integer-valued.
Polylogarithm series transformations
For fixed , we have that (compare to the special case of the integral formula for the Nielsen generalized polylogarithm function defined in) See equation (4) in section 2 of Borwein, Borwein and Girgensohn's article Explicit evaluation of Euler sums (1994).
Notice that if we set , the integral with respect to the generating function, , in the last equation when corresponds to the Dirichlet generating function, or DGF, , of the sequence of provided that the integral converges. This class of polylogarithm-related integral transformations is related to the derivative-based zeta series transformations defined in the next sections.
Square series generating function transformations
For fixed non-zero such that and , we have the following integral representations for the so-termed square series generating function associated with the sequence , which can be integrated termwise with respect to :See the article Math.NT/1609.02803.
This result, which is proved in the reference, follows from a variant of the double factorial function transformation integral for the Stirling numbers of the second kind given as an example above. In particular, since
we can use a variant of the positive-order derivative-based OGF transformations defined in the next sections involving the Stirling numbers of the second kind to obtain an integral formula for the generating function of the sequence, , and then perform a sum over the derivatives of the formal OGF, to obtain the result in the previous equation where the arithmetic progression generating function at hand is denoted by
for each fixed .
Hadamard products and diagonal generating functions
We have an integral representation for the Hadamard product of two generating functions, and , stated in the following form:
where i is the imaginary unit.
More information about Hadamard products as diagonal generating functions of multivariate sequences and/or generating functions and the classes of generating functions these diagonal OGFs belong to is found in Stanley's book.See section 6.3 in Stanley's book. The reference also provides nested coefficient extraction formulas of the form
which are particularly useful in the cases where the component sequence generating functions, , can be expanded in a Laurent series, or fractional series, in , such as in the special case where all of the component generating functions are rational, which leads to an algebraic form of the corresponding diagonal generating function.
Example: Hadamard products of rational generating functions
In general, the Hadamard product of two rational generating functions is itself rational.See section 2.4 in Lando's book. This is seen by noticing that the coefficients of a rational generating function form quasi-polynomial terms of the form
where the reciprocal roots, , are fixed scalars and where is a polynomial in for all . For example, the Hadamard product of the two generating functions
and
is given by the rational generating function formula
Example: Factorial (approximate Laplace) transformations
Ordinary generating functions for generalized factorial functions formed as special cases of the generalized rising factorial product functions, or Pochhammer k-symbol, defined by
where is fixed, , and denotes the Pochhammer symbol are generated (at least formally) by the Jacobi-type J-fractions (or special forms of continued fractions) established in the reference. If we let denote the convergent to these infinite continued fractions where the component convergent functions are defined for all integers by
and
where denotes an associated Laguerre polynomial, then we have that the convergent function, , exactly enumerates the product sequences, , for all . For each , the convergent function is expanded as a finite sum involving only paired reciprocals of the Laguerre polynomials in the form of
Moreover, since the single factorial function is given by both and , we can generate the single factorial function terms using the approximate rational convergent generating functions up to order . This observation suggests an approach to approximating the exact (formal) Laplace–Borel transform usually given in terms of the integral representation from the previous section by a Hadamard product, or diagonal-coefficient, generating function. In particular, given any OGF we can form the approximate Laplace transform, which is -order accurate, by the diagonal coefficient extraction formula stated above given by