Readings

Key

[AC] = Stanley, Richard P. Algebraic Combinatorics: Walks, Trees, Tableaux, and More. Springer, 2018. ISBN: 9783319771724. Online 2013 version.

[EC1] = ———. Enumerative Combinatorics. Vol. 1. Cambridge, UK: Cambridge University Press, 1997. ISBN: 9780521553094. Online version.

[EC2] = ———. Enumerative Combinatorics. Vol. 2. Cambridge, UK: Cambridge University Press, 2001. ISBN: 9780521789875. 

Lecture sessions with reading assignments are listed below.

LEC # TOPICS READINGS

2

Catalan numbers (cont.): formula for Cn, reflection principle, necklaces, triangulations of polygons, plane binary trees, parenthesizations.

Stanley, Richard P. This resource may not render correctly in a screen reader."Exercises on Catalan and Related Numbers" (PDF). (excerpted from [EC2])

Stanley, Richard P. This resource may not render correctly in a screen reader."Catalan Addendum" (PDF).

3

Pattern avoidance in permutations. Stack- and queue-sortable permutations. Young diagrams and Young tableaux. Hook-length formula.

[AC] This resource may not render correctly in a screen reader."Chapter 8: A Glimpse of Young Tableaux" (PDF - 1.2MB).

If you want to learn more details about the links between combinatorics of Young tableaux and representation theory, see Sagan, Bruce E. The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. Springer, 2001. ISBN: 9780387950679.

4

Frobenius-Young identity. Schensted correspondence. Longest increasing and decreasing subsequences in permutations.

[AC] This resource may not render correctly in a screen reader."Appendix 1 to Chapter 8: The RSK Algorithm" (PDF - 1.2MB).

Schensted, C. "Longest Increasing and Decreasing Subsequences." Canadian Journal of Mathemetics 13 (1961), 179-191.

Knuth, Donald E. This resource may not render correctly in a screen reader."Permutations, Matrices, and Generalized Young Tableaux" (PDF). Pacific Journal of Mathematics 34 (1970), 709-727.

Greene, Curtis. This resource may not render correctly in a screen reader."An Extension of Schensted's Theorem" (PDF). Advances in Mathematics 14 (1974), 254-265.

5

Proof of the hook-length formula based on a random hook walk.

Greene, Curtis, Albert Nijenhuis, and Herbert Wilf. This resource may not render correctly in a screen reader."A Probabilistic Proof of a Formula for the Number of Young Tableaux of a Given Shape" (PDF). Advances in Mathematics 31 (1979), no. 1.

6

Hook walks (cont.). Linear extensions of posets. Hook-length-type formulas for shifted shapes and trees.

Knuth, Donald E. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley Professional, 1998. Section 5.1.4. ISBN: 9780201896855.

7

q-factorials and q-binomial coefficients.

[AC] This resource may not render correctly in a screen reader."Chapter 6: Young Diagrams and q-binomial Coefficients" (PDF - 1.2MB).

8

Grassmannians over finite fields: Gaussian elimination and row-reduced echelon form.

[EC1] This resource may not render correctly in a screen reader."Section 1.7: Permutations of Multisets" (PDF - 4.4MB). (see Propositions 1.7.2 and 1.7.3)

9

Sets and multisets. Statistics on permutations: inversions, cycles, descents.

[EC1] This resource may not render correctly in a screen reader."1.2 Sets and Multisets" (PDF - 4.4MB), This resource may not render correctly in a screen reader."1.3 Cycles and Inversions" (PDF - 4.4MB), and This resource may not render correctly in a screen reader."1.4 Descents" (PDF - 4.4MB).

15

Posets and lattices. Boolean lattice. Partition lattice. Young's lattice.

[EC1] Chapter 3: Partially Ordered Sets: This resource may not render correctly in a screen reader."3.1 Basic Concepts" (PDF - 4.4MB), This resource may not render correctly in a screen reader."3.2 New Posets from Old" (PDF - 4.4MB), and This resource may not render correctly in a screen reader."3.3 Lattices" (PDF - 4.4MB).

16

Distributive lattices. Birkhoff's fundamental theorem for finite distributive lattices.

[EC1] This resource may not render correctly in a screen reader."3.4 Distributive Lattices" (PDF - 4.4MB).

17

Sperner's property. Symmetric chain decompositions. Sperner's and Dilworth's theorems. Greene's theorem.

[AC] This resource may not render correctly in a screen reader."Chapter 4: The Sperner Property" (PDF - 1.2MB).

18

Greene's theorem vs Schensted correspondence. Up and down operators. Differential posets.

[EC1] This resource may not render correctly in a screen reader."3.21 Differential Posets" (PDF - 4.4MB).

19

Differential posets (cont.). Fibonacci lattice. Unimodality of Gaussian coefficients.

[AC] This resource may not render correctly in a screen reader."Chapter 6: Young Diagrams and q-binomial Coefficients" (PDF - 1.2MB). (see Corollary 6.10)

20

Proof of unimodality of Gaussian coefficients (cont.). Theory of partitions. Euler's pentagonal number theorem.

[EC1] This resource may not render correctly in a screen reader."1.8 Partition Identities" (PDF - 4.4MB).

23

Two combinatorial proofs of Cayley's formula.

[AC] Chapter 9. This resource may not render correctly in a screen reader."Appendix: Three Elegant Combinatorial Proofs" (PDF - 1.2MB).

Egecioglu, Ömer and Jeffrey B. Remmel. "Bijections for Cayley Trees, Spanning Trees, and Their q-analogues." J. Combinatorial Theory, Ser. A, 42 (1986), 15-30.