MAT8010  Combinatorics, Spring 2019
• Here is a summary of the main topics that we covered this semester.
Generating functions (ordinary, exponential)
Pólya theory
Permutation statistics
Lagrange inversion
Inclusionexclusion
Determinantal formulas: matrixtree and B.E.S.T. theorems,
Lindström–Gessel–Viennot lemma,
determinantpermanent/PfaffianHafnian method,
MacMahon's master theorem,
transfer matrix method
Partially ordered sets and lattices: distributive lattices and Birkhoff's theorem, Möbius functions and Möbius inversion
• Assignment 3 due Thursday, Jun. 6: any 6 from either of
 these Stanley Ch. 4 transfermatrix method exercises
[2]: #67, 68, 69, 73
 or these Stanley Ch. 3 exercises.
[2]: #10(a)
[2 ]: #34, 42(a,b), 45(a), 46(a,c), 47(a,b,c), 53, 70(a,b)
[2+]: #10(b), 14(a,b), 46(b), 85
• Assignment 2 due Thursday, May 9: all of the following Stanley Ch. 2 exercises.
[2]: #2
[2]: #25
[2+]: #14 (at least A_{1}(n), A_{2}(n), A_{3}(n))
• Assignment 1 due Thursday, Mar. 28 (note change): any 8 of the following Stanley Ch. 1 exercises.
[2]: #66, 113
[2]: #5, 20, 21, 26, 29, 47(a,b), 54, 68, 69, 102(a,b)
[2+]: #12, 18, 47(c), 175, 178, 102(c)
Instructor
Yifei Zhu
Huiyuan 3419
8801 5911
zhuyf@sustc.edu.cn
Office Hours: Monday & Thursday 10:0011:30 am
Grader: 黄弘毅
Class QQ group: 796570508
Objectives
This is a graduate introduction course to combinatorial theory.
This semester, we will study basic combinatorial objects
(e.g., subsets, multisets, permutations, set/number partitions, compositions, graphs, trees),
their enumeration, and other properties, such as graphical or partially ordered set structures.
Prerequisites
103b, 214.
Textbooks
Main text: R.P. Stanley, Enumerative combinatorics, Vol. I, Second Edition, Cambridge University Press.
Here are the book's errata.
Other useful sources:
F. Ardila,
Algebraic and geometric methods in enumerative combinatorics, Part I
H. Wilf,
generatingfunctionology
J.H. van Lint and R.M. Wilson, A course in combinatorics
Exams
There will be one final exam worth 50% of your final grade.
Homework
There will be three assignments to be posted on this page.
Homework is worth 50% of your final grade.
Students must make arrangements in advance if they will not be handing in homework on time.
We encourage you to discuss homework problems with your classmates,
including strategies for solving different kinds of problems.
However, when you actually write up your solutions, you must do this on your own.
