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