Math 511: Introduction to Combinatorics
Spring 2005

This course is an introduction to many of the basic concepts, constructions, and examples of combinatorics. It is taught from the textbook of

• Richard P. Stanley, Enumerative Combinatorics, Vol. 1, corrected reprint, Cambridge University Press, 1997.

The course is not an introductory graduate course. The absolute minimum requirement is a good understanding of abstraction and a solid modern algebra background (as from a graduate course), and the more graduate math you know, the better (that's the famous "mathematical maturity"). If you aren't sure whether you might be interested or ready for this class, please see me.

We meet on MWF 2:20 - 3:20 in LN-2205.

	Special class times:
	Wed. Feb. 9: No class.
	Fri. Feb. 11: We meet 2:20-3:20 in the usual room and continue 3:30-4:30 in LN-2201.

There is a Combinatorics Seminar that will try to meet at a time convenient for all.

Click here for a class schedule with readings and homework instructions.

I will expect you, the students, to study the material and to work on as many of the exercises as you can. (Most have solutions in the book, but of course you shouldn't look at them until you get seriously stuck.) I will meet separately with each student frequently (every week or two) to discuss your progress and any questions you or I may have. I will frequently collect written work (see the homework assignments). There will probably be a take-home final.

Textbook Corrections

There are some corrections in the back of the book. Stanley has a Web page of corrections and supplementations.

Here are additional corrections and comments of my own.

• Page 17, line 5-: ``left-to-right maxima'' are known as outstanding elements (in French ``éléments saillants'', Rényi (1962); translation by MR 44 #3376; also see Zbl. 139, p. 353), although a better name in English might be projecting elements.
• Page 25, line 11: Greene-Zaslavsky (1983; MR 84k:05032) call ``left-to-right minima'' retreating elements.
• Page 50, line 6-, #43(b): It is necessary to give three initial conditions. Presumably Stanley intends a_-2 = a_-1 = 0. (?)
• Page 70, equation (21): Both cases of s_i+1 should be s_j+1. (Stanley's own correction (Website) is incorrect.)
• Page 74, line 7: There is no definition of the rook polynomial of a board B. It is r_B(x) := Sum_k≥0 r_k x^k. Note that the size of the board (i.e., n) is not recoverable from r_B(x).
• Page 74, definition of a Ferrers board: For the proof of 2.4.1 to make sense, the (i,j) coordinates must be viewed as Cartesian (x,y) coordinates, not matrix-style coordinates as they usually are for boards. Thus, a Ferrers board description (b₁,b₂,...,b_m)_≤ is a list of column heights from left to right.
• Page 75, Theorem 2.4.4: The proof is very abbreviated. Especially, one must verify that every Ferrers board that ought to be counted actually is counted.
• Page 83, line 4-: In case the termini of the paths are not all distinct, the union of the A_π should be a disjoint union. A more formally correct setup would be to associate each n-path with a particular π, i.e., define

  A' = { (L,π) : L belongs to A_π }

  and

  sgn(L,π) = sgn(π).

  Then * acts by (L,π)* = (L*,π).
• Page 92, line 5: A_T^a = 0 should be V_T^a = 0.
• Page 106, line 8-: In the correction on p. 321 one might add, more specifically, that the zero element = join of the empty set.
• Page 110, definition of linear extension: Warning! There are really two and a half possible definitions.
  1. The standard one is that a linear extension of P is a total ordering (of the same set) that, as a relation, contains P.
  2. An obviously equivalent definition is that it is a permutation (x₁,...,x_n) of the elements of P such that x₁ < ... < x_n is a linear extension in the first sense.
  3. Stanley's definition is equivalent to these as indicated in the book, but it is not the same.
  I'm not sure Stanley always means the last definition. Sometimes you may have to think of a "linear extension" in the first or second sense in order to understand an exercise or statement.
• Page 111, line 3-: Change "m element" to "m-element".
• Page 113, definition of the incidence algebra, and in particular page 116, definition of the Möbius function: Stanley defines an incidence-algebra function φ as having domain Int(P), but it is also common to treat it as having domain P × P and the property that φ(x,y)=0 when x is not ≤ y. Sometimes the latter definition is more useful, e.g., in summations.
• Page 122, Figure 3-30, caption: \hat P(Γ₆) = \hat P(Γ₅)*.
• Page 127, Ex. 3.10.3: Stanley chooses to say that the null set doesn't span anything. However, it is standard in linear algebra that the null set spans the zero subspace, {0}, and I believe this is most consistent with the definition of span.
• Page 192, Ex. 57, answers: The range of m in each formula should be: m in C for the first and third, and m ≥ 3 in the second; where also the range of j should be 2 ≤ j ≤ m-1. (I'm not sure why Stanley says 1 ≤ j ≤ m and m ≥ 1.)
• Index:
  • Rook polynomial: [ADD definition]
  • Stirling number of the second kind:
    • exercise, [ADD] 87, 92
    • formula, 38

To my home page.