Generating Functions and Their Applications

Generating Functions

Ordinary Generating Functions

A sequence {aₙ} ↔ f(x) = Σₙ₌₀^∞ aₙxⁿ.

Operations on sequences ↔ operations on functions.

Convolution: (a*b)ₙ = Σₖ₌₀ⁿ aₖbₙ₋ₖ ↔ f(x)·g(x).

Number of partitions of the number n into parts 1,2,3,...: ∏ₖ₌₁^∞ 1/(1−xᵏ) = Σₙ p(n)xⁿ.

Number of partitions into odd parts = number of partitions into distinct parts (remarkable Euler’s identity).

Exponential Generating Functions

For labeled objects: f(x) = Σₙ aₙxⁿ/n!.

Product of EGFs: a*b_n = C(n,k)aₖbₙ₋ₖ (choosing k labeled places).

Number of derangements: D_n = n! Σ (−1)ᵏ/k!. EGF: e^{−x}/(1−x).

Linear Recurrences and Fractions

A sequence is linearly recurrent ⟺ its OGF is a rational function.

F(n) (Fibonacci numbers) → f(x) = x/(1−x−x²) = x/((1−φx)(1−ψx)). Decomposition into partial fractions → Binet’s formula.

Analytic Methods

Saddle point method (Laplace): for the coefficient [xⁿ]f(x) at large n — asymptotics via the saddle point of f.

Application: p(n) ~ e^{π√(2n/3)}/(4n√3) — from the Hardy–Ramanujan formula via the Dedekind η function.

Generating Functions for Algorithm Analysis

Generating functions are systematically applied in the analysis of algorithms (book “Analytic Combinatorics” by Flajolet and Sedgewick). Symbolic methods: the function for trees T(z) satisfies T(z) = z·exp(T(z)) for labeled rooted trees — this is a functional equation. Number of rooted trees with n vertices: [zⁿ]T(z) = nⁿ⁻¹/n! (again Cayley’s formula).

Method of analytic continuation: The asymptotics of the coefficients [zⁿ]f(z) is determined by the singularities of f(z). For rational f: poles give exponential growth. For algebraic f: branch points give a power factor. Flajolet–Odlyzko transfer theorem: near a square root singularity z₀: f(z) ~ C(1−z/z₀)^{-α} ⟹ [zⁿ]f(z) ~ C·n^{α−1}/Γ(α)·z₀^{−n}.

Random Structures via Generating Functions

Random tree: If T is a random rooted tree with n vertices (uniformly), then E[height] = O(√n) for Cayley trees and O(log n) for BST from random permutations. Generating functions allow calculating these expectations exactly.

Secretary problem: From a deck of n cards, draw one by one until an ace is drawn. The expected number of draws: (n+1)/(k+1), where k is the number of aces. Formula via generating functions of “discrete uniform order statistics”.

Estimates for Nontrivial Enumerative Problems

Number of proper colorings of a cycle Cₙ in m colors: P(Cₙ, m) = (m−1)ⁿ + (−1)ⁿ(m−1). This is obtained from the chromatic polynomial via the inclusion-exclusion formula or the transfer matrix: [[m−1, −1],[1, 0]]ⁿ.

Number of Latin squares of order n is one of the fastest-growing combinatorial functions: L(n) ~ (n/e²)^{n²} (van der Waerden’s asymptotics). Exact values are known for few n (up to n=11). Each Latin square corresponds to a system of orthogonal Latin squares, used in the construction of block codes and the design of experiments.

Block Designs and Experimental Design

Balanced Incomplete Block Design (BIBD (v,b,r,k,λ)): v objects, b blocks, each object in r blocks, each block of k objects, each pair in λ blocks. Necessary condition: λ(v−1) = r(k−1), bk = vr. Projective planes PG(2,q) realize BIBDs with v = b = q²+q+1, r = k = q+1, λ = 1. Applications in agricultural experiments, clinical trials, planning computer experiments.

Coding in Finite Fields

Finite field GF(pⁿ) — field with pⁿ elements (p is prime). Construction: GF(pⁿ) = ℤ_p[x]/(f(x)), where f is an irreducible polynomial of degree n over ℤ_p. Group GF(pⁿ)* = ℤ_{pⁿ−1} — cyclic. Primitive element g: generates the entire multiplicative group. Discrete logarithm: to solve gˣ = a is computationally hard, foundation of cryptography (ECDSA, Diffie–Hellman on elliptic curves). Algorithms for computing the discrete logarithm: Pohlig–Hellman, BSGS, Index Calculus.

Combinatorial Proofs of Identities

Vandermonde identity: C(m+n,r) = Σ C(m,k)C(n,r−k). Combinatorial proof: to split a group of m+n people into r — choose k from the first m and r−k from the second n. Pascal’s identity: C(n+1,k) = C(n,k) + C(n,k−1) — an element is included or not. Hockey stick identity: Σᵢ₌₀^r C(n+i,i) = C(n+r+1,r). Combinatorial: choose r from {1,...,n+r+1} and look at the largest not chosen.

Pollard’s Theorem and Algebraic Combinatorics

Polynomial methods in combinatorics: Combinatorial Nullstellensatz (Alon): if the sum of the degrees of the polynomial in variables f(x₁,...,xₙ) = Σ cₐxᵃ has a nonzero coefficient at xₐ: aᵢ = dᵢ and given Sᵢ with |Sᵢ| > dᵢ, then ∃ sᵢ ∈ Sᵢ: f(s₁,...,sₙ) ≠ 0. Application: Hamming bound from coding theory, Erdős–Ko–Rado theorem via polynomials, code design with geometric properties.

Catalan Numbers and Their Combinatorial Interpretations

Cₙ = C(2n,n)/(n+1) = 1,1,2,5,14,42,132,... They count: the number of correctly parenthesized expressions, BST with n vertices, non-crossing partitions, monotone paths below the diagonal, triangulations of an (n+2)-gon. OGF: C(x) = (1−√(1−4x))/2x. Recurrence: Cₙ₊₁ = ΣCₖCₙ₋ₖ — convolution type. Also: Narayana numbers Nₙ,ₖ = C(n,k)C(n,k−1)/n — a refinement of Catalan by the number of peaks in a Dyck path.

Numerical Example: Fibonacci Numbers via OGF

Problem: Compute F₈ using the generating function and Binet’s formula.

Step 1: Recurrence Fₙ=Fₙ₋₁+Fₙ₋₂, F₀=0, F₁=1. OGF: F(x)=x/(1−x−x²).

Step 2: Partial fractions: 1−x−x²=−(x−r₁)(x−r₂), roots r₁=(−1+√5)/2, r₂=(−1−√5)/2. Binet’s formula: Fₙ=(φⁿ−ψⁿ)/√5, where φ=(1+√5)/2≈1.618, ψ=(1−√5)/2≈−0.618.

Step 3: F₈=(1.618⁸−(−0.618)⁸)/√5. Let’s calculate: 1.618⁸≈46.98; (−0.618)⁸=(0.618)⁸≈0.022 (even power, positive).

Step 4: F₈=(46.98−0.022)/2.236≈46.96/2.236≈21. Checking: 0,1,1,2,3,5,8,13,21 → F₈=21. ✓ Catalan number C₄=14 — number of BST on 4 vertices, next value: C₅=42.