Textbook
- Analytic Combinatorics, Flajolet and Sedgewick
- Generatingfunctionology, Wilf
Homework Assignments
Lecture Notes
Introduction to Generating Functions
- Topic 1: What is an answer?
- Topic 2: Generating Functions and Formal Power Series
- Topic 3: The Hierarchy of Generating Functions
Unlabeled Structures
- Topic 4: Combinatorial Classes and Admissible Constructions
- Topic 5: Compositions, Words, Trees, and More
- Topic 6: Additional Constructions (MSet, PSet, Substitution)
Coefficient Extraction
- Topic 7: Coefficient Extraction from Rational GFs
- Topic 8: Lagrange Inversion
- Topic 9: Coefficient Extraction from Algebraic GFs
Labeled Structures
- Topic 10: Constructions with Labeled Objects
- Topic 11: Two-Level Constructions
- Topic 12: Labeled Trees, Mappings, and Graphs
- Topic 13: The Boxed Product
Multivariate Generating Functions and Probability
- Topic 14: Bivariate GFs and Specifications
- Topic 15: Probability, Moments, and Concentration
- Topic 16: Bivariate Enumeration and Catalytic Variables
- Topic 17: The Kernel Method
- Topic 18: Resultant Methods
- Topic 19: The Guess-and-Check Method
Complex Analysis of GFs
- Topic 20: Singularities and Exponential Growth
- Topic 21: Rational and Meromorphic Functions
- Topic 22: Standard Function Scale, part 1
- Topic 23: Standard Function Scale, part 2
- Topic 24: Multiple Singularities
- Topic 25: Puiseux Series, Newton's Polygons, and Algebraic GFs
Accompanying Code
- Topic 16: A collection of three python programs to simulate the distributions for binomial and Poisson random variables, as well as the distribution of the number of cycles in a random permutation.
- binomial.py – Simulates repeated trials of a binomial draw with n binary experiments, T at a time.
-
python binomial.py n T &
- poisson.py – Simulates repeated trials of a Poisson draw with mean r, T at a time.
-
python poisson.py r T &
- num-cycles-dist.py – Simulates the distribution of the number of cycles in a permutation of length n, T at a time.
-
python num-cycles-dist.py n T &
-
Topic 18: Maple Worksheet to compute the minimal polynomial for 2-West-stack-sortable permutations
Note: you may need to right-click and choose "save link" to download.
-
Topic 25: Maple Worksheet to demonstrate multiple branch singularities and sheet interaction in algebraic generating functions
Note: you may need to right-click and choose "save link" to download.