Math 249: Algebraic Combinatorics—Spring 2015

Time and place
Homework and grading
List of topics by lecture
Problem sets


(5/1) Problem Set 5 posted, due May 15, the last day of final exams. There is no final exam for this class.
(4/15) Problem Set 4 posted, due on May 1, the last class meeting. I plan to post one more problem set to be due at the end final exam week.
(3/2) Problem Set 3 posted.
(2/9) Problem Set 2 posted.
(2/5) Pointers on this page to Stanley EC Vol 1 now refer to the 2nd edition. If you have the 1st edition, you may wish to consult the 2nd edition manuscript on Stanley's EC web page, which has an appendix listing material re-numbered between editions.
(1/28) Problem Set 1 now posted, see below.
(1/3) Welcome to Math 249!


Mark Haiman,
Office hours Wednesdays 11:00-12:30 or by appointment

Time and place

MWF 2-3 pm, Room 2 Evans Hall


The course will loosely follow

Among other useful information on Stanley's web page, linked above, you can find a PDF manuscript version of Volume I, 2nd edition.

I will give pointers to reading from Stanley for many of the lectures, and include a number of problems from Stanley in the homework assignments.

For some course topics you may also find the following helpful:

Homework and grading

Problem sets are below, after the list of lecture topics. I'll post new sets at irregular intervals, due about two weeks after posted. Grades will be based on homework; there will be no exams. To get an A in the course, you should do most of the probems, not skipping the harder ones.


  1. Ordinary generating functions and enumeration of sets, mappings, multisets, distributions, permutations, words, lattice paths, trees, and other basic combinatorial objects.
  2. Combinatorial species, exponential generating functions and cycle index. Combinatorial interpretation of Lagrange inversion.
  3. Posets, lattices and incidence algebras. Mobius inversion. Geometric lattices and their characteristic polynomials. Brief discussion of polytopes, simplicial complexes and shellability.
  4. Symmetric functions. Character theory of the symmetric groups Sn and general linear groups GLn.
  5. q-analogs in enumeration and symmetric function theory. Geometry and combinatorics of Hall-Littlewood polynomials and the Hall algebra.
  6. q,t-analogs and Macdonald polynomials.

List of topics by lecture

I will update this list as the course proceeds. Pointers to Stanley, EC Vol 1 refer to the 2nd edition.

  1. (1/21) Basic counting principles; ordinary generating functions; enumeration of words, permutations, sets and multisets. [Stanley 1.1-1.2]
  2. (1/23) Formal power series. Sets and multisets continued.
  3. (1/26) Binomial coefficient identities; binomial inversion. The `12-fold way.' Stirling numbers S(n,k). [Stanley 1.9]
  4. (1/28) Signless Stirling numbers of the 1st kind c(n,k); ordinary generating functions for c(n,k) and S(n,k).
  5. (1/30) Integer partitions. Partition identities. Combinatorial interpretation of Rogers-Ramanujan identities. [Stanley 1.8]
  6. (2/2) Euler's pentagonal number identity and recurrence for p(n). Sylvester's identity. q-binomial and multinomial coefficients. [Stanley 1.7]
  7. (2/4) q-Binomial Theorems and Cauchy's identity. [Stanley 1.8]
  8. (2/6) Subspaces of (Fq)n. Descents of permutations; quasisymmetric expansion of (x1 + x2 + ···)n. [Stanley 7.19]
  9. (2/9) Counting permutations by major index. [Stanley 1.4]
  10. (2/11) Double partitions and symmetry of π qinv(π) tmaj(π).
  11. (2/13) Counting ordered rooted trees and other Catalan enumerations. [Stanley 1.5]
  12. (2/18) Cayley's tree enumerator. Matrix-Tree Theorem. [Stanley 5.6]
  13. (2/20) Matrix-Tree applications. Intro to species.
  14. (2/23) Exponential generating function of a species; sum and product of species. [Stanley 5.1-2]
  15. (2/25) Composition of species. Mixed ordinary and exponential generating functions. Examples: partitions, permutations, trees, exponential generating functions for S(n,k) and c(n,k).
  16. (2/27) Counting trees using functional digraphs. Lagrange inversion formula from Cayley's tree enumerator. [Stanley 5.3-4]
  17. (3/2) Counting structures of a species up to isomorphism. Cycle index.
  18. (3/4) Decorated species and plethystic evaluation ZF[A] of cycle indices.
  19. (3/6) Plethysm and the cycle index for composite species.
  20. (3/9) Species examples with computer demo: (i) connected graphs up to isomorphism, counted by number of vertices and edges; (ii) unrooted trees up to isomorphism.
  21. (3/11) Posets and distributive lattices. [Stanley 3.1-3.5]
  22. (3/13) Incidence algebras, Mobius function. Principle of Inclusion-Exclusion as an example of Mobius inversion. [Stanley 3.6-3.8]
  23. (3/16) Classical (number theoretic) Mobius inversion. Chromatic polynomial as a characteristic polynomial. Mobius function of partition lattice Πn from chromatic polynomial of the complete graph Kn. General formulas for the Mobius function of a lattice. [Stanley 3.9-3.10]
  24. (3/18) Reduced incidence algebras. Incidence algebra interpretation of multiplication and composition of formal series. Mobius function of Πn revisited.
  25. (3/20) Order polynomials and reciprocity. Acyclic orientations and value χG(−1) of the chromatic polynomial of a graph. [Stanley 3.12, 3.15]
  26. (3/30) Symmetric functions. Ordering on partitions. Monomial and elementary bases. [Stanley 7.1-7.4]
  27. (4/1) Complete homogeneous and power-sum symmetric functions. Involution ω. [Stanley 7.5-7.8]
  28. (4/3) Scalar product and Cauchy identities. Schur functions: combinatorial definition, symmetry, quasi-symmetric expansion. [Stanley 7.9, 7.10]
  29. (4/6) RSK algorithm. [Stanley 7.11]
  30. (4/8) Orthormality of Schur functions; ω(sλ). [Stanley 7.12]
  31. (4/10) Pieri formulas. Bialternant formula sλ(x1,...,xn) = aλ+δ/aδ. [Stanley 7.15]
  32. (4/13) Polynomial representations of GLn and their characters. Bialternant interpreted as Weyl character formula. [Stanley Ch. 7 Appendix 2]
  33. (4/15) Jacobi-Trudi formula for sλ/μ. Jeu-de-taquin. Schensted insertion understood as rectification. [Stanley Ch. 7 Appendix 1]
  34. (4/17) Statement of main theorem on jeu-de-taquin. Preservation of descent set; generalization to semi-standard tableaux. Computation of skew schur functions by rectification. Dual equivalence.
  35. (4/20) Dual equivalence on straight shapes. Reduction to elementary dual equivalences.
  36. (4/22) Exchange lemma for jeu-de-taquin on posets. Proof of main theorem on jeu-de-taquin. Yamanouchi tableaux and the Littlewood-Richardson rule.
  37. (4/24) Characters of finite groups. Frobenius map, relation to cycle index of a species, isometry property. [Stanley 7.18]
  38. (4/27) Irreducible characters of symmetric groups Sn. Plethystic substitution.
  39. (4/29) Murnaghan-Nakayama rule. Definition of LLT polynomials.
  40. (5/1) More on LLT, Hall-Littlewood and Macdonald polynomials.

Problem sets

Back to top | Prof. Haiman's home page | Calendar