Combinatorics Textbook
From the fundamentals of counting to algebraic combinatorics. A textbook series building definitions, theorems, and proofs in a systematic progression.
Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs
A single-page survey of undergraduate combinatorics. Covers the fundamentals of counting, binomial coefficients, inclusion-exclusion, generating functions, Catalan numbers, Ramsey theory, Burnside and Polya enumeration, combinatorial designs, posets, and algebraic combinatorics. Includes a dependency diagram and a theorem-algorithm directory.
Fundamentals of Counting: The Addition Principle, Multiplication Principle, Permutations, and Combinations
Starting from the addition and multiplication principles, we define and prove the formulas for permutations P(n,r), combinations C(n,r), permutations with repetition, and combinations with repetition H(n,r). We conclude with the enumeration of injections and surjections.
Binomial Coefficients and the Binomial Theorem: From Pascal's Triangle to the Multinomial Theorem
We prove Pascal's identity, the binomial theorem, the Vandermonde convolution, and the multinomial theorem. We then extend the discussion to generalized (negative) binomial coefficients and Lucas' theorem.
The Inclusion--Exclusion Principle: Counting by Alternating Sums
We prove the inclusion--exclusion principle and apply it to derive the formula for the number of derangements D_n, Euler's totient function, the relationship between surjections and Stirling numbers of the second kind, and the M\"{o}bius inversion formula.
Generating Functions I (Ordinary): Encoding Sequences as Power Series
We introduce ordinary generating functions (OGFs), establish the connection between products and convolutions, derive Binet's formula for the Fibonacci numbers via OGFs, and present the generating functions for the Catalan numbers and the partition function.
Generating Functions II (Exponential): Counting Labeled Structures
We introduce exponential generating functions (EGFs) and show that their product corresponds to labeled merging. We then derive the EGFs for Stirling numbers and Bell numbers, and prove Cayley's formula for labeled trees.
Recurrence Relations and Counting: Solving Linear Recurrences
We present the method of characteristic equations for solving linear recurrences with constant coefficients, treat the case of repeated roots, discuss nonhomogeneous recurrences, establish the equivalence with generating functions, and introduce matrix exponentiation and the Kitamasa method.
Catalan Numbers and Lattice Paths: The Reflection Principle and Bijective Proofs
We prove the formula C_n = (1/(n+1)) C(2n, n) for the Catalan numbers using the reflection principle, state the Lindstr\"{o}m--Gessel--Viennot lemma, construct bijections among five combinatorial interpretations of the Catalan numbers, solve the ballot problem, and introduce Narayana numbers.
The Pigeonhole Principle and Ramsey Theory: Existential Combinatorics
We develop the generalized pigeonhole principle, prove the Erd\H{o}s--Szekeres theorem on monotone subsequences, establish the existence of Ramsey numbers R(s,t), give a complete proof that R(3,3) = 6, and derive the probabilistic lower bound R(k,k) > 2^{k/2}.
Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry
Starting from the definitions of group actions, orbits, and stabilizers, we prove Burnside's lemma (the Cauchy--Frobenius theorem), introduce the cycle index of a permutation group, and derive P\'olya's enumeration theorem. Applications to necklace and bracelet counting are given.
Combinatorial Designs and Latin Squares: Balanced Arrangements
We define Latin squares and prove their existence, introduce mutually orthogonal Latin squares (MOLS), develop the theory of balanced incomplete block designs (BIBDs), prove Fisher's inequality, and discuss the connection with finite projective planes.
Partially Ordered Sets and Lattices: The Combinatorics of Order
We develop the theory of partially ordered sets (posets), including Hasse diagrams, chains and antichains, and prove Dilworth's theorem and Mirsky's theorem. We then introduce lattices and the M\"obius function of the incidence algebra.
Combinatorics and Algebra: Formal Power Series and an Introduction to Algebraic Combinatorics
We examine the algebraic structure of the formal power series ring Q[[x]], including multiplicative inverses, composition, and formal differentiation. We then discuss P-recursive (holonomic) sequences, prove the Lagrange inversion formula, and introduce the WZ method and hypergeometric series.