(Note: In these lectures, I do not always acknowledge the sources of the ideas and techniques that I teach. Some are well-known, and some are my own contribution to the subject; others I learned from specific individuals. For instance, Dana Randall came up with the trick of turning dominos tilings into routings, and David Wilson showed me how this trick generalizes via the "deleted double" construction. Also, the lecture from 9/26 is taken from the first chapter of Gian-Carlo Rota's classic book "Finite Operator Calculus." I'm sure there are other omissions of credit; please let me know about them! Also let me know about my mistakes, of course.)
9/13 (lesson plan | video): Overview. Course mechanics. Algebraic proofs versus bijective proofs. Ordinary sum (or alternating sum) of entries in a row of Pascal's triangle (or their squares). Generating functions.
9/17 (lesson plan | video): The generating function for Fibonacci numbers. The ring of formal power series and its properties. Cancellation and multiplicative inverses. The q-adic topology. Equivalence of convergence and absolute convergence. The bivariate generating function for Pascal's triangle. The formal binomial theorem (with arbitrary exponent).
9/20 (lesson plan | video): Encoding recurrence relations as algebraic relations between generating functions. The role of linearity. The vector space of solutions to a linear recurrence equation. The shift-operator T on sequence-space. Polynomials in T and the finite-dimensional subspaces they annihilate. The general solution to homogeneous linear recurrence equations with constant coefficients (with repeated roots allowed). Generalized Fibonacci sequences (the Lucas sequence in particular).
9/25 (lesson plan | video): More on homogeneous LREs with constant coefficients. Application to counting domino tilings of a 2-by-n rectangle. Recursive programming in Maple. Joint recurrence equations and the use of matrix equations.
9/26 (lesson plan | video): Proof of the formal binomial theorem. Many bases for the space of solutions to a LRE. Change-of-basis formulas. Calculus of finite differences applied to polynomials. Difference tables. The falling factorial basis for the space of polynomials. Partitions of sets and Bell numbers. Linear functionals on the space of polynomials. Dobinski's formula for the Bell numbers.
10/2 (lesson plan | video): Weighted enumeration. Application to counting domino tilings. Counting paths in directed acyclic graphs. Dynamic programming. Transfer matrices. Applications to counting domino tilings.
10/4 (lesson plan | video): The characteristic polynomial. The Cayley-Hamilton theorem and its applications. The strip-tiling theorem (rationality of the generating function). The orthogonality property for Stirling numbers. The combinatorial interpretation of Stirling numbers.
10/9 (lesson plan | video): Properties of Stirling numbers (recurrence relations and generating functions). The Addition and Multiplication Principles for generating functions. Application to Stirling numbers. Introduction to Catalan numbers via Dyck paths and ballot sequences.
10/11 (lesson plan | video): More on Catalan numbers: pairings, parenthesizations, triangulations. The generating function for Catalan numbers. The formula for Catalan numbers. The Catalan triangle. Application of the Multiplication Principle to counting domino tilings. The cofactor theorem. The trace theorem and non-zero eigenvalues. Application to counting domino tilings of a cylinder.
10/16 (lesson plan | video): Generating functions, traces, and eventually recurrent sequences. Popoviciu's lemma and reciprocity. Reciprocity for binomial coefficients. Sign-reversing involutions. Orthogonality for Stirling numbers.
10/18 (lesson plan | video): Stirling orthogonality (concluded). The reflection principle for counting constrained lattice paths. Tilings and paths. The exchange principle for non-intersecting pairs of paths (2-routings).
10/23 (lesson plan | video): The exchange principle, stated formally. Catalan numbers and triangulations. Catalan numbers and convolution. Coins in a fountain and continued fractions.
10/25 (lesson plan | no video): Coins in a fountain and continued fractions (correction from last time). Student solutions.
10/30 (lesson plan | video): Student solutions (concluded). Iteratively solving equations in the ring of formal power series. Polyominos. Lattice animals and directed lattice animals. Heaps, pyramids and half-pyramids.
11/1 (lesson plan | video): The short recurrence for counting triangulations. The short recurrence for counting lattice paths by q-weight. The q-integers.
11/6 (lesson plan | video): Number partitions. Ferrers graphs and Young diagrams. Gaussian polynomials (the q-binomial coefficients). Quasi-polynomials. Constraining part-sizes and/or requiring distinctness. Odd parts vs. distinct parts. The long recurrence for p(n). Euler's pentagonal number theorem. Franklin's bijective proof.
11/8 (lesson plan | video): The sign of a permutation. Permanents and determinants. Lindstrom's lemma. The determinant of the Pascal matrix. Plane partitions and tilings.
11/13 (no lesson plan | video): Dodgson condensation. Alternating sign matrices. Domino tilings of Aztec diamonds.
11/15 (no lesson plan | no video): REACH comes to visit.
11/20 (no lesson plan | video): Diagonals of generating functions.
11/27 (lesson plan | video): Plane partitions and tilings (MacMahon's formula). Routings. The routings-into-matchings trick. Lindstrom's lemma. Dodgson condensation. The q-weighted MacMahon formula. Solid partitions and the dimension barrier.
11/29 (lesson plan | video): Frieze patterns and diamond patterns. Tridiagonal matrices. The weighted version of Lindstrom's lemma. Gessel and Viennot. Hankel and Toplitz matrices. Number walls and windows.
12/4 (lesson plan | video): Cayley-Hamilton Theorem, proved combinatorially. Matchings of the 2-by-2n grid.
12/6 (lesson plan | video): Reciprocity. The Ehrhart summation convention. The polytope reciprocity theorem. Application to binomial coefficients. Application to chromatic polynomials.
12/11 (lesson plan | video): Domino-tiling reciprocity. The quadratic recurrence for matchings of the 2-by-2n grid. The quadratic recurrence for matchings of the Aztec diamond.
12/13 (lesson plan | video): Problem 17.3 via weighted path-enumeration. Weighted Kuo condensation on 2-by-2n and 2n-by-2n grids, revisited. From Dodgson to dominos. Relationships between recurrences. Somos sequences. Summary of course.