Math 5800, Combinatorial Analysis, Fall 2025

Math 5800-001, Fall 2025

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

Office hours after Dec. 4: F Dec. 12 from 11:00am-noon in DRL 4E2B

Office Phone: (215) 573-9093.

Lecture: TR 12 noon - 1:30pm in DRL 4E9

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 the 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. 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 (in-class) hour exams and a (take-home) 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 Tuesday, Sept. 30 from 12noon-1:30pm in DRL 4E9 and Midterm 2 will be on Thursday, Nov. 20 from 12noon-1:30pm in DRL 4E9. Both the midterms will be closed-book, no notes, smart phones, calculators, etc.

For Midterm 1, you should be able to reproduce proofs that we covered in class (or any other proof that you know) of

Euler's pentagonal number theorem, Foata's prooof that inv and maj have the same distribution over permutations and multiset permutations

Formulas for the number of compositions of n into k parts, proof that the number of lattice paths from (0,0) to (n,n) is (2n)!/(n+1)!n!, proof that the number of colorings of a graph on n vertices with x colors is a polynomial in x, formula for the number of parking functions on n cars

Proof that the Eulerian polynomials have only real zeros

For Midterm 2, you should be able to reproduce proofs that we covered in class (or any other proof that you know) of

Basic results involving rook polynomials: definition of rook and hit numbers, Goldman-Joichi-White factorization theorem for Ferrers boards, Problem des Menage. (See Notes on Rook Polynomials, Chapter 1, and Stanley, Chapter 2).

Applications of rook polynomials to Simon Newcomb's problem and vector compositions. (See Notes on Rook Polynomials, Chapter 1).

Heilmann-Lieb Theorem on zeros of weighted matching polynomials. (See Notes on Rook Polynomials, Chapter 2).

You should be able to give an outline of the two proofs of the hook-length formula (the probabilistic proof and the proof based on the Hillman-Grassl algorithm (see Sagan, pp. 230-235).

Give an outline of the proof of the Jacobi-Trudi identity using the Gessel-Viennot method of nonintersectiong lattice paths (See Sagan, Theorem 7.2.3 (a) ).

Important Dates:
Tuesday, August 26: Classes begin

Important Dates:
Tuesday, August 26: Classes begin
Midterm 1: Tuesday, Sept. 30 from 12noon-1:30pm in DRL 4E9
Last Day to Drop a Course: Oct. 6.
Fall Break: Thursday, Oct. 9 - Sunday, Oct. 12.
Grade mode change deadline Oct. 24.
Last Day to Withdraw from a Course: Nov. 3.
Midterm 2: Thursday, Nov. 20 from 12noon-1:30pm in DRL 4E9
Thanksgiving Break: Thursday, Nov. 27 - Sunday, November 30.
Last Day of Classes: Monday, Dec. 8.
Take-home Final exam due on Dec. 18 by 11:59pm, as a pdf attachment to an email.

Take-home Final Exam:

Final Exam Due by 11:59pm on Thursday, Dec. 18. Upload a pdf to canvas, email a pdf to me, or slide a hard copy under my office door.

Homework Assignments:

HW1 Due on Thursday, Sept. 18. Turn in a hard copy in class, or upload a pdf to canvas.

HW2 Due on Tuesday, Dec. 5. Turn in a hard copy in class, or upload a pdf to canvas.