Generating Functions

Encoding Sequences as Power Series

A generating function encodes a sequence $a_0, a_1, a_2, \ldots$ as a formal power series: $A(x) = a_0 + a_1 x + a_2 x^2 + \cdots = \sum_{n=0}^{\infty} a_n x^n$

We manipulate $A(x)$ algebraically — multiplication, differentiation, partial fractions — to extract combinatorial information.

Convolution = Multiplication

If $A(x) = \sum a_n x^n$ and $B(x) = \sum b_n x^n$, then: $A(x) \cdot B(x) = \sum_n \left(\sum_{k=0}^{n} a_k b_{n-k}\right) x^n$

The coefficient of $x^n$ counts ways to choose items from $A$ and $B$ that sum to $n$.

Catalan Numbers via Generating Functions

The Catalan number OGF satisfies $C(x) = 1 + x \cdot C(x)^2$, giving: $C_n = \frac{1}{n+1}\binom{2n}{n}, \quad C_0=1,\ C_1=1,\ C_2=2,\ C_3=5,\ C_4=14,\ C_5=42$

import math

def catalan(n):
    return math.comb(2 * n, n) // (n + 1)

def ogf_multiply(f, g, terms):
    result = [0] * terms
    for i, fi in enumerate(f):
        for j, gj in enumerate(g):
            if i + j < terms:
                result[i + j] += fi * gj
    return result

print(catalan(5))                           # 42
print(ogf_multiply([1,1,1], [1,1,1], 5))   # [1, 2, 3, 2, 1]

Your Task

Implement catalan(n), ogf_multiply(f, g, terms), and extract_coefficient(ogf, n).