Problems in Enumerative Combinatorics (for Math 5020-001 Fall 2020)

(Adopted from a structure created by and problems assigned by Richard Stanley for his Fall 2016 course in enumeration at MIT.)

Difficulty rating of problems (adapted from EC1ed2, p. 103):

1. 1. easy: most students should be able to solve it;
2. 2. moderately difficult: many students should be able to solve it;
3. 3. difficult: a few students should be able to solve it;
4. 4. horrendous: no students should be able to solve it (without already knowing how or using deep machinery not a prerequisite for the course);
5. 5. unsolved.

Further gradations are indicated by + and −. Thus a [3−] problem is about the most difficult problem that makes a reasonable homework exercise, and a [5−] problem is an unsolved problem that has received little attention and may not be too difficult.

The actual grade on a homework problem is based on the following somewhat harebrained scheme. Each problem has a difficulty factor [d], such as [3−]. This is converted into a weight w(d), as follows.

• w(1−) = 0.1, w(1) = 0.3, w(1+) = 0.5
• w(2−) = 1, w(2) = 2, w(2+) = 3
• w(3−) = 5, w(3) = 8, w(3+) = 12
• w(4−) = 18, w(4) = 25, w(4+) = 50
• w(5−), w(5): depends on solution

Hand in at most one part from any multipart problem whose parts have separate difficult factors. If a multipart problem has an overall difficulty factor but the individual parts do not, then hand in all parts. Each problem or part of a problem will have ten points. Your grade on a problem will be the number of points you receive (out of 10) times the difficulty weight. The weights assume that you solved the problem from scratch using material from class covered to that point and basic math knowledge for a first-year combinatorics graduate student. If it appears that you already had some familiarity with the problem or use some deep result that most other students in the course won't know, the weight may be reduced.

A problem number preceded by A indicates one of the "Additional Problems" to be handed out in class. All other problems are from the text. If you've taken a version of this class before, please choose problems that you haven't previously solved.

You are welcome to discuss problems with me or other students, and I'm happy to give hints. Please do not try to look up the specific problems and solutions on the internet. You won't learn nearly as much that way. (Searching for general information in the area of the problem is OK.) If you find the exact solution to one of the assigned problems, please let me know where it is. Also please make sure you write up the solution in your own words and cite any resources that helped you significantly.

Problem Set 1 (due 1 October 2020) Turn in your "best" four problems from 1.4 (i.e., Chapter 1, Problem 4 (page 104)), 1.5, 1.7, 1.12, 1.17, 1.29, 1.33, A1, A2, A3. There is a 50% penalty on Problem 1.12 for using induction, recurrences, generating functions, summations, finite differences, etc. Problem 1.33(b) seems a little more difficult than a typical [2+] problem so has a weight w(2++)=4. There is a 20% penalty for solving 1.33(b) using linear algebra.