MATH 245:Enumerative Combinatorics
Fall 2014, UC Davis
||MWF 3:10-4:00pm in Bainer 1128
|Office hours: Wednesday 5:10-6pm
||Anne Schilling, MSB 3222, phone: 554-2326,
||Richard P. Stanley, "Enumerative Combinatorics, Volume I"
Cambridge Studies in Advanced Mathematics 49, Cambridge University
||MAT 145, 150 or equivalent; or permission by instructor
Problems will be assigned regularly in class. Students are
expected to work on these problems in groups of 2-3 students. Each group
should present at least one or two homework solutions in class.
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)
- 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.