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, { f n } n = 0 ∞ {\displaystyle \{f_{n}\}_{n=0}^{\infty }} , the ordinary generating function (OGF) of the sequence, denoted F ( z ) {\displaystyle F(z)} , and the exponential generating function (EGF) of the sequence, denoted F ^ ( z ) {\displaystyle {\widehat {F}}(z)} , are defined by the formal power series:
F ( z ) = ∑ n = 0 ∞ f n z n = f 0 + f 1 z + f 2 z 2 + ⋯ {\displaystyle F(z)=\sum _{n=0}^{\infty }f_{n}z^{n}=f_{0}+f_{1}z+f_{2}z^{2}+\cdots }
F ^ ( z ) = ∑ n = 0 ∞ f n n ! z n = f 0 0 ! + f 1 1 ! z + f 2 2 ! z 2 + ⋯ . {\displaystyle {\widehat {F}}(z)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}z^{n}={\frac {f_{0}}{0!}}+{\frac {f_{1}}{1!}}z+{\frac {f_{2}}{2!}}z^{2}+\cdots .}
In this article, we use the convention that the ordinary (exponential) generating function for a sequence { f n } {\displaystyle \{f_{n}\}} is denoted by the uppercase function F ( z ) {\displaystyle F(z)} / F ^ ( z ) {\displaystyle {\widehat {F}}(z)} for some fixed or formal z {\displaystyle z} 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 [ z n ] F ( z ) := f n {\displaystyle [z^{n}]F(z):=f_{n}} . 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 { f a n + b } {\displaystyle \{f_{an+b}\}} given an ordinary generating function F ( z ) {\displaystyle F(z)} where a , b ∈ N {\displaystyle a,b\in \mathbb {N} } , a ≥ 2 {\displaystyle a\geq 2} , and 0 ≤ b < a {\displaystyle 0\leq b<a} . In the first two cases where ( a , b ) := ( 2 , 0 ) , ( 2 , 1 ) {\displaystyle (a,b):=(2,0),(2,1)} , we can expand these arithmetic progression generating functions directly in terms of F ( z ) {\displaystyle F(z)} :
… excerpt ends here. Continue reading the full article.
