**Math 580-001, Fall 2019**

**Prof. Jim Haglund, ** jhaglund@math.upenn.edu

Course webpage:
http://www.math.upenn.edu/~jhaglund/580/

**Office hours (all in DRL 4E2B): **

M, 9-9:50am.

W, 10:30-11:30am.

**
Office Phone:**
(215) 573-9093.

**Grader: Logan Crew, crewl@sas.upenn.edu**

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

Inclusion-Exclusion.

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

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