generating function

This entry is about the generating functions in the sense of algebraic combinatorics. For another notion see generating function in classical mechanics.



A generating function is an element of R[[z]]R[\![z]\!], the rig of formal power series over the rig RR (which is often taken to be the natural numbers or the rational numbers), used for purposes of combinatorics. A general element takes the form

(1)f(z)= n=0 f nz n.f(z) = \sum_{n=0}^{\infty}f_n z^n.

If RR is taken to be the real numbers or the complex numbers (or any subrig), then we can ask whether the power series has a radius of convergence r0r \ge 0 and if there’s an analytic continuation; if so, then we also say that the continuation is the generating function.

When R=,R = \mathbb{N}, we can think of the coefficients on z nz^n as counting the number of ways to put a particular structure on the finite set nn. (You get structure types if you take this literally.)

Multiplying generating functions in the same variable gives

(2)( n=0 f nz n)( n=0 g nz n)= n=0 k=0 nf kg nkz n, \left(\sum_{n=0}^{\infty}f_n z^n\right)\left(\sum_{n=0}^{\infty}g_n z^n\right) = \sum_{n=0}^{\infty}\sum_{k=0}^n f_k g_{n-k} z^n,

which effectively says to split up the set into two parts, put the ff structure on the first part and the gg structure on the second part.

Ordinary generating functions (OGFs) describe structures on totally ordered sets, while exponential generating functions (EGFs) apply to unordered sets (whose elements may be distinguished by having different labels). For example, the generating function for being an unordered finite set is

(3)e z=1+z+z 22!+z 33!+, e^z = 1 + z + \frac{z^2}{2!} + \frac{z^3}{3!} + \cdots ,

while the generating function for being a finite ordered set is

(4)11z=1+z+z 2+z 3+. \frac{1}{1-z} = 1 + z + z^2 + z^3 + \cdots .

If we assume that the zeroth term is 11, then multiplying generating functions in different variables gives

(5)( n=0 f nx n)( n=0 g nz n)=1+(f 1x+g 1z)+(f 2x 2+f 1g 1xz+g 2z 2)+ \left(\sum_{n=0}^{\infty}f_n x^n\right)\left(\sum_{n=0}^{\infty}g_n z^n\right) = 1 + (f_1 x + g_1 z) + (f_2 x^2 + f_1 g_1 x z + g_2 z^2) + \cdots

If we take the product of countably many generating functions f i(x i)f^i(x_i) and then set x i=p i s,x_i = p_i^{-s}, where p ip_i is the iith prime, then we get

(6)1 s+f 1 12 s+f 1 23 s+f 2 14 s+f 1 35 s+f 1 1f 1 26 s++ if e i i(p i e i) s+, 1^{-s} + f^1_1 2^{-s} + f^2_1 3^{-s} + f^1_2 4^{-s} + f^3_1 5^{-s} + f^1_1 f^2_1 6^{-s} + \cdots + \prod_{i} f^i_{e_i} (p_i^{e_i})^{-s} + \cdots,

which is called the Dirichlet generating function for the family f i.f^i.

The product of two Dirichlet generating functions gives

(7)( n=1 f nn s)( n=1 g nn s)= n=1 d|nf dg n/dn s, \left(\sum_{n=1}^{\infty}f_n n^{-s}\right)\left(\sum_{n=1}^{\infty}g_n n^{-s}\right) = \sum_{n=1}^{\infty} \sum_{d|n} f_d g_{n/d} n^{-s},

which effectively says to factor the term into two dimensions, apply ff to the first and gg to the second.

Sometimes we take the exponents on zz to be in a rig other than the natural numbers. For example, we might set z az b=z max(a,b)z^a \cdot z^b = z^{\max(a,b)} and (z a) b=z a+b;(z^a)^b = z^{a+b}; such a system lets us talk about the cost of operations done in parallel (max) or sequentially (+). Similarly, we could take the exponents to be binary string?s when considering instantaneous codes, or finite field elements when considering structures on a finite collection of objects.


The OGF T(z)T(z) for binary trees (rooted in the plane, counted by number of internal nodes) satisfies T(z)=1+zT(z) 2T(z) = 1 + z T(z)^2, which can be solved as T(z)=114z2zT(z) = \frac{1-\sqrt{1-4z}}{2z}. The coefficient of z nz^n in T(z)T(z) is the nnth Catalan number (2nn)/(n+1)\binom{2n}{n}/(n+1).

Fixed-point free involutions on a set have the EGF e z 2/2e^{z^2/2}, while arbitrary involutions have EGF e z+z 2/2e^{z+z^2/2}, and partitions have EGF e e z1e^{e^z-1}.

In quantum field theory generating functions often appear as partition functions and vacuum amplitudes as functions of source fields.


  • Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, CUP, 2009. (author pdf)

Revised on September 10, 2015 06:18:29 by Noam Zeilberger (