6.1 Ordinary generating functions

Ordinary generating functions

An ordinary generating function (OGF) encodes an entire sequence of numbers into a single algebraic expression. Instead of working with a sequence term by term, you package it into a power series and then use algebra to discover properties of the sequence that would be hard to spot otherwise. OGFs are one of the central tools in combinatorics for solving counting problems, proving identities, and finding closed-form expressions.

Definition and Structure

The ordinary generating function for a sequence $a_0, a_1, a_2, a_3, \ldots$ 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$

Each term of the sequence becomes the coefficient of the corresponding power of $x$. The variable $x$ is just a placeholder; you're not plugging in actual numbers. That's why these are called formal power series: convergence doesn't matter. You never need to worry about whether the series "adds up" to a finite value. You just manipulate the expressions algebraically.

A key fact is the uniqueness property: two formal power series are equal if and only if every corresponding coefficient matches. So each sequence determines exactly one OGF, and each OGF determines exactly one sequence.

Properties and Operations

The real power of OGFs comes from the fact that algebraic operations on the generating functions correspond to natural operations on the sequences they encode.

Addition. If $A(x) = \sum a_n x^n$ and $B(x) = \sum b_n x^n$, then

$A(x) + B(x) = \sum (a_n + b_n) x^n$

You just add the sequences term by term. Straightforward.

Multiplication (Cauchy product). This is where things get interesting. The product $A(x) \cdot B(x)$ gives a new series whose coefficient of $x^n$ is the convolution:

$[x^n]\, A(x) B(x) = \sum_{k=0}^{n} a_k \, b_{n-k}$

Combinatorially, this counts the number of ways to split $n$ into two parts and choose from set $A$ for one part and set $B$ for the other. Multiplication of OGFs is the algebraic version of combining independent choices.

Shifting. To shift a sequence to the right (inserting zeros at the front), multiply by a power of $x$. For example, $x^2 \cdot G(x)$ shifts the sequence two positions to the right. To shift left (removing initial terms), you subtract them off and divide:

$\frac{G(x) - a_0}{x} = a_1 + a_2 x + a_3 x^2 + \cdots$

Differentiation. Taking the derivative of $G(x)$ multiplies each coefficient by its index:

$G'(x) = \sum_{n=1}^{\infty} n \, a_n \, x^{n-1}$

So $x \cdot G'(x) = \sum n \, a_n \, x^n$, which is useful when your sequence involves factors of $n$.

Other operations:

• Hadamard product: multiplying corresponding terms $a_n b_n$ (not the same as the Cauchy product; this doesn't arise from simple multiplication of OGFs)
• Substitution/composition: replacing $x$ with another series $B(x)$ in $A(x)$, which enables more complex sequence constructions

Common Sequences and Their Generating Functions

A handful of OGFs show up constantly. Knowing these by heart saves a lot of time.

The constant sequence $(1, 1, 1, \ldots)$:

$\frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots$

This is the geometric series formula, treated formally. It's the single most important OGF to remember, because many others are built from it.

The geometric sequence $(1, a, a^2, a^3, \ldots)$:

$\frac{1}{1-ax} = \sum_{n=0}^{\infty} a^n x^n$

So the coefficient of $x^n$ in $\frac{1}{1-ax}$ is simply $a^n$.

Binomial coefficients. The generating function for the $n$th row of Pascal's triangle is:

$(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$

More generally, the generalized binomial series $(1-x)^{-r} = \sum_{n=0}^{\infty} \binom{n+r-1}{r-1} x^n$ gives the OGF for choosing with repetition.

Fibonacci numbers $(0, 1, 1, 2, 3, 5, 8, \ldots)$:

$F(x) = \frac{x}{1 - x - x^2}$

This comes directly from the recurrence $F_n = F_{n-1} + F_{n-2}$ with initial conditions $F_0 = 0, F_1 = 1$.

Catalan numbers $(1, 1, 2, 5, 14, 42, \ldots)$:

$C(x) = \frac{1 - \sqrt{1-4x}}{2x}$

Partition numbers. The number of ways to write $n$ as a sum of positive integers (order doesn't matter) is encoded by the infinite product:

$\prod_{k=1}^{\infty} \frac{1}{1 - x^k}$

Each factor $\frac{1}{1-x^k} = 1 + x^k + x^{2k} + \cdots$ accounts for using 0, 1, 2, ... copies of the part $k$.

Constructing Generating Functions

When you face a new counting problem, here's a general approach for building its OGF:

1. Identify the sequence. Write out the first several terms of whatever you're counting.
2. Look for a recurrence. If $a_n$ satisfies a recurrence relation (like $a_n = 2a_{n-1} + 3a_{n-2}$), multiply both sides by $x^n$, sum over all valid $n$, and express everything in terms of $G(x)$.
3. Solve for $G(x)$. The recurrence turns into an algebraic equation in $G(x)$. Solve it to get a closed-form expression.
4. Use combinatorial structure directly. If the problem involves independent choices (e.g., "pick items from several categories"), write a generating function for each category and multiply them together.

Example: Deriving the Fibonacci OGF.

Start with $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$, with $F_0 = 0, F_1 = 1$.

1. Define $F(x) = \sum_{n=0}^{\infty} F_n x^n$.

2. Multiply the recurrence by $x^n$ and sum from $n=2$ to $\infty$: $\sum_{n=2}^{\infty} F_n x^n = \sum_{n=2}^{\infty} F_{n-1} x^n + \sum_{n=2}^{\infty} F_{n-2} x^n$

3. Rewrite each side using $F(x)$:

   • Left side: $F(x) - F_0 - F_1 x = F(x) - x$
   • First sum on right: $x(F(x) - F_0) = xF(x)$
   • Second sum on right: $x^2 F(x)$

4. Solve: $F(x) - x = xF(x) + x^2 F(x)$, giving $F(x) = \frac{x}{1 - x - x^2}$.

This same strategy works for any linear recurrence with constant coefficients.

Interpreting Coefficients

Combinatorial Interpretations

The notation $[x^n] G(x)$ means "the coefficient of $x^n$ in $G(x)$." Reading off these coefficients is how you extract answers from a generating function.

Some important examples:

• $[x^n] \frac{1}{(1-x)^k} = \binom{n+k-1}{k-1}$. This counts the number of weak compositions of $n$ into $k$ nonneg­ative parts (equivalently, multisets of size $n$ from $k$ types).
• In a product $A(x) \cdot B(x)$, the coefficient $[x^n]$ counts the total number of ways to pick one structure of size $k$ from $A$ and one of size $n-k$ from $B$, summed over all $k$.
• When you impose restrictions on a counting problem (e.g., "each part is at most 3"), you modify the individual factors in the product accordingly.

Extraction Techniques

Once you have a closed-form OGF, you need to pull out the coefficient of $x^n$. The main techniques:

Partial fraction decomposition (for rational OGFs). If $G(x) = \frac{P(x)}{Q(x)}$ where $\deg P < \deg Q$, factor $Q(x)$ and decompose:

$\frac{P(x)}{(1 - r_1 x)(1 - r_2 x)} = \frac{A}{1 - r_1 x} + \frac{B}{1 - r_2 x}$

Then $[x^n] G(x) = A \cdot r_1^n + B \cdot r_2^n$. This is exactly how you derive the Binet formula for Fibonacci numbers.

Binomial series expansion. For OGFs involving square roots or fractional powers, use the generalized binomial theorem:

$(1 + x)^\alpha = \sum_{n=0}^{\infty} \binom{\alpha}{n} x^n$

where $\binom{\alpha}{n} = \frac{\alpha(\alpha-1)\cdots(\alpha-n+1)}{n!}$ for any real $\alpha$.

Taylor expansion. Expand around $x = 0$ using standard series identities.

Lagrange inversion. When $G(x)$ is defined implicitly (e.g., $G(x) = x \cdot \phi(G(x))$ for some function $\phi$), this theorem gives a formula for $[x^n] G(x)$ directly. The Catalan number OGF is a classic application.

Closed-Form Expressions for Sequences

Derivation Methods

The typical workflow for finding a closed-form expression for $a_n$:

1. Set up the OGF from a recurrence or combinatorial description.
2. Simplify the OGF into a recognizable closed form (rational function, product, etc.).
3. Decompose using partial fractions (for rational OGFs) or series expansions.
4. Extract the coefficient of $x^n$ from each term.
5. Verify by checking the formula against known initial values and the original recurrence.

For rational generating functions with distinct roots, the closed form will always be a linear combination of exponentials: $a_n = c_1 r_1^n + c_2 r_2^n + \cdots$. Repeated roots introduce polynomial factors like $n \cdot r^n$.

Advanced Techniques

These go beyond the basics but are worth knowing at this level:

• Kernel method: used for functional equations where $G(x)$ satisfies something like $G(x) = 1 + x \cdot G(x)^2$. You find a substitution that "kills" one side of the equation.
• Singularity analysis: to find the asymptotic behavior of $a_n$ (how it grows for large $n$), you analyze the singularities of $G(x)$ in the complex plane. The dominant singularity (closest to the origin) controls the growth rate.
• Darboux's method: a specific technique for extracting asymptotics from OGFs with algebraic singularities (like square roots).
• Riordan arrays: a framework that organizes families of sequences defined by related generating functions into infinite lower-triangular matrices, making certain recurrence patterns easier to handle.