Math 580-001, Fall 2019
Prof. Jim Haglund, email@example.com
Course webpage: http://www.math.upenn.edu/~jhaglund/580/
Office hours (all in DRL 4E2B):
Grader: Logan Crew, firstname.lastname@example.org
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
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.
Rook Polynomials: Permutations with Restricted Position, Zeros of Rook Polynomials and Matching Polynomials.
Counting with Symmetric Functions.
Posets: Mobius Functions.
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
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.
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
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.