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.

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.

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.

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**should be_{i+1}**s**. (Stanley's own correction (Website) is incorrect.)_{j+1} - 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
_{1},b_{2},...,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*_{π}}

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

**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.- The standard one is that a linear extension of P is a total ordering (of the same set) that, as a relation, contains P.
- An obviously equivalent definition is that it is a permutation (x
_{1},...,x_{n}) of the elements of P such that x_{1}< ... < x_{n}is a linear extension in the first sense. - Stanley's definition is equivalent to these as indicated in the book, but it is not the same.

- 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:
- Rook polynomial: [ADD definition]
- Stirling number of the second kind:
- exercise, [ADD] 87, 92
- formula, 38

To my home page.