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, Zeros of Rook Polynomials and Matching Polynomials.

Counting with Symmetric Functions.

Posets: Mobius Functions.

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. Also, we may make use of the following notes on rook polynomials written by Jeff Remmel. rookchap1.pdf. Some other notes on rook polynomials (an earlier version of the book, which contains some material not yet in rookchap1.pdf) Notes on Rook Polynomials.

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 5pm (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.

Midterm 2: The exam will be a closed book exam. No notes, calculators, cell phones, etc. will be allowed. The exam covers material from:

Sections 2.1-2.4, 2.7 from Stanley's Enumberative Combinatorics, Volume 1,

Material from the "Notes on Rook Polynomials" at the link above, pages 1-7 (up to equation (1.35)) and pages 17-20 (up to Corollary 2.8.1), and

Sections 7.1, 7.2, 7.3 (up to and including page 222), 7.6 and 7.7 from Chapter 7, "Counting with Symmetric Functions", of Sagan's draft of his new book.

Take-Home Final Exam (Due Thursday, Dec. 19 by 5pm, either under my office door or as a pdf attachement to an email.

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

HW2 (due in class on 11/7):
(1) Give a combinatorial proof that D(n) = (n-1)D(n-1)+(n-1)D(n-2), where D(n) is the number of derangements of n things.
(2) Do exercises 6, 7, 10, 25, and 35 from Chapter 2 in Stanley's Enumberative Combinatorics, 2nd Edition.