Generating function transformation

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, formula_1, the ordinary generating function (OGF) of the sequence, denoted formula_2, and the exponential generating function (EGF) of the sequence, denoted formula_3, are defined by the formal power series
In this article, we use the convention that the ordinary (exponential) generating function for a sequence formula_6 is denoted by the uppercase function formula_2 / formula_3 for some fixed or formal formula_9 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 formula_10.
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.
The focus of this section is to give formulas for generating functions enumerating the sequence formula_11 given an ordinary generating function formula_2 where formula_13, formula_14, and formula_15. In the first two cases where formula_16, we can expand these arithmetic progression generating functions directly in terms of formula_2:
More generally, suppose that formula_20 and that formula_21 denotes the formula_22 primitive root of unity. Then we have the formula
For integers formula_24, another useful formula providing somewhat "reversed" floored arithmetic progressions are generated by the identity
Powers of an OGF and composition with functions.
The exponential Bell polynomials, formula_26, are defined by the exponential generating function
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. 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 formula_28.
Reciprocals of an OGF (special case of the powers formula).
The power series for the reciprocal of a generating function, formula_2, is expanded by
If we let formula_31 denote the coefficients in the expansion of the reciprocal generating function, then we have the following recurrence relation:
Powers of an OGF.
Let formula_33 be fixed, suppose that formula_34, and denote formula_35. Then we have a series expansion for formula_36 given by
and the coefficients formula_38 satisfy a recurrence relation of the form
Another formula for the coefficients, formula_38, is expanded by the Bell polynomials as
where formula_42 denotes the Pochhammer symbol.
Logarithms of an OGF.
If we let formula_34 and define formula_44, then we have a power series expansion for the composite generating function given by
where the coefficients, formula_46, 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 formula_3 denote the EGF of the sequence, formula_50, and suppose that formula_51 is the EGF of the sequence, formula_52. The sequence, formula_53, generated by the exponential generating function for the composition, formula_54, is given in terms of the exponential Bell polynomials as follows:
We compare the statement of this result to the other known statement of Faà di Bruno's formula which provides an analogous expansion of the formula_56 derivatives of a composite function in terms of the derivatives of the two functions of formula_9 defined as above.
Integral transformations.
OGF ⟷ EGF conversion formulas.
We have the following integral formulas for formula_58 which can be applied termwise with respect to formula_9 when formula_9 is taken to be any formal power series variable:
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 formula_64, defined in. 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 formula_2.
Example: A double factorial integral for the EGF of the Stirling numbers of the second kind.
The single factorial function, formula_66, 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 formula_69. This integral representation of formula_70 then implies that for fixed non-zero formula_71 and any integral powers formula_72, we have the formula
Thus for any prescribed integer formula_74, 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 formula_76.
Example: An EGF formula for the higher-order derivatives of the geometric series.
For fixed non-zero formula_77 defined such that formula_78, let the geometric series over the non-negative integral powers of formula_79 be denoted by formula_80. The corresponding higher-order formula_81 derivatives of the geometric series with respect to formula_9 are denoted by the sequence of functions
for non-negative integers formula_74. These formula_81 derivatives of the ordinary geometric series can be shown, for example by induction, to satisfy an explicit closed-form formula given by
for any formula_74 whenever formula_78. As an example of the third OGF formula_89 EGF conversion formula cited above, we can compute the following corresponding "exponential" forms of the generating functions formula_90:
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 formula_92 we define the "fractional integral operator" (of order formula_93) by the integral transformation
which corresponds to the (formal) power series given by
For fixed formula_96 defined such that formula_97, we have that the operators formula_98. 
Moreover, for fixed formula_99 and integers formula_100 satisfying formula_101 we can define the notion of the "fractional derivative" satisfying the properties that
and
where we have the semigroup property that formula_105 only when none of formula_106 is integer-valued.
Polylogarithm series transformations.
For fixed formula_107, we have that (compare to the special case of the integral formula for the "Nielsen generalized polylogarithm function" defined in) 
Notice that if we set formula_109, the integral with respect to the generating function, formula_110, in the last equation when formula_111 corresponds to the Dirichlet generating function, or DGF, formula_112, of the sequence of formula_6 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 formula_114 such that formula_115 and formula_78, we have the following integral representations for the so-termed "square series" generating function associated with the sequence formula_6, which can be integrated termwise with respect to formula_9:
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, formula_121, and then perform a sum over the formula_81 derivatives of the formal OGF, formula_2 to obtain the result in the previous equation where the arithmetic progression generating function at hand is denoted by
for each fixed formula_125.
Hadamard products and diagonal generating functions.
We have an integral representation for the Hadamard product of two generating functions, formula_2 and formula_110, stated in the following form:
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. The reference also provides nested coefficient extraction formulas of the form
which are particularly useful in the cases where the component sequence generating functions, formula_130, can be expanded in a Laurent series, or fractional series, in formula_9, 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. This is seen by noticing that the coefficients of a rational generating function form "quasi-polynomial" terms of the form
where the reciprocal roots, formula_133, are fixed scalars and where formula_134 is a polynomial in formula_100 for all formula_136. 
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 formula_141 is fixed, formula_142, and formula_143 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 formula_144 denote the formula_145 convergent to these infinite continued fractions where the component convergent functions are defined for all integers formula_146 by
and
where formula_149 denotes an associated Laguerre polynomial, then we have that the formula_150 convergent function, formula_151, exactly enumerates the product sequences, formula_152, for all formula_153. For each formula_146, the formula_150 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 formula_157 and formula_158, we can generate the single factorial function terms using the approximate "rational" convergent generating functions up to order formula_159. 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 formula_110 we can form the approximate Laplace transform, which is formula_159-order accurate, by the diagonal coefficient extraction formula stated above given by
Examples of sequences enumerated through these diagonal coefficient generating functions arising from the sequence factorial function multiplier provided by the rational convergent functions include
where formula_164 denotes a modified Bessel function, formula_165 denotes the subfactorial function, formula_166 denotes the alternating factorial function, and formula_167 is a Legendre polynomial. Other examples of sequences enumerated through applications of these rational Hadamard product generating functions given in the article include the Barnes G-function, combinatorial sums involving the double factorial function, sums of powers sequences, and sequences of binomials.
Derivative transformations.
Positive and negative-order zeta series transformations.
For fixed formula_168, we have that if the sequence OGF formula_2 has formula_81 derivatives of all required orders for formula_171, that the "positive-order zeta series transformation" is given by
where formula_173 denotes a Stirling number of the second kind. 
In particular, we have the following special case identity when formula_174 when formula_175 denotes the triangle of first-order Eulerian numbers:
We can also expand the "negative-order zeta series transformations" by a similar procedure to the above expansions given in terms of the formula_81-order derivatives of some formula_178 and an infinite, non-triangular set of generalized Stirling numbers "in reverse", or generalized Stirling numbers of the second kind defined within this context.
In particular, for integers formula_179, define these generalized classes of Stirling numbers of the second kind by the formula
Then for formula_168 and some prescribed OGF, formula_178, i.e., so that the higher-order formula_81 derivatives of formula_2 exist for all formula_74, we have that
A table of the first few zeta series transformation coefficients, formula_187, appears below. These weighted-harmonic-number expansions are almost identical to the known formulas for the Stirling numbers of the first kind up to the leading sign on the weighted harmonic number terms in the expansions.
Examples of the negative-order zeta series transformations.
The next series related to the polylogarithm functions (the "dilogarithm" and "trilogarithm" functions, respectively), the alternating zeta function and the Riemann zeta function are formulated from the previous negative-order series results found in the references. In particular, when formula_188 (or equivalently, when formula_189 in the table above), we have the following special case series for the dilogarithm and corresponding constant value of the alternating zeta function:
When formula_191 (or when formula_192 in the notation used in the previous subsection), we similarly obtain special case series for these functions given by
It is known that the first-order harmonic numbers have a closed-form exponential generating function expanded in terms of the natural logarithm, the incomplete gamma function, and the exponential integral given by
Additional series representations for the r-order harmonic number exponential generating functions for integers formula_195 are formed as special cases of these negative-order derivative-based series transformation results. For example, the "second-order harmonic numbers" have a corresponding exponential generating function expanded by the series
Generalized negative-order zeta series transformations.
A further generalization of the negative-order series transformations defined above is related to more "Hurwitz-zeta-like", or "Lerch-transcendent-like", generating functions. Specifically, if we define the even more general parametrized Stirling numbers of the second kind by
for non-zero formula_96 such that formula_199, and some fixed formula_200, we have that
Moreover, for any integers formula_202, we have the partial series approximations to the full infinite series in the previous equation given by
Examples of the generalized negative-order zeta series transformations.
Series for special constants and zeta-related functions resulting from these generalized derivative-based series transformations typically involve the "generalized r-order harmonic numbers" defined by 
formula_204 for integers formula_205. A pair of particular series expansions for the following constants when formula_206 is fixed follow from special cases of BBP-type identities as
Several other series for the "zeta-function-related" cases of the Legendre chi function, the polygamma function, and the Riemann zeta function include
Additionally, we can give another new explicit series representation of the inverse tangent function through its relation to the Fibonacci numbers expanded as in the references by
for formula_210 and where the golden ratio (and its reciprocal) are respectively defined by formula_211.
Inversion relations and generating function identities.
Inversion relations.
An "inversion relation" is a pair of equations of the form
which is equivalent to the "orthogonality relation"
Given two sequences, formula_6 and formula_215, related by an inverse relation of the previous form, we sometimes seek to relate the OGFs and EGFs of the pair of sequences by functional equations implied by the inversion relation. This goal in some respects mirrors the more number theoretic (Lambert series) generating function relation guaranteed by the Möbius inversion formula, which provides that whenever
the generating functions for the sequences, formula_217 and formula_218, are related by the "Möbius transform" given by
Similarly, the "Euler transform" of generating functions for two sequences, formula_217 and formula_218, satisfying the relation
is given in the form of
where the corresponding inversion formulas between the two sequences is given in the reference.
The remainder of the results and examples given in this section sketch some of the more well-known generating function transformations provided by sequences related by inversion formulas (the binomial transform and the Stirling transform), and provides several tables of known inversion relations of various types cited in Riordan's "Combinatorial Identities" book. In many cases, we omit the corresponding functional equations implied by the inversion relationships between two sequences ("this part of the article needs more work").
The binomial transform.
The first inversion relation provided below implicit to the binomial transform is perhaps the simplest of all inversion relations we will consider in this section. For any two sequences, formula_6 and formula_215, related by the inversion formulas
we have functional equations between the OGFs and EGFs of these sequences provided by the binomial transform in the forms of
and
The Stirling transform.
For any pair of sequences, formula_6 and formula_215, related by the Stirling number inversion formula
these inversion relations between the two sequences translate into functional equations between the sequence EGFs given by the Stirling transform as
and
Tables of inversion pairs from Riordan's book.
These tables appear in chapters 2 and 3 in Riordan's book providing an introduction to inverse relations with many examples, though which does not stress functional equations between the generating functions of sequences related by these inversion relations. The interested reader is encouraged to pick up a copy of the original book for more details.
Gould classes of inverse relations.
The terms, formula_234 and formula_235, in the inversion formulas of the form
forming several special cases of "Gould classes of inverse relations" are given in the next table.
For classes 1 and 2, the range on the sum satisfies formula_237, and for classes 3 and 4 the bounds on the summation are given by formula_238. These terms are also somewhat simplified from their original forms in the table by the identities
The simpler Chebyshev inverse relations.
The so-termed "simpler" cases of the Chebyshev classes of inverse relations in the subsection below are given in the next table.
The formulas in the table are simplified somewhat by the following identities:
Additionally the inversion relations given in the table also hold when formula_242 in any given relation.
Chebyshev classes of inverse relations.
The terms, formula_234 and formula_235, in the inversion formulas of the form
for non-zero integers formula_246
forming several special cases of "Chebyshev classes of inverse relations" are given in the next table.
Additionally, these inversion relations also hold when formula_242 for some formula_248 or when the sign factor of formula_249 is shifted from the terms formula_235 to the terms formula_234. The formulas given in the previous table are simplified somewhat by the identities
Legendre–Chebyshev classes of inverse relations.
The "Legendre–Chebyshev classes of inverse relations" correspond to inversion relations of the form
where the terms, formula_234 and formula_235, implicitly depend on some fixed non-zero formula_256. In general, given a class of Chebyshev inverse pairs of the form
if formula_246 a prime, the substitution of formula_259, formula_260, and formula_261 (possibly replacing formula_262) leads to a "Legendre–Chebyshev" pair of the form
Similarly, if the positive integer formula_264 is composite, we can derive inversion pairs of the form
The next table summarizes several generalized classes of Legendre–Chebyshev inverse relations for some non-zero integer formula_246.
Abel inverse relations.
"Abel inverse relations" correspond to "Abel inverse pairs" of the form
where the terms, formula_268 and formula_269, may implicitly vary with some indeterminate summation parameter formula_270. 
These relations also still hold if the binomial coefficient substitution of formula_271 is performed for some non-negative integer formula_272. 
The next table summarizes several notable forms of these Abel inverse relations.
Inverse relations derived from ordinary generating functions.
If we let the "convolved Fibonacci numbers", formula_273, be defined by
we have the next table of inverse relations which are obtained from properties of ordinary sequence generating functions proved as in section 3.3 of Riordan's book.
Note that relations 3, 4, 5, and 6 in the table may be transformed according to the substitutions formula_275 and formula_276 for some fixed non-zero integer formula_277.
Inverse relations derived from exponential generating functions.
Let formula_278 and formula_279 denote the Bernoulli numbers and Euler numbers, respectively, and suppose that the sequences, formula_280, formula_281, and formula_282 are defined by the following exponential generating functions:
The next table summarizes several notable cases of inversion relations obtained from exponential generating functions in section 3.4 of Riordan's book.
Multinomial inverses.
The inverse relations used in formulating the binomial transform cited in the previous subsection are generalized to corresponding two-index inverse relations for sequences of two indices, and to multinomial inversion formulas for sequences of formula_284 indices involving the binomial coefficients in Riordan. 
In particular, we have the form of a two-index inverse relation given by
and the more general form of a multinomial pair of inversion formulas given by