Math 249: Algebraic Combinatorics—Fall 2016

Time and place
Subject matter
Homework and grades
Problem sets
List of lecture topics


(8/15) Welcome to Math 249! Watch this page for further information.
(9/7) Problem Set 1 posted, due in 3 weeks.
(10/19) Problem Set 2 posted, due in 3 weeks.
(11/29) Problem Set 3 posted, due during finals week.


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

Time and place

MWF 3-4 pm, Latimer 105

Subject matter

The first part of the course will be an introduction to classical combinatorial enumeration, ordinary and exponential generating functions and their unification using the theory of species, along with related topics such as partition identites and Lagrange inversion.

Next we will turn to combinatorial theory of symmetric functions and Young tableaux, including Hall-Littlewood, LLT and Macdonald polynomials, and their connections with representations of the symmetric and general linear groups, and with the geometry of flag varieties and Hilbert schemes.

If we have time, I might also discuss the relationship of Hall-Littlewood and LLT polynomials to Kazhdan-Lusztig theory.


There is no required textbook for this course. I will give a self-contained presentation of the material in the lectures. You may, however, find some of the following useful as reference texts.

The UC library links above should work from computers on campus. You can access library resources from off campus by using the library Proxy Server.

Homework and grades

I'll post problem sets below at irregular intervals, generally due 2-3 weeks after posting. Grades will be based on homework. There will be no exams. To get an A in the course, you should do most of the problems, not skipping the harder ones.

You can turn in problems in class, at my office (slip them under the door if I'm not in), or by e-mail as PDF files.

Problem sets

List of lecture topics

I will update this list as the course goes on. Pointers to Stanley Vol. I (that is, Chapters 1-4) refer to the 2nd edition.

  1. (8/24) Ordinary generating functions. Example: counting ordered rooted trees (Catalan numbers).
  2. (8/26) Some more things enumerated by Catalan numbers. Formal power series and how to work with them. [Stanley 1.1]
  3. (8/29) The "12-fold way" of basic enumeration problems. Binomial and multiset coefficients; distributions. Stirling numbers (2nd kind). [Stanley 1.9]
  4. (8/31) 12-fold way continued. Binomial and multinomial theorems. q-Binomial and q-multinomial coefficients. [Stanley 1.7]
  5. (9/2) Lattice path and finite field interpretations of q-binomial and q-multinomial coefficients. Multiset coefficients via generating functions.
  6. (9/7) 1st and 2nd kind Stirling numbers; ordinary generating functions.
  7. (9/9) Partition generating functions. Partititions with distinct parts, odd parts, or other restrictions. q-Binomial Theorems. [Stanley 1.8]
  8. (9/12) Applications of q-Binomial Theorems: Cauchy's identity, Jacobi Triple Product, Euler's pentagonal number formula and recurrence for p(n).
  9. (9/14) Rogers-Ramanujan identities (discussion without proof). Gessel quasi-symmetric functions Qn,D(x) and enumeration of permutations by descent set.
  10. (9/16) More on Qn,D(x). Enumeration of permutations by number of descents and by major index. Eulerian polynomials in terms of Stirling numbers. [Stanley 1.4]
  11. (9/19) Symmetry and significance of w∈Sn qinv(w) tmaj(w).
  12. (9/21) Definition of combinatorial species. Exponential generating function of a species.
  13. (9/23) Sum and product of species. Examples. Exponential generating function and explicit formula for 2nd kind Stirling numbers S(n,k).
  14. (9/26) Composition of species. Examples. Counting rooted trees using function graphs. [Stanley 5.1]
  15. (9/28) Mixed ordinary/exponential generating functions for species enumerated with weights.
  16. (9/30) Lagrange inversion formula. Combinatorial proof using generic species and Cayley's tree enumerator. [Stanley 5.4]
  17. (10/3) Matrix-Tree Theorem. [Stanley 5.6]
  18. (10/5) Cycle index of a species. Specializations to the exponential G.F. for labelled structures and the ordinary G.F. for unlabelled structures.
  19. (10/7) Cycle index of sums, products, and composite species; examples.
  20. (10/10) Polya's formula for the ordinary G.F. for unlabelled rooted trees. Plethystic logarithm. Ordinary G.F.'s for unlabelled graphs, connected graphs, and unrooted trees, counted by number of vertices and number of edges. Computer demo.
  21. (10/12) Symmetric functions in finite and infinite numbers of variables. Basis of monomial symmetric functions. Partial ordering on partitions of n. Theorem that transpose reverses the ordering.
  22. (10/14) Bases of elementary and complete homogeneous symmetric functions, and their coefficients in terms of monomial symmetric functions. Classical fundamental theorem of symmetric functions.
  23. (10/17) Inner product and Cauchy identity. Basis of power-sums. Orthogonality of power-sums.
  24. (10/19) Plethystic substitution; involution ω. Combinatorial definition and symmetry of Schur functions sλ (including skew Schur functions).
  25. (10/21) RSK for permutations. Preservation of descent sets.
  26. (10/24) Orthogonality of Schur functions and formula ω sλ = sλ* via RSK.
  27. (10/26) Adjoints. Basis-free Cauchy identity Ω[AX] f = f[X+A]. Pieri formulas. Littlewood-Richardson coefficients cνλμ = ⟨sν, sλsμ⟩ = ⟨sλ, sν/μ.
  28. (10/28) Representations of GLn and their characters; examples. Symmetry of characters. Statement of the Weyl character formula for GLn.
  29. (10/31) Schur functions as GLn characters and related unsolved, semi-solved and solved combinatorial problems.
  30. (11/2) Constructing irreducible GLn representations. Jacobi-Trudi identity. Representations of Sn and finite groups: basic properties.
  31. (11/4) Representations of Sn and finite groups: examples. Frobenius characteristic map F; isometry property; relation to cycle index of a species. Computation of F(1SnSμ) = hμ.
  32. (11/7) The irreducible characters of Sn.
  33. (11/9) Graded character of Sn on C[z1,...,zn]. Generalized hook formula for sλ(1,t,...,tn-1) and hook formula for number of standard Young tableaux of shape λ.
  34. (11/14) Construction of irreducible representations of Sn.
  35. (11/16) Jeu de taquin: slides, dual equivalence.
  36. (11/18) Jeu de taquin: fundamental theorems.
  37. (11/21) Jeu de taquin for semistandard tableaux. Yamanouchi tableaux (and a bit about crystals). Littlewood-Richardson rule.
  38. (11/28) Hall-Littlewood polynomials Hμ and raising operators.
  39. (11/30) Kλ,μ(q) as q analog of weight multiplicity, in terms of q-root partition function for GLn. Characterization of Hμ by upper and lower triangularities. Sketch of geometric proof of positivity of Kλ,μ(q) using T*(G/B).
  40. (12/2) Charge of words and tableaux. Combinatorial interpretations of Kλ,μ(q) in terms of charge and counterclockwise fillings. Sketch of proof using upper and lower triangularities.

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