Generating Functions - Core Definitions

Generating functions provide a powerful algebraic tool for encoding sequences as formal power series. This transformation allows us to apply techniques from analysis and algebra to solve discrete problems, bridging the gap between combinatorics and continuous mathematics.

DefinitionOrdinary Generating Function

The ordinary generating function (OGF) for a sequence $\{a_n\}_{n=0}^{\infty}$ is the formal power series: $G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$

We treat this as a formal object without worrying about convergence, though analytic properties become relevant in many applications.

The term "formal" means we manipulate these series algebraically without concern for convergence. The variable $x$ serves as a placeholder marking position in the sequence.

ExampleBasic Generating Functions

Several fundamental sequences have simple generating functions:

Constant sequence $(1, 1, 1, \ldots)$ : $G(x) = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$
Natural numbers $(0, 1, 2, 3, \ldots)$ : $G(x) = \sum_{n=0}^{\infty} nx^n = \frac{x}{(1-x)^2}$
Powers of 2 $(1, 2, 4, 8, \ldots)$ : $G(x) = \sum_{n=0}^{\infty} 2^n x^n = \frac{1}{1-2x}$
Binomial coefficients $\binom{n}{k}$ for fixed $k$ : The $n$ -th coefficient of $(1+x)^n$ is $\binom{n}{k}x^k$ .

DefinitionExponential Generating Function

The exponential generating function (EGF) for a sequence $\{a_n\}_{n=0}^{\infty}$ is: $\hat{G}(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} = a_0 + a_1 x + a_2 \frac{x^2}{2!} + a_3 \frac{x^3}{3!} + \cdots$

EGFs are particularly useful for counting labeled structures where order matters.

The factorial denominators in EGFs naturally account for the number of ways to arrange labeled objects, making them ideal for permutation problems.

DefinitionOperations on Generating Functions

Given sequences $\{a_n\}$ and $\{b_n\}$ with generating functions $A(x)$ and $B(x)$ :

Addition: $A(x) + B(x)$ generates $\{a_n + b_n\}$
Multiplication: $A(x) \cdot B(x)$ generates $\left\{\sum_{k=0}^{n} a_k b_{n-k}\right\}$ (convolution)
Scalar multiplication: $cA(x)$ generates $\{ca_n\}$
Shifting: $x^m A(x)$ generates $(0, 0, \ldots, 0, a_0, a_1, \ldots)$ with $m$ zeros
Differentiation: $A'(x)$ generates $\{(n+1)a_{n+1}\}$

Remark

The convolution property is particularly powerful: the product of generating functions corresponds to the convolution of sequences. This transforms summations into algebraic operations. For instance, to count the number of ways to select objects from two different collections, we multiply their generating functions. This principle underlies the use of generating functions in partition theory, where we encode the ways to write integers as sums.

Generating functions transform sequence problems into problems about functions, where we can leverage our intuition and tools from calculus and algebra to obtain results that would be difficult to derive directly.