Generating Functions Summary

Combinatorics · Axiom Academy

Let's review the key concepts from Unit 8: Ordinary and Exponential Generating Functions. Ordinary Generating Functions (OGF) Definition: For sequence (a₀, a₁, a₂, ...), the OGF is A(x) = a₀ + a₁x + a₂x² + ... Key Property: Coefficient of xⁿ equals aₙ, making coefficient extraction straightforward Best For: Counting problems where order doesn't matter and repetitions are allowed Operations: Addition, multiplication, and composition correspond to sequence operations Exponential Generating Functions (EGF) Definition: For sequence (a₀, a₁, a₂, ...), the EGF is A(x) = a₀ + a₁x/1! + a₂x²/2! + ... Key Property: Coefficient of xⁿ/n! equals aₙ, accounting for factorial scaling Best For: Counting labeled objects, permutations, and problems where order matters Operations: Product of EGFs naturally handles labeled combinatorial structures Addition: (A + B)(x) combines sequences term-by-term Multiplication: A(x)·B(x) gives convolution of sequences Scaling: A(cx) replaces xⁿ with cⁿxⁿ in all terms Differentiation: A'(x) shifts indices and multiplies by position Integration: ∫A(x)dx divides by position and adds constant Multiplication: A(x)·B(x) gives binomial convolution Differentiation: A'(x) shifts sequence left by one position Composition: Natural for labeled structures with substitutions Product Rule: Handles labeled objects being joined together Example Recap: Solving a Recurrence with Generating Functions

This is the written version of the interactive lesson above. See the full Combinatorics course.