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]\!]$, the rig of formal power series over the rig $R$ (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) = \sum_{n=0}^{\infty}f_n z^n.$

If $R$ 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 $r \ge 0$ and if there’s an analytic continuation; if so, then we also say that the continuation is the generating function.

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

Multiplying generating functions in the same variable gives

(2)$\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 $f$ structure on the first part and the $g$ 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 + \frac{z^2}{2!} + \frac{z^3}{3!} + \cdots ,$

while the generating function for being a finite ordered set is

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

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

(5)$\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)$ and then set $x_i = p_i^{-s},$ where $p_i$ is the $i$th prime, then we get

(6)$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.$

The product of two Dirichlet generating functions gives

(7)$\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 $f$ to the first and $g$ to the second.

Sometimes we take the *exponents* on $z$ to be in a rig other than the natural numbers. For example, we might set $z^a \cdot z^b = z^{\max(a,b)}$ and $(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)$ for binary trees (rooted in the plane, counted by number of internal nodes) satisfies $T(z) = 1 + z T(z)^2$, which can be solved as $T(z) = \frac{1-\sqrt{1-4z}}{2z}$. The coefficient of $z^n$ in $T(z)$ is the $n$th *Catalan number* $\binom{2n}{n}/(n+1)$.

Fixed-point free involutions on a set have the EGF $e^{z^2/2}$, while arbitrary involutions have EGF $e^{z+z^2/2}$, and partitions have EGF $e^{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
(176.189.43.179)