Enumerative Combinatorics (SF2741)

Spring 2012


Where and when: Tuesdays at 13:15-15:00 in room 3733. 

Instructor: Petter Brändén, room 3626

Credits: 7.5, Grades: A-F, Language: English

Literature: R. P. Stanley, Enumerative Combinatorics, second edition, Cambridge University Press, 2011 (Electronic copy available at Stanley's homepage).

Contents: Basic methods in enumerative combinatorics. Sieve methods, for example inclusion-exclusion, the involution principle and the method of using determinants to count lattice paths. Various aspects of the theory of partially ordered sets, for example lattice theory, Möbius inversion in posets, P-partitions, and connections to topology.

Examination and grading: Four sets of homework problems will be handed out. Here is how the grading works:

Undergraduate students: Solving roughly 85% of the problems gives grade B, 75% gives C, 65% gives D, 55% & gives E, 50% gives Fx. In addition, one can choose to do a voluntary assignment which consists of writing a summary of a research article. Details about this assignment and articles to choose from can be found here. If satisfactory written, the summary will raise one's grade by one step.

Graduate students: In order to pass, one must solve 70% of the homework problems and hand in a satisfactory summary of a research article.

Homework: Collaboration is allowed, but you should write the solutions yourself. Please show all your work!

HW1. (To be handed in Feb. 28): Exercises from Stanley 1: 1.12 (Hint: Use Euler's formula for planar graphs), 1.20, 1.26, 1.33a, 44a, 47ab, 102abc, 114ab, 121ab.

HW2. (To be handed in March 20): PDF

HW3. (To be handed in April 17): PDF

HW4. (To be handed in May 22): PDF


Date Plan
01-19 Ch. 1.1-1.2.
01-24 Ch. 1.1-1.3.
01-31 Ch. 1.3-1.4.
02-07 Ch. 1.7-1.9, 2.1-2.2.
02-14 Ch. 2.1-2.2, 2.7
02-21 NO CLASS!
02-27 Ch. 2.7, 3.1-3.2
03-06 Ch. 3.2-3.4
03-13 Ch. 3.4-3.8
03-20 Ch. 3.8-3.11
03-27 Ch. 3.11
04-03 NO CLASS!
04-10 Ch. 3.11, Ch. 3.15. Notes from class: PDF. Exposition differs slightly from book.
04-17 Ch. 3.15, 3.12, 3.13
05-01 NO CLASS! Public Holidays