Department of Mathematics Syllabus

This syllabus is advisory only. For details on a particular instructor's syllabus (including books), consult the instructor's course page. For a list of what courses are being taught each quarter, refer to the Courses page.

MAT 245: Enumerative Combinatorics
Approved: 2009-03-01, Jesus De Loera

Units/Lecture:

Fall, alternate years; 4 units; lecture/extensive problem solving

Suggested Textbook: (actual textbook varies by instructor; check your instructor)
Enumerative Combinatorics, Vol. I, R. P. Stanley ($121). Supplement: A Course in Enumeration, M. Aigner ISBN-13: 978-3642072536 ($70)
Search by ISBN on Amazon: 978-0-521-66351-9

Prerequisites:

MAT 145, 150 (or equivalent), or consent of instructor

Course Description:

Introduction to modern combinatorics and its applications. Emphasis on enumerative aspects of combinatorial theory.

Suggested Schedule:

Lectures Sections Topics/Comments


Depending on the instructor, different emphasis may be given to the various topics.
1 Chapter 1.1 Motivation, examples of enumeration through bijections and through generating functions
2-3 Chapter 1.1 Formal power series and generating functions, basics of solving recurrences (Catalan numbers is a good choice of example).
4-5 Chapters 1.2 Sets, multisets, permutations, and compositions. Set partitions and Stirling numbers of second kind.
6-7 Chapter 1.3 Permutation Statistics: cycle structure and Stirling numbers of first kind, inversions and descents
8-9 Chapter 1.3 Number-partitions and lattice paths, Gaussian coefficients
10 Chapter 1.4 Counting functions between finite sets and the twelvefold way
11-12 Chapter 1 Additional practice with solving recurrences, exponential generating functions and composition of generating functions. (most of this material appears as exercises in Stanley's book).
13-14 Chapter 2.1 Inclusion-exclusion
15-16 Chapter 2.2, 2.3 Applications: derangements, problemes des menages, permutations with forbidden position
17 Chapter 3.1 Basic concepts on posets: chains, anti-chains, order ideals, linear extensions, rank functions.
18 Chapter 3.2 New posets from old: direct sum and product of posets.
19 Chapter 3.3-3.4 Lattices, construction of distributive lattices, examples.
20 Chapter 3.6 The incidence algebra of a poset: Moebius functions
21 Chapter 3.7 Moebius inversion formula
22-23 Chapter 3.8 Techniques for computing Moebius functions, order complexes.
24-25 Chapter 3.9 Lattices and their Moebius functions.
26-28 Chapter 4 (sections 1,6,7) Further topics (as time allows): Rational generating functions, linear homogeneous Diophantine equations, or the transfer-matrix method.


Two more lectures can be used for midterms or to catch-up when falling behind.