# MATH 245:Enumerative Combinatorics Winter 2021, UC Davis

 Lectures: MWF 3:10-4:00pm in Zoom CRN 44430 Office hours: after each class Instructor: Anne Schilling, MSB 3222, anne@math.ucdavis.edu Text: Richard P. Stanley, "Enumerative Combinatorics, Volume I" Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, Second Edition 2012 Other very useful text: Bruce E. Sagan, "Combinatorics: The art of counting", Graduate Studies in Mathematics, AMS, 2020 Prerequisites: MAT 145, 150 or equivalent; or permission by instructor Grading: Homework: 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). Presentation: 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. Web: http://www.math.ucdavis.edu/~anne/WQ2021/245.html

### Course description

Introduction to combinatorics at the graduate level, covering the following main topics:
I. Introduction to counting (permutation statistics, twelvefold way)
II. Inclusion-Exclusion
III. Order (posets, lattices, Moebius inversion)
IV. Generating functions

The sequel to this course MAT 246 will cover symmetric functions and algebraic combinatorics.

### Topics

• 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

Homework 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.