| Date | Lecture | Notes |
|---|---|---|
| Week 1 | ||
| 8/28 | Introduction to the course; the Pigeon-Hole Principle | |
| 8/30 | The Generalized Pigeon-Hole Principle; the Erdős–Szekeres Theorem | |
| Week 2 | ||
| 9/4 | Labor Day | |
| 9/6 | The Method of Mathematical Induction: weak and strong induction | |
| Week 3 | ||
| 9/11 | Permutations, strings over a finite alphabet, and choice problems; binomial coefficients and Pascal's Triangle | notes |
| 9/13 | Combinatorial proofs of binomial identities (hockey stick, Vandermonde); the Binomial Theorem | notes |
| Week 4 | ||
| 9/18 | Multinomial coefficients and the Multinomial Theorem; distributing objects into boxes (distinct vs. identical) | notes |
| 9/20 | Stars and bars: weak compositions and compositions; set partitions and Stirling numbers of the second kind | notes |
| Week 5 | ||
| 9/25 | Stirling numbers of the second kind, Bell numbers, counting surjections; integer partitions | notes |
| 9/27 | Ferrers diagrams, conjugate and self-conjugate partitions; introduction to cycles in permutations | notes |
| Week 6 | ||
| 10/2 | Cycles in permutations; decomposition of a permutation into disjoint cycles | notes |
| 10/4 | Midterm 1 | |
| Week 7 | ||
| 10/9 | Permutations with a restricted cycle structure; Stirling numbers of the first kind | |
| 10/11 | The Sieve: the Principle of Inclusion-Exclusion | |
| Week 8 | ||
| 10/16 | Derangments, Hat Check Problem, Ballot Sequences | notes |
| 10/18 | Ballot Sequences, Catalan Numbers, Tower of Hanoi, Intro to Generating Functions | |
| Week 9 | ||
| 10/23 | Using Generating Functions to solve recurrences, Fibonnacci Numbers | notes |
| 10/25 | Generating Functions | notes |
| Week 10 | ||
| 10/30 | Triangulations of an n-gon | |
| 11/1 | Solving the Catalan generating function; Newton's Binomial Theorem and a closed formula for the Catalan numbers | |
| Week 11 | ||
| 11/6 | Motzkin Numbers Example | |
| 11/8 | Products and compositions of generating functions; introduction to exponential generating functions | |
| Week 12 | ||
| 11/13 | Exponential generating functions and recurrence relations; review for Midterm 2 | |
| 11/15 | Midterm 2 | |
| Week 13 | ||
| 11/21 | Products of exponential generating functions | |
| 11/22 | THANKSGIVING Break | |
| Week 14 | ||
| 11/27 | Compositions of exponential generating functions (set partitions, committees with chairpersons) | |
| 11/29 | Subsequence conditions on permutations: pattern avoidance | |
| Week 15 | ||
| 12/4 | Permutations avoiding a pattern of length three; the Catalan numbers again | |
| 12/6 | Stack sortable permutations and 231-avoidance | |
| Week 16 | ||
| 12/11 | Two stacks in series; review for the final exam | |
| 12/18 | Final Exam (3PM) | |