Combinatorics Learning Roadmap

Phase 1: Foundations (4-6 weeks)

Basic Counting Principles

• Addition and multiplication principles
• Rule of sum and rule of product
• Bijective proofs and counting arguments
• Principle of inclusion-exclusion (PIE)
• Complementary counting
• Overcounting and undercounting techniques

Permutations and Combinations

• Permutations without repetition
• Permutations with repetition
• Circular permutations and arrangements
• Combinations (binomial coefficients)
• Combinations with repetition (multicombinations)
• The 12-fold way (Twelvefold way)
• Stars and bars technique

Binomial Theorem and Identities

• Binomial theorem and expansion
• Pascal's triangle properties
• Binomial identities (Vandermonde, hockey stick, etc.)
• Multinomial theorem
• Combinatorial proofs of identities

Basic Recurrence Relations

• First-order linear recurrences
• Second-order linear recurrences (Fibonacci, Lucas)
• Solving homogeneous recurrences
• Non-homogeneous recurrences
• Characteristic equation method
• Applications: counting sequences, tiling problems

Phase 2: Intermediate Combinatorics (8-10 weeks)

Week 1-2: Generating Functions

• Ordinary generating functions (OGF)
• Operations on generating functions
• Using GF to solve recurrences
• Exponential generating functions (EGF)
• Applications: counting permutations, partitions
• Product, composition, and differentiation of GFs
• Catalog of generating functions

Week 3-4: Graph Theory Basics

• Graph terminology and representations
• Degree sequences and Handshaking lemma
• Special graphs: complete, bipartite, regular, trees
• Paths, cycles, and connectivity
• Eulerian and Hamiltonian paths/circuits
• Graph coloring basics
• Planar graphs and Euler's formula
• Trees: properties, spanning trees, Cayley's formula

Week 5-6: Advanced Counting

• Derangements and subfactorial
• Catalan numbers and their applications
• Stirling numbers (first and second kind)
• Bell numbers and partition numbers
• Surjections, injections, and function counting
• Lattice paths and Dyck paths
• Young tableaux basics

Week 7-8: Principle of Inclusion-Exclusion

• General PIE formula and proof
• Applications to counting problems
• Derangements via PIE
• Chromatic polynomial
• Counting surjections
• Sieve methods
• Bonferroni inequalities

Week 9-10: Pigeonhole Principle

• Simple pigeonhole principle
• Generalized pigeonhole principle
• Ramsey theory introduction
• Applications to number theory
• Erdős-Ko-Rado theorem
• Applications to graph theory

Phase 3: Advanced Combinatorics (10-12 weeks)

Algebraic Combinatorics

• Group actions and Burnside's lemma
• Pólya enumeration theorem
• Cycle index of permutation groups
• Counting under symmetry
• Young tableaux and representations
• Schur functions
• Symmetric functions
• Applications: necklace problems, graph automorphisms

Enumerative Combinatorics

• Partitions and partition identities
• Ferrers diagrams and conjugate partitions
• q-binomial coefficients (Gaussian binomials)
• Pentagonal number theorem
• Partition generating functions
• Restricted partitions
• Rogers-Ramanujan identities

Extremal Combinatorics

• Turán's theorem
• Ramsey numbers and theory
• Extremal set theory (Sperner's theorem)
• Erdős-Ko-Rado theorem
• Kruskal-Katona theorem
• Forbidden subgraph problems
• Lovász Local Lemma

Probabilistic Method

• Basic probability in combinatorics
• First moment method
• Second moment method
• Lovász Local Lemma
• Alterations and deletions
• Random graphs (Erdős-Rényi)
• Concentration inequalities
• Applications: existence proofs

Combinatorial Designs

• Latin squares and orthogonal Latin squares
• Block designs (BIBD)
• Steiner systems
• Finite projective planes
• Hadamard matrices
• Error-correcting codes
• Applications: experimental design, cryptography

Matroid Theory

• Definition and basic properties
• Independent sets, bases, circuits
• Duality in matroids
• Representable matroids
• Greedy algorithm and matroids
• Matroid union and intersection
• Applications: optimization, network flows

Phase 4: Specialized Topics (8-10 weeks)

Analytic Combinatorics

• Complex analysis for combinatorics
• Singularity analysis
• Transfer theorems
• Admissibility conditions
• Asymptotic enumeration
• Saddle-point method
• Applications: average-case analysis of algorithms

Additive Combinatorics

• Sum-free sets
• Cauchy-Davenport theorem
• Freiman's theorem
• Roth's theorem on arithmetic progressions
• Sum-product problem
• Applications to number theory and computer science

Algebraic Graph Theory

• Graph spectra and eigenvalues
• Adjacency, Laplacian, and incidence matrices
• Spectral graph theory
• Strongly regular graphs
• Expander graphs
• Applications: network analysis, random walks

Combinatorial Optimization

• Matching theory (Hall's theorem, König's theorem)
• Network flows (max-flow min-cut)
• Minimum spanning trees
• Traveling salesman problem
• Linear programming and combinatorial optimization
• Approximation algorithms
• Integer programming

Topological Combinatorics

• Simplicial complexes
• Borsuk-Ulam theorem
• Kneser's conjecture and Lovász's proof
• Nerve theorem
• Applications: fair division, discrete geometry

Computational Combinatorics

• Algorithms for generating combinatorial objects
• Combinatorial search and backtracking
• Dynamic programming for counting
• Memoization techniques
• SAT solvers and constraint satisfaction
• Integer linear programming solvers

Phase 5: Research-Level Topics (Ongoing)

Combinatorics on Words

• Formal languages
• Pattern avoidance
• Sturmian words
• De Bruijn sequences
• Applications: bioinformatics, data compression

Geometric Combinatorics

• Convex polytopes
• Face lattices and f-vectors
• Gale diagrams
• Configuration spaces
• Oriented matroids

Combinatorial Game Theory

• Nim and Nim-sum
• Sprague-Grundy theorem
• Partizan games
• Surreal numbers
• Combinatorial game complexity

Discrete Geometry

• Arrangements of lines and hyperplanes
• Incidence geometry
• Sylvester-Gallai theorem
• Erdős distance problem
• Geometric graph theory

Quantum Combinatorics

• Quantum graphs
• Quantum chromatic numbers
• Non-local games
• Applications to quantum computing