Generating function transformation

In mathematics a transformation of a <a href="/facts/Sequence/gV2S4uqp">sequence's</a> <a href="/facts/Generating_function/K7UVjnjL">generating function</a> 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 <a href="/facts/Derivative/7Ito70Dh">higher-order derivatives</a> of these functions (see derivative transformations).
Given a sequence, 
 
 
 
 {
 
 f
 
 n
 
 
 
 }
 
 n
 =
 0
 
 
 ∞
 
 
 
 
 {\displaystyle \{f_{n}\}_{n=0}^{\infty }}
 
, the <a href="/facts/Generating_function/K7UVjnjL">ordinary generating function</a> (OGF) of the sequence, denoted 
 
 
 
 F
 (
 z
 )
 
 
 {\displaystyle F(z)}
 
, and the <a href="/facts/Generating_function/K7UVjnjL">exponential generating function</a> (EGF) of the sequence, denoted 
 
 
 
 
 
 
 F
 ^
 
 
 
 (
 z
 )
 
 
 {\displaystyle {\widehat {F}}(z)}
 
, are defined by the <a href="/facts/Formal_power_series/CNmaG0Vk">formal power series</a>

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 <a href="/facts/Generating_function/K7UVjnjL">main article</a> gives examples of generating functions for many sequences. Other examples of generating function variants include <a href="/facts/Dirichlet_generating_function/K7UVjnjL">Dirichlet generating functions</a> (DGFs), <a href="/facts/Lambert_series/HFU5HfCR">Lambert series</a>, and <a href="/facts/Newton_series/aY1txFhj">Newton series</a>. In this article we focus on transformations of generating functions in mathematics and keep a running list of useful transformations and transformation formulas.

Generating function transformation open-in-new

Generating function transformation