Problems in Enumerative Combinatorics (for Math 5020-001 Spring 2017)

(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 EC1, second ed., 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. I've indicated ones I've assigned in previous years in bold.

Problem Set 1 (due 7 12 February 2017) 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.

Problem Set 2 (due 8 March 2017) Turn in your "best" four problems from 1.38, 1.44, 1.53, 1.54 (answer should not involve summations), 1.84, 1.87, A6, A8, A10, A11.

Problem Set 3 (due 3 April 2017) Turn in your "best" four problems from 1.47(a,b)[counts as one problem], 1.108(b), 1.113, 1.132, 1.138, 2.25, 2.26, A4, A7.

Problem Set 4 (due 1 May 2017) Turn in your "best" three problems from A9, A17, A30, A31, A32, A33.