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

Inclusion-exclusion

Determinantal formulas: matrix-tree and B.E.S.T. theorems, Lindström–Gessel–Viennot lemma, determinant-permanent/Pfaffian-Hafnian 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 transfer-matrix 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₁(n), A₂(n), A₃(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 3-419

8801 5911

zhuyf@sustc.edu.cn

Office Hours: Monday & Thursday 10:00-11: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.