Professor: Mark Haiman

Professor Haiman's Office: 855 Evans Hall. Office hour Mondays 12:30-2pm.

Catalog description: Basic combinatorial principles, graphs, partially ordered sets, generating functions, asymptotic methods, combinatorics of permutations and partitions, designs and codes. Additional topics at the discretion of the instructor.

Lectures: MWF 11-12pm, Room 71 Evans

Course Control Number: 54557

Prerequisites: Math 55

Text: Miklos Bona, A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, Second Edition (World Scientific, 2006).

Homework: Weekly problem sets due each Wednesday

Exams:

• Midterm exam in class, Friday, March 12.
• Final exam Tuesday, May 11, 7-10pm (exam group 8), Room 71 Evans

Grading: Homework 35%, Midterm exam 20%, Final exam 45%.

Syllabus:

• Counting basics: sum and product principles, pigeonhole principle. Review of mathematical induction.
• Elementary enumeration problems: words, permutations, subsets, distributions
• Binomial and multinomial theorems
• Set partitions; Stirling and Bell numbers
• Integer partitions
• The "twelve-fold way"
• Permutations and their cycle structure
• Ordinary generating functions and examples; Catalan numbers
• Generating functions for elementary enumeration problems
• Partition identities
• Sieve principle (via generating functions)
• Exponential generating functions and examples; exponential structures.
• Graphs and trees. Generating functions for counting trees. Matrix-tree theorem.
• Polya-Burnside theorem.
• Cycle index generating function for species of structures; counting connected graphs up to isomorphism
• Additional topics if time; may include graph coloring and matchings, planar graphs, posets.

Reading and Homework Assignments

• Reading for Lectures 1-3: Bona, Chapters 1-3. Problem Set 1, due Jan. 27 (corrected 1/22; the previous version was based on exercise numbers from the old edition of the book); PS 1 Solutions.
• Reading for Lectures 4-6: Chapters 4 and 5.1-5.2. Problem Set 2, due Feb. 3; PS 2 Solutions. Note: problem 4.37 was graded but not counted, because it turned out that the problem was misprinted in some versions of the book.
• Reading for Lectures 7-9: Chapter 5 continued. Problem Set 3, due Feb. 10 (problem D corrected 2/8); PS 3 Solutions.
• Reading for Lectures 10-11: Come to class! (or get notes from another student who did, on "12-fold way"). Also, Chapter 6. Problem Set 4, due Feb. 17. This homework is a bit shorter than usual, since Monday is a holiday. PS 4 Solutions.
• Reading for Lectures 12-14: Chapter 6 continued, Chapter 8 up through 8.1.2, additional Notes on Ordinary Generating Functions. Problem Set 5, due Feb. 24 (Note: Problem A(b) was wrong, fixed 1/22. I also changed Problem C, since we didn't get as far in the lecture as I hoped when I made up the problems.) PS 5 Solutions.
• Reading for Lectures 15-17: Chapter 8 through 8.1.3, Notes on Ordinary Generating Functions. Problem Set 6, due March 3. PS 6 Solutions.
• Reading for Lectures 18-20: Notes on Partitions and their Generating Functions. Problem Set 7, due March 10 (typo in Problem D corrected 3/7); PS 7 Solutions. Reminder: Midterm Exam is Friday, Mar. 12, in class, covering the material on Problem Sets 1-6.
• Midterm Exam Solutions
• Reading for Lectures 21-22: Chapter 7. Problem Set 8, due March 17 (a short one, since March 12 is the midterm exam); PS 8 Solutions.
• Announcement: Mar. 15 through Apr. 2, our class will move to Room 118 Barrows Hall so that equipment can be installed in 71 Evans.
• Reading for Lectures 23-25: Chapter 9 (for definitions), 10.1, and Notes on Ordinary Generating Functions, sections 3 and 4. Problem Set 9, due March 31. (Correction 3/29: problems C and D only require an algebraic identity for V(x), not a closed formula.) PS 9 Solutions.
• Reading for Lectures 26-28: Notes on Matrix-Tree theorem and Cayley's tree enumerator, sections 1 and 2. Problem Set 10, due April 7; PS 10 Solutions.
• Reading for Lectures 29-31: 10.3-10.4; Matrix-Tree and Cayley Notes, sections 3 and 4. Problem Set 11, due April 14; PS 11 Solutions.
• Reading for Lectures 32-34: 8.2, Notes on exponential generating functions and structures. (Caveat: the example of alternating permutations discussed in Section 7 of the notes is not actually a combinatorial species, since the definition of the structure depends on the specific set X={1,...n}, or more precisely, on the intrinsic ordering of X.) Problem Set 12, due April 21; PS 12 Solutions.
• Reading for Lectures 35-39: Additional notes on exponential generating functions and Notes on cycle generating functions. You will probably find this last set of notes harder reading than the others, but I'll give you some clues in the lectures. Problem Set 13, due Friday, April 30. Note: since some of the homework problems are on material that I'll finish covering in Friday's lecture, you may turn in PS 13 under my office door (855 Evans) at any time on Friday. I'll pick it up Saturday morning. PS 13 Solutions.
• I'll have RRR week office hours MW 11-1. I expect to have the graded last homework back by the Wednesday office hour.
• Final Exam is Tuesday, May 11, 7-10pm, in 71 Evans. Any topics covered in class and/or homework may be on the exam. Rules and format are the same as on the midterm. You may bring one sheet of notes (written on both sides). There will be space for answers on the exam itself, but you should bring your own scratch paper.
• Final Exam Solutions (correction: in the solution to Problem 7 I left out 4 edges from the picture, and the matrix should have 4's on the diagonal, not 3's).