Math 580-001, Fall 2019

Prof. Jim Haglund,
Course webpage:

Office hours (all in DRL 4E2B):
M, 9-9:50am.
W, 10:30-11:30am.

Office Phone: (215) 573-9093.

Grader: Logan Crew,

Grader's Office hours: Thursday 2-2:50pm in DRL 3N2B.

Lecture: TR 12-1:20pm in DRL 3W2

Course: An introduction to combinatorics suitable for advanced undergraduates or graduate students in mathematics. In particular, it covers certain core material that all students who take a Ph. D. oral exam in combinatorics (minor or major) here at Penn must know. The primary text for the course is Enumerative Combinatorics Volume I by Richard Stanley (2nd edition), Chapters 1, 2 and part of 3. Specific topics to be covered in the course include:

Basic Objects in Enumeration: Generating Functions, Permutation Statistics, Eulerian Polynomials, Multiset Permutations, q-Binomial Coefficients, Stirling and Bell Numbers.

Involutions, Determinants.


Rook Polynomials: Permutations with Restricted Position, q-Rook Polynomials, Zeros of Rook Polynomials and Matching Polynomials.

Posets: Mobius Functions.

The Transfer-Matrix Method.

A good auxillary reference for this course I recommend is generatingfunctionology, by Herb Wilf. This can be downloaded for free from his webpage Stanley's book is on reserve in the Physics/Math Library on the 3rd floor of DRL. Also, we will cover most of Chapter 1 from my book The q,t-Catalan Numbers and the Space of Diagonal Harmonics". In addition, some of the lectures will be taken from a pilot version of "Combinatorics: The Art of Counting" by Bruce Sagan. Copies of some of the chapters of this book will be distributed in class.

Exams and Grades: There will be two hour exams and a final exam. Each hour exam counts 25% of your grade, and the final exam counts 35%. There will also be HW assignments (posted at the bottom of this web page) counting 15% of your grade. Midterm 1 will be on Thursday, Oct. 3 from 12-1:20pm in DRL 3W2 and Midterm 2 will be on Thursday, Nov. 14 from 12-1:20pm in DRL 3W2. The final exam will be a take-home exam, due on Thursday, Dec. 19 by noon (under my office door, or as an email pdf attachment).

Midterm 1: The exam will be a closed book exam. No notes, calculators, cell phones, etc. will be allowed. It Covers material from Chapter 1 of Stanley's Enumerative Combinatorics, except sections 1.5, 1.6.2, 1.6.3, and 1.10. Also includes a discussion of the basic properties of parking functions, the proof that the Eulerian polynomials have only real zeros, and the proof that the Catalan numbers (defined as the binomial coefficient (2n choose n), divided by n+1, also count the number of lattice paths from (0,0) to (n,n) consisting of unit North and East steps, which never go below the diagonal y=x.

Important Dates:
Tuesday, August 27: Classes begin
Midterm 1: Thursday, Oct. 3, 12-1:20pm in DRL 3W2
Last Day to Drop a Course: Oct. 7.
Fall Break: Thursday, Oct. 10 - Sunday, Oct. 13.
Last Day to Withdraw from a Course: Nov. 4.
Midterm 2: Thursday, Nov. 14, 12-1:20pm in DRL 3W2
Thanksgiving Break: Thursday, Nov. 28 - Sunday, Dec. 1
Last Day of Classes: Monday, Dec.9
Take-home Final exam due on Thursday, Dec. 19 by noon

Homework Assignments:

HW1 (due in class on 9/26): Do exercises #3 parts (a),(b) and (f), #5, #7, #19 parts (a) and (b), and #29 from Chapter 1 of Stanley's Enumerative Combinatorics, Second Edition. Also, under the bijection of p.28 from Stanley (as in Example 1.3.9), what sequence (a1,...,a9) does the permutation (5263)(9)(8714) with n=9, t=3 and cycle function f(C1)=1, f(C2)=3, and f(C3=3), get mapped to? In addition, give a bijective proof that 132 avoiding permutations in the symmetric group Sn are in bijection with Dyck paths from (0,0) to (n,n) (i.e. lattice paths consisting of unit North and East steps that never go below the main diagonal x=y).