MATH 245:Enumerative Combinatorics
Winter 2021, UC Davis
||MWF 3:10-4:00pm in Zoom
|Office hours: after each class
||Anne Schilling, MSB 3222,
Other very useful text:
- Richard P. Stanley, "Enumerative Combinatorics, Volume I"
Cambridge Studies in Advanced Mathematics 49, Cambridge University
Press, Second Edition 2012
- Bruce E. Sagan, "Combinatorics: The art of counting", Graduate Studies in Mathematics, AMS, 2020
||MAT 145, 150 or equivalent; or permission by instructor
A list of problems is assigned. Two problems from the list of problems is due every second Friday (so 10 different problems in total for the quarter).
In addition, every second Friday we will discuss homework problems. You can team up in groups of 2-3 students and present problems during these discussions. Each student is expected to present at least one or two problems (in a group) during the quarter.
Introduction to combinatorics at the graduate level, covering the
following main topics:
I. Introduction to counting (permutation statistics, twelvefold way)
III. Order (posets, lattices, Moebius inversion)
IV. Generating functions
The sequel to this course MAT 246 will cover symmetric functions
and algebraic combinatorics.
- Motivation; example of a non-combinatorial and combinatorial proof (ch 1.1)
- Review of basic counting: sets and multisets (ch. 1.2)
- Cycles and inversions (ch. 1.3)
- Descents (ch. 1.4)
- Partitions and q-binomial coefficients (ch. 1.7)
- Partition identities (ch. 1.8)
- The twelvefold way (ch. 1.9)
- Rogers-Ramanujan identities
- Inclusion-exclusion (ch. 2.1, 2.2)
- Permutations with restricted position (ch. 2.3)
- Involutions (ch. 2.6)
- The Matrix-Tree Theorem (Sagan ch. 2.6)
- Posets (ch. 3.1)
- Lattices (ch. 3.3)
- Distributive lattices (ch. 3.4)
- Incidence algebras (ch. 3.6)
- Moebius inversion formula (ch. 3.7)
- Applications of Moebius inversion (ch. 3.8)
- Promotion and evacuation (ch. 3.10)
- Markov chain on linear extensions
List of Problems
An extension of Problem 17 can be found in:
Stanton, Dennis W.; White, Dennis E. A Schensted algorithm for rim hook tableaux. J. Combin. Theory Ser. A 40 (1985), no. 2, 211-247.
This is also related to n-cores and n-quotients of a partition.