# 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

The book is available at the bookstore and will be put on reserve in the Reserve Reading Room. Despite the name and a certain tendency towards enumeration, the book goes far beyond that and is an excellent introduction to much of combinatorics as a whole.

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.

## Course Outline

Short outline:

• Stanley, Chapters 1 to as far as we get, probably somewhere in Chapter 4. Stanley's chapters are big; many of his sections could have been called chapters. We will cover as many sections as we can.

## Textbook Corrections

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

• 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 si+1 should be sj+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 rB(x) := Sumk≥0 rk xk. Note that the size of the board (i.e., n) is not recoverable from rB(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 (b1,b2,...,bm) 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: ATa = 0 should be VTa = 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 (x1,...,xn) of the elements of P such that x1 < ... < xn 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(Γ6) = \hat P(Γ5)*.
• 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: