Ordinary and Exponential Generating Functions

Generating functions transform combinatorial problems into algebraic ones by encoding sequences as formal power series. The choice between ordinary and exponential generating functions depends on the combinatorial structure being counted.

DefinitionOrdinary Generating Function (OGF)

For a sequence $\{a_n\}_{n=0}^\infty$ , the ordinary generating function is: $A(x) = \sum_{n=0}^\infty a_n x^n$

OGFs are natural for counting unordered structures, such as:

Partitions of integers
Compositions (ordered partitions)
Paths in graphs
Solutions to linear recurrences

DefinitionExponential Generating Function (EGF)

For a sequence $\{a_n\}_{n=0}^\infty$ , the exponential generating function is: $A(x) = \sum_{n=0}^\infty a_n \frac{x^n}{n!}$

EGFs are natural for counting labeled structures where order matters, such as:

Permutations with restricted patterns
Labeled graphs and trees
Set partitions
Arrangements with symmetries

The key difference is that OGF multiplication gives convolution $c_n = \sum_{k=0}^n a_k b_{n-k}$ , while EGF multiplication gives $c_n = \sum_{k=0}^n \binom{n}{k} a_k b_{n-k}$ , which counts ways to partition an $n$ -set and apply operations to each part.

ExampleBasic OGF Examples

Geometric series: $\frac{1}{1-x} = \sum_{n=0}^\infty x^n$ (counts $a_n = 1$ for all $n$ )
Binomial series: $(1+x)^k = \sum_{n=0}^k \binom{k}{n} x^n$ (finite) or $(1+x)^\alpha = \sum_{n=0}^\infty \binom{\alpha}{n} x^n$ (for $|x| < 1$ )
Fibonacci numbers: If $F_n$ satisfies $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0, F_1 = 1$ , then: $F(x) = \sum_{n=0}^\infty F_n x^n = \frac{x}{1-x-x^2}$
Catalan numbers: $C(x) = \frac{1-\sqrt{1-4x}}{2x}$ satisfies $C(x) = 1 + xC(x)^2$

ExampleBasic EGF Examples

Exponential function: $e^x = \sum_{n=0}^\infty \frac{x^n}{n!}$ (counts all permutations, $a_n = n!$ )
Permutations: The EGF for $a_n = n!$ is $\frac{1}{1-x} = \sum_{n=0}^\infty \frac{n! x^n}{n!}$
Derangements: $D(x) = \frac{e^{-x}}{1-x} = e^{-x} \cdot \sum_{n=0}^\infty x^n$ gives: $D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$
Bell numbers: The EGF is $B(x) = e^{e^x - 1}$ , encoding all set partitions

Remark

The product principle differs between OGF and EGF:

OGF: If $A(x) = \sum a_n x^n$ and $B(x) = \sum b_n x^n$ , then $A(x)B(x) = \sum c_n x^n$ where $c_n = \sum_{k=0}^n a_k b_{n-k}$ .
EGF: If $A(x) = \sum a_n \frac{x^n}{n!}$ and $B(x) = \sum b_n \frac{x^n}{n!}$ , then $A(x)B(x) = \sum c_n \frac{x^n}{n!}$ where $c_n = \sum_{k=0}^n \binom{n}{k} a_k b_{n-k}$ .

The binomial coefficient in EGF multiplication counts ways to select which elements get the first operation vs. the second.

DefinitionCommon Operations

Key operations on generating functions:

Addition: $(A+B)(x) = A(x) + B(x)$ corresponds to disjoint union
Multiplication: $(AB)(x) = A(x)B(x)$ corresponds to Cartesian product (with appropriate interpretation)
Differentiation: $A'(x) = \sum_{n=1}^\infty n a_n x^{n-1}$ shifts indices
Integration: $\int A(x)dx = \sum_{n=0}^\infty \frac{a_n}{n+1} x^{n+1}$
Substitution: $A(B(x))$ for composition of structures (requires $B(0) = 0$ for OGF)

ExampleSolving Recurrences with Generating Functions

Find a closed form for $a_n = 3a_{n-1} - 2a_{n-2}$ with $a_0 = 1, a_1 = 1$ .

Let $A(x) = \sum_{n=0}^\infty a_n x^n$ . Multiply the recurrence by $x^n$ and sum: $\sum_{n=2}^\infty a_n x^n = 3\sum_{n=2}^\infty a_{n-1} x^n - 2\sum_{n=2}^\infty a_{n-2} x^n$

This gives: $A(x) - a_0 - a_1 x = 3x(A(x) - a_0) - 2x^2 A(x)$ $A(x) - 1 - x = 3x A(x) - 3x - 2x^2 A(x)$ $A(x)(1 - 3x + 2x^2) = 1 - 2x$

Thus: $A(x) = \frac{1-2x}{(1-x)(1-2x)} = \frac{1}{1-x} - \frac{x}{1-2x} = \sum_{n=0}^\infty x^n - \sum_{n=0}^\infty 2^n x^{n+1}$

Comparing coefficients: $a_n = 1$ for $n = 0$ and $a_n = 1 - 2^n$ for $n \geq 1$ .

Generating functions provide a unified framework connecting combinatorics, algebra, analysis, and number theory through the language of formal power series.