6.3 Operations on generating functions

Generating functions operations

Operations on generating functions let you build new sequences from old ones using algebra. Addition, multiplication, and composition each have a direct combinatorial meaning, and mastering these operations is what makes generating functions so useful for counting.

Addition and Multiplication

Addition combines two generating functions by adding coefficients of like powers. 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$.

$$(1 + 2x + 3x^2) + (4 + 5x + 6x^2) = 5 + 7x + 9x^2$$

Combinatorially, this corresponds to counting the union of two disjoint sets. If $a_n$ counts one type of object of size $n$ and $b_n$ counts another, then $a_n + b_n$ counts both types together.

Multiplication is more interesting. The product $A(x) \cdot B(x)$ has coefficients given by the Cauchy product (also called convolution):

$$c_n = \sum_{k=0}^{n} a_k \, b_{n-k}$$

This formula says: to build an object of size $n$, choose some size $k$ for the first part and size $n - k$ for the second, then multiply the number of choices. For example:

$$(1 + 2x)(3 + 4x) = 3 + 4x + 6x + 8x^2 = 3 + 10x + 8x^2$$

The coefficient of $x^1$ is $1 \cdot 4 + 2 \cdot 3 = 10$, which is exactly the Cauchy product at $n = 1$.

A classic application: if you roll two dice, the generating function for a single die is $x + x^2 + x^3 + x^4 + x^5 + x^6$. Squaring this gives a generating function whose coefficient of $x^n$ counts the number of ways to roll a sum of $n$.

Composition and Advanced Operations

Composition means substituting one generating function into another. Given $F(x)$ and $G(x)$ with $G(0) = 0$ (this condition matters for convergence in the formal power series setting), you form $F(G(x))$ by replacing every $x$ in $F$ with $G(x)$.

For example, if $F(x) = 1 + x + x^2$ and $G(x) = 2x$, then:

$$F(G(x)) = 1 + 2x + (2x)^2 = 1 + 2x + 4x^2$$

Composition is especially useful for nested or hierarchical combinatorial structures, like placing objects into groups that are themselves arranged in some pattern.

All of these operations live inside the formal power series ring $\mathbb{R}[[x]]$, which is closed under addition, multiplication, and (with the right conditions) composition. "Formal" means you don't worry about whether the series converges numerically. You treat $\sum a_n x^n$ as a purely algebraic object. That said, when you do want numerical answers (e.g., using $\frac{1}{1-x} = \sum_{n \geq 0} x^n$), convergence for $|x| < 1$ becomes relevant.

Solving counting problems

Application of Basic Operations

Each operation translates a combinatorial idea into algebra:

• Addition handles disjoint unions. If set $A$ has generating function $A(x)$ and set $B$ has $B(x)$, and $A \cap B = \emptyset$, then $A \cup B$ has generating function $A(x) + B(x)$.
• Multiplication handles Cartesian products (independent choices). Choosing a shirt from 3 options and pants from 2 options gives $3 \times 2 = 6$ outfits. In generating function terms, you're multiplying the two functions.
• Composition handles substitution into structures. For instance, counting ways to partition objects into groups, where each group is itself structured, often requires composing the generating function for the group structure into the one for the overall arrangement.

Coefficient extraction is how you read off answers. The notation $[x^n] F(x)$ means "the coefficient of $x^n$ in $F(x)$." For example, $[x^n] \frac{1}{1 - x - x^2}$ gives the $n$th Fibonacci number (with appropriate initial conditions), since the Fibonacci recurrence $f_n = f_{n-1} + f_{n-2}$ translates directly into that rational generating function.

Advanced Techniques

Partial fraction decomposition breaks a rational generating function into simpler pieces whose coefficients you can read off directly.

For example, to extract coefficients from $\frac{1}{(1-x)(1-2x)}$:

1. Decompose: $\frac{1}{(1-x)(1-2x)} = \frac{A}{1-x} + \frac{B}{1-2x}$
2. Solve for $A$ and $B$: you get $A = -1$, $B = 2$
3. Expand each fraction as a geometric series: $[x^n] = -1 \cdot 1^n + 2 \cdot 2^n = 2^{n+1} - 1$

The Lagrange inversion theorem handles implicit equations where a generating function is defined in terms of itself. If $T(x) = x \, \phi(T(x))$ for some known function $\phi$, Lagrange inversion gives you a formula for $[x^n] T(x)$. This is particularly powerful for tree enumeration. For instance, the equation $T(x) = x(1 + T(x))^2$ counts a family of rooted trees, and Lagrange inversion extracts the coefficients without needing to solve for $T$ explicitly.

Pattern recognition also saves work. Knowing common generating functions lets you spot answers quickly:

• $\frac{1}{(1-x)^2} = \sum_{n \geq 0} (n+1) x^n$, generating the sequence $1, 2, 3, 4, \ldots$
• $\frac{1}{(1-x)^k}$ generates $\binom{n+k-1}{k-1}$, which counts multisets of size $n$ from $k$ types

Deriving generating functions

Modification Techniques

These techniques let you transform a known generating function into one for a related sequence.

Shifting (multiplying by $x^m$) shifts the sequence by $m$ positions. If $F(x) = \sum_{n \geq 0} a_n x^n$, then $x \cdot F(x) = \sum_{n \geq 1} a_{n-1} x^n$. This is useful when a recurrence involves shifted indices.

Differentiation produces weighted sequences. Since:

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

differentiating $\frac{1}{1-x}$ gives $\frac{1}{(1-x)^2} = \sum_{n \geq 0} (n+1) x^n$. Differentiation corresponds combinatorially to "marking" or distinguishing one element in a structure. Integration reverses this, dividing coefficients by $n+1$, which can be thought of as "unmarking" a distinguished element.

Variable substitution transforms indices. Replacing $x$ with $x^2$ in $\frac{1}{1-x} = \sum x^n$ gives $\frac{1}{1-x^2} = \sum x^{2n}$, which generates the sequence $1, 0, 1, 0, 1, \ldots$ (nonzero only at even indices).

Multiplying by a geometric series can also be useful. For instance:

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

This recovers the all-ones sequence from the alternating-index sequence.

Advanced Derivation Methods

The Hadamard product $A(x) \odot B(x) = \sum a_n b_n x^n$ gives the term-by-term product of two sequences. Unlike ordinary multiplication (which gives convolution), the Hadamard product multiplies corresponding coefficients directly. It's less common but useful when you need element-wise combination of sequences.

Functional equations translate recurrences into generating function equations. The classic example is the Catalan numbers, defined by $C_0 = 1$ and $C_{n+1} = \sum_{k=0}^{n} C_k C_{n-k}$. The convolution in that recurrence becomes ordinary multiplication:

$$C(x) = 1 + x \, C(x)^2$$

Solving this quadratic in $C(x)$ gives $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$.

Exponential generating functions (EGFs) require adjusted rules. If $\hat{A}(x) = \sum a_n \frac{x^n}{n!}$, then multiplication of EGFs corresponds to the binomial convolution $c_n = \sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}$, which counts ways to split a labeled set of size $n$ into two parts and apply separate structures to each. The exponential formula $\hat{F}(x) = \exp(\hat{G}(x))$ connects the EGF for connected structures $G$ to the EGF for sets of those structures $F$. For example, this relates connected graphs to all graphs, or cycles to permutations.

Operations vs combinatorial interpretations

Combinatorial Meanings of Basic Operations

Each algebraic operation on generating functions has a precise combinatorial counterpart:

Convolution deserves extra emphasis. When you multiply two OGFs, the coefficient $c_n = \sum_{k} a_k b_{n-k}$ counts ways to partition $n$ into two parts and independently choose structures on each part. This is exactly what happens when distributing $n$ indistinguishable objects into two distinct bins with constraints encoded by $A(x)$ and $B(x)$.

Advanced Interpretations and Applications

The exponential formula is one of the deepest connections between operations and combinatorics. If $\hat{C}(x)$ is the EGF for connected structures, then $\exp(\hat{C}(x))$ is the EGF for sets of those structures. This single identity lets you count labeled forests from labeled trees, permutations from cycles, and set partitions from blocks.

Functional equations reveal recursive structure. The equation $C(x) = x + C(x)^2$ for (a shifted version of) binary trees says: a binary tree is either a single node ($x$) or a pair of binary trees joined at a root ($C(x)^2$). The algebraic equation directly mirrors the recursive definition of the combinatorial object. Reading functional equations this way often provides the most intuitive route to setting them up correctly.