Math 491 lectures, topic by topic

(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. I'm sure there are other omissions of credit; please let me know about them! Also let me know about my mistakes, of course. And lastly, let me know if I forget to include my lesson-plans for some particular lecture or lectures.)

9/2 (lesson plan) 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/4 (lesson plan) Introduction to Maple.

9/9 (lesson plan) The generating function for Fibonacci numbers. The ring of formal power series and its properties. Cancellation and multiplicative inverses. Equivalence of convergence and absolute convergence.

9/11 (lesson plan) The bivariate generating function for Pascal's triangle. The formal binomial theorem (with arbitrary exponent). Encoding recurrence relations as algebraic relations between generating functions.

9/16 (lesson plan) 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.

9/18 (lesson plan) The general solution to homogeneous linear recurrence equations with constant coefficients (with repeated roots allowed). More on homogeneous LREs with constant coefficients. Application to counting domino tilings of a 3-by-n rectangle. Joint recurrence equations and the use of matrix equations.

9/23 (lesson plan) Matrices, characteristic polynomials, and recurrences.

9/25 (lesson plan) The case of non-diagonalizable matrices and linear recurrences whose associated polynomials have multiple roots. The relationship between generating functions, explicit formulas for coefficients, and linear operators. The falling factorial basis for the space of polynomials of degree < m. Using difference tables to find a polynomial formula for a sequence of numbers.

9/30 (lesson plan) Entries in powers of matrices, diagonalizable or not; the Cayley-Hamilton theorem. Difference tables, polynomial functions, and non-polynomials functions. Counting paths in directed graphs. Dynamic programming.

10/2 (lesson plan) Transfer matrices. Applications to counting domino tilings.

10/7 (lesson plan) The strip-tiling theorem (rationality of the generating function). Weighted enumeration and two-variable generating functions.

10/9 (lesson plan) Weighted enumeration (concluded). The addition and multiplication principles. Irreducible tilings.

10/14 (lesson plan) Irreducible tilings. Transfer matrices and traces.

10/16 (lesson plan) Graphs, perfect matchings and spanning trees. Ballot sequences and Catalan numbers.

10/21 (lesson plan) The generating function of Catalan numbers.

10/23 (lesson plan) The Catalan recurrence. The reflection principle.

10/28 (lesson plan) Dyck paths weighted by area (a 2-variable generating function).

10/30 (no notes; substitute lecture by Paul Terwilliger)

11/4 (lesson plan) Surfaces and tilings.

11/6 (lesson plan) Tilings, lattice paths, and routings. The exchange principle.

11/11 (lesson plan) Catalan numbers and parenthesizations of products. Catalan numbers and triangulations of polygons. The "short" recurrence for Catalan numbers (omitted from oral lecture).

11/13 (lesson plan) The "short" recurrence for counting lattice paths by q-weight. Number partitions. The "long" recurrence for counting unconstrained partitions.

11/18 (lesson plan) Number partitions. The long recurrence for counting partitions.

11/20 (lesson plan) Non-commuting variables. The sign of a permutation. Permanents and determinants. Lindstrom's lemma.

11/25 (lesson plan) Lindstrom's lemma. Plane partitions. Dodgson condensation.

12/2 (lesson plan) Plane partitions (concluded). More on Dodgson condensation. Frieze patterns. Number walls.

12/9 (lesson plan) From routings to perfect matchings. Lindstrom with weights. Number walls and linear recurrences.