Math 5800, Fall 2021

Prof. Jim Haglund, jhaglund@math.upenn.edu
Course webpage: http://www.math.upenn.edu/~jhaglund/5800/

Office hours:

Office Phone: (215) 573-9093.

Lecture: TR 10:15-11:44am in DRL 2C2

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 1, Second Edition by Richard Stanley, available on Amazon and (hopefully soon) at the Penn bookstore. A good auxillary text is The Art of Counting by Bruce Sagan. Specific topics to be covered in the course include:

Basic Objects and Techniques in Combinatorial Analysis: Partitions, Compositions, Generating Functions, Permutation Statistics, Eulerian Polynomials, Multiset Permutations, q-Binomial Coefficients, Stirling and Bell Numbers.

Involutions, Determinants.

Inclusion-Exclusion.

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

Counting with Symmetric Functions.

Posets: Mobius Functions.


Another good auxillary reference for this course I recommend is generatingfunctionology, by Herb Wilf. Stanley's book is on reserve in the Physics/Math Library on the 3rd floor of DRL. Also, we will cover much of Chapter 1 from my book The q,t-Catalan Numbers and the Space of Diagonal Harmonics". We may make use of the following notes on rook polynomials: 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. 5 from 10:15-11:44am in DRL 2C2 and Midterm 2 will be on Thursday, Nov. 16 from 10:15-11:44am, also in DRL 2C2. Both the midterms will be closed-book, no notes, smart phones, calculators, etc. The final exam will be a take-home exam, due on Wednesday, Dec. 20 by 5pm (under my office door, or as an pdf attachment to an email).

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 on alternating permutations (pp. 44-47), and also multiset permutations, partition identities, and the Twelvefold way (pp. 55-80).

• The proof that the number of parking functions equals (n+1)^{n-1}, the proof that the Eulerian polynomials have only real zeros, and the proof using generating functions that the nth Catalan number (defined as 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), equals the binomial coefficient (2n choose n), divided by n+1.

• Pages 1-7 from Chapter 1 of my book "The q,t-Catalan numbers ..." on Foata's map between inv and maj on permutations and basic properties of Catalan numbers and q-binomial coefficeints.

• Material on rook placements, vector compositions and Simon Newcomb's Problem from pages 1-6 of "Notes on Rook Polynomials"


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

• Material on zeros of rook polynomials and matching polynomials from Chapter 2 of "Notes on Rook Polynomials" (Heilmann-Lieb Theorem, Monotone Permanent Conjecture, Grace's Theorem, Transformations which preserve the property of having only real zeros,...).

• Material on Symmetric Functions from "Counting with Symmetric Functions" and other material from Chapter 7 of Stanley's "Enumerative Combinatorics, Volume 2" (Various bases of Sym, including the complete homogeneous symmetric functions, the elementary symmetric functions, the monomial symmetric functions, the power sum symmetric functions, and the Schur functions. The RSK algorithm and its applications. The Jacobi Trudi identity, the Cauchy identity, and the Hall scalar product).

Take-Home Final Exam (Due Wednsaday, Dec. 20 by midnight, either under my office door or as a pdf attachement to an email.

Important Dates:
Tuesday, August 29: Classes begin
Midterm 1: Thursday, Oct. 5, 10:15-11:44am in DRL 2C2
Last Day to Drop a Course: Oct. 9.
Fall Break: Thursday, Oct. 12 - Sunday, Oct. 15.
Last Day to Withdraw from a Course: Nov. 6.
Midterm 2: Thursday, Nov. 16, 10:15-11:44am in DRL 2C2
Thanksgiving Break: Thursday, Nov. 23 - Sunday, Nov. 26
Last Day of Classes: Monday, Dec. 11
Take-home Final exam due on Dec. 20 by 5pm.

Homework Assignments:

HW1 (due in class on Thursday 9/28).

HW2 (due in class on Tuesday 11/14, or earlier as a pdf attchment in an email sent to jhaglund@math.upenn.edu).