Generating Functions Explained with Sequences and Power Series

An exponential generating function (EGF) encodes a sequence a₀, a₁, a₂, ... as a power series where the coefficient of xⁿ is aₙ/n!; unlike ordinary generating functions, EGFs often provide nicer convergence properties and are particularly useful for combinatorial problems involving labeled structures. For example, the EGF for the constant sequence 1 is eˣ, and the EGF for permutations of n elements is 1/(1-x). To count derangements (permutations with no fixed points), we use the combinatorial identity that any permutation can be decomposed into a fixed set and a deranged set, leading to the EGF equation eˣ × D̃(x) = 1/(1-x), which solves to D̃(x) = eˣ/(1-x), providing an elegant method to derive the number of derangements of a finite set.

Exponential generating functions are used for exponential combinatorial structures like permutations. The tangent function tan(t) = t + t³/3 + 2t⁵/15 + 17t⁷/315 + ... has coefficients that count alternating permutations. An alternating permutation on n elements is one where the elements alternate between decreasing and increasing: a₁ > a₂ < a₃ > a₄ < ... The number of alternating permutations on 2n+1 elements equals the coefficient of t^(2n+1)/(2n+1)! in tan(t). This was discovered by André in the late 19th century.

This segment introduces exponential generating functions as a method for solving permutation problems with multi-sets. The video explains that 'papaya' forms a multi-set with two P's, three A's, and one Y. The method involves constructing exponential generating functions for each letter type: P: 1 + x + x^2/2, A: 1 + x + x^2/2 + x^3/6, Y: 1 + x. These functions represent possible selections of each letter type, with factorial denominators accounting for arrangements of identical elements. The product of these functions, when expanded, contains terms representing all possible arrangements. The coefficient of x^4/4! in this product gives the number of ways to arrange 4 letters from the multi-set.

To solve permutation problems with constraints, construct an exponential generating function by creating a product of terms, where each term corresponds to a letter type. For each letter type, include powers of x corresponding to the allowed counts, divided by the factorial of each count. The coefficient of x^M/M! in the product gives the answer.

Exponential generating functions solve permutation problems with repeated elements. For 'ENGINE' (E:2, N:2, G:1, I:1), the function is (1+x+x²/2!)² × (1+x)², where the coefficient of x⁴/4! gives 102 arrangements. For '8768678' (three 8s, two 7s, two 6s), the function is (1+x+x²/2!+x³/3!) × (1+x+x²/2!) × (1+x+x²/2!), with coefficient of x⁴/4! equal to 624. For geometric sequences like 1, -4, 16, -64, ..., the function is e^(-4x) = 1 - 4x + 16x²/2! - 64x³/3! + ..., following e^(kx) = Σ (kⁿxⁿ)/n!. To find coefficients in products, identify all term pairs whose powers sum to the target power.

A generating function is a formal power series that encodes a sequence of numbers, where the coefficient of qⁿ represents the nth term of the sequence; this powerful tool transforms complex combinatorial problems into algebraic manipulations, enabling elegant solutions to integer partition problems and recursive sequences through techniques like partial fraction decomposition.

The generating function for the number of integer partitions of n with parts no larger than m is given by the product formula πₘ(q) = ∏ⱼ=1^m 1/(1 - q^j), which can be proven by induction by considering how adding a new part size affects existing partitions; this leads to Euler's famous theorem that the number of partitions of n into odd parts equals the number of partitions of n into distinct parts.

The generating function for integer partitions is the infinite product ∏_{i=1}^∞ 1/(1 - x^i), where each term 1/(1 - x^i) represents the generating function for selecting any number of i's (including zero), and the coefficient of x^n in this product gives the number of ways to partition the integer n; this generating function approach can also be extended to solve more complex partition problems with restrictions, such as proving that the number of partitions where no part appears more than twice equals the number of partitions where no part is divisible by three.

This segment covers the complete methodology for solving integer partition problems using generating functions. The problem of finding non-negative integer solutions to 2a + 5b = 100 is equivalent to finding integer partitions of 100 using only parts of size 2 and 5. The number of solutions to 2a = n is 0 if n is odd and 1 if n is even, with generating function 1/(1 - x²). Similarly, solutions to 5b = n are 0 if n is not divisible by 5 and 1 if it is, with generating function 1/(1 - x⁵). The generating function for the combined equation is the product of individual generating functions: C(x) = A(x) × B(x) = 1/[(1 - x²)(1 - x⁵)]. This rational function is then decomposed using partial fractions into simpler components: A/(1 + x) + B/(1 - x)² + (Cx⁴ + Dx³ + Ex² + Fx + G)/(1 - x⁵). The coefficients are found by multiplying both sides by the denominator and equating coefficients of like powers of x from highest to lowest.

Analytic combinatorics studies generating functions as complex functions to derive asymptotic formulas for combinatorial coefficients. The transfer theorem states that if a generating function F(z) has a dominant singularity at z=ρ with local behavior (ρ - z)^(-α), then the coefficient f_n ~ C × n^(-α-1) × ρ^(-n). For many combinatorial classes, this yields asymptotic behavior of the form f_n ~ C × n^(-3/2) × ρ^(-n), showing universal square-root singularities.

This lecture demonstrates how the symbolic method combined with meromorphic asymptotics provides immediate asymptotic estimates for combinatorial coefficients. The key principle is that the dominant singularity closest to the origin determines all asymptotic growth behavior. Examples include: (1) Derangements (permutations with no fixed points) with generating function e^(-z)/(1-z), yielding n!/e; (2) Surjections (coupon collector sequences) with generating function 1/(2-e^z), yielding (log 2)^n/(2 log 2); (3) Double surjections requiring each element to appear at least twice; (4) Alignments (sequences of labeled cycles) with generating function 1/(1-log(1/(1-z))); (5) Set partitions (Bell numbers) with generating function (1/(1-z))^r/r!, yielding r^n/(r! * r). The method works even for complex generating functions, with error terms exponentially small.

Meromorphic functions, which are ratios of analytic functions, can be analyzed using complex integration and residue theory to derive asymptotic estimates for their coefficients. The key insight is that the asymptotic growth of coefficients is determined by the dominant pole—the singularity closest to the origin—with the exponential growth factor being the reciprocal of this pole's location, and the sub-exponential factor being a polynomial in n of degree one less than the pole's order. For combinatorial generating functions with non-negative coefficients, Pringsheim's theorem guarantees that the dominant pole is real and positive, simplifying the analysis significantly.

Analytic combinatorics applies complex analysis to combinatorial enumeration, extending from single-variable generating functions to arrays of d-dimensional numbers. Single-variable generating functions encode sequences as power series, with rational functions arising from linear recursions, algebraic ones from convolutions, and differentially finite functions from polynomial recursions. Hardy and Ramanujan pioneered asymptotic analysis of integer partitions around 1918 using Cauchy's integral formula. The saddle point method, developed from 1950 to 1990, provided systematic evaluation requiring regular boundary behavior. Philippe Flajolet and Andrew Odlyzko established the transfer theorem, showing analytic behavior near dominant singularities directly translates to coefficient asymptotics. Multivariate generating functions arise naturally in combinatorics (counting classes with multiple parameters), probability theory (random tilings, quantum walks), queuing theory, lattice point enumeration, and algorithm analysis. Algebraic generating functions embed as diagonals of rational functions, enabling application of rational function techniques. The Aztec diamond tiling model demonstrates how generating functions encode macroscopic limit shapes with phase boundaries between deterministic and random regions.

This section establishes the foundational framework of analytic combinatorics. It introduces enumerative combinatorics as the study of discrete objects through sequences counting objects of each size, with applications ranging from counting change combinations to algorithm runtimes. Generating functions serve as the central tool, encoding sequences as power series that can be analyzed using complex analysis. The lecture presents the hierarchy of generating function classes: rational functions (from linear recurrences) ⊂ algebraic functions ⊂ D-finite functions (satisfying linear differential equations). The tangent function example demonstrates how exponential generating functions reveal combinatorial structure, with residues at singularities providing explicit asymptotic formulas. The Cauchy integral formula enables coefficient extraction through complex integrals, while singularities closest to the origin dominate asymptotic behavior.