MIT OpenCourseWare

Browse materialsMIT 18.212 · Spring 2019

Algebraic Combinatorics

Subjects: Algebra · Mathematics

Art: Johannes Kepler, Konjukce Saturnu a Jupiteru Originál, 1596 · Public domain

Instructor: Prof. Alexander Postnikov
Term: Spring 2019
Level: Undergraduate
What's inside: 8 problem sets · 5 solutions · 1 lecture note · 1 reading · 34 other files · 3 web pages
Materials open: MIT OCW

Start here

Start course: Lecture 1: Catalan numbers: drunkard’s walk problem, generating…Find a topic

Progress is saved in this browser.

Export or import progress

About this course

Source: MIT OpenCourseWare 18.212 Algebraic Combinatorics, Spring 2019, Prof. Alexander Postnikov — original course page on ocw.mit.edu ↗. License: CC BY-NC-SA 4.0. Study order: MIT's own listing order, section by section. Taken from MIT's published course files, downloaded from ocw.mit.edu on September 23, 2026. How RedLectern is built.

Materials are grouped the way MIT organized them. A verified, course-wide order has not been established here.

Has MIT solutions 5 files in this course are named by MIT as solutions.

Before you start

Prerequisites are not listed here. Check MIT's own syllabus for this course.

How this course was organized

What's here, and what isn't

MIT's own materials here did not support a verified, course-wide order, so they are grouped by section instead.

Not included here

24 items from the source could not be safely included:

MIT's page format for this item wasn't recognized clearly enough to place it safely. (24 items)

Materials by section

Grouped by section, as MIT organized them. Not sequenced or ordered.

Lecture Notes

34 files

Assignments

8 problem sets

Other materials from this course

MIT OpenCourseWare, Prof. Alexander Postnikov, 18.212 Algebraic Combinatorics, Spring 2019.

License: CC BY-NC-SA 4.0 · Edition: Spring 2019 · Open the original course on OCW ↗

Organized by RedLectern, independent of MIT and not endorsed by MIT.

Per-resource rights are recorded on each resource; All-Rights-Reserved items are link-only, never mirrored.

Algebraic Combinatorics

Before you start

What's here, and what isn't

Not included here

Materials by section

Lecture Notes

Assignments

Other materials from this course

Lecture 1: Catalan numbers: drunkard’s walk problem, generating function, recurrence relation.

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

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

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

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

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

Lecture 7: q -factorials and q -binomial coefficients.

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

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

Lecture 10: Statistics on permutations (cont.). Equidistributed statistics. Major index. Records. Exceedances. Stirling numbers.

Lecture 11: Stirling numbers (cont.). Set-partitions. Rook placements on triangular boards. Non-crossing and non-nesting set-partitions.

Lecture 12: Eulerian numbers. Increasing binary trees. 3 Pascal-like triangles: Eulerian triangles, Stirling triangles of 1st and 2ⁿd kind.

Lecture 13: Discussion of problem set 1.

Lecture 14: Discussion of problem set 1 (cont.).

Lecture 15: Posets and lattices. Boolean lattice. Partition lattice. Young’s lattice.

Lecture 16: Distributive lattices. Birkhoff’s fundamental theorem for finite distributive lattices.

Lecture 17: Sperner’s property. Symmetric chain decompositions. Sperner’s and Dilworth’s theorems. Greene’s theorem.

Lecture 18: Greene’s theorem vs Schensted correspondence. Up and down operators. Differential posets.

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

Lecture 20: Proof of unimodality of Gaussian coefficients (cont.). Theory of partitions. Euler’s pentagonal number theorem.

Lecture 21: Partition theory (cont.). Franklin’s combinatorial proof of Euler’s pentagonal number theorem. Jacobi’s triple product identity.

Lecture 22: Partition theory (cont.). Combinatorial proof of Jacobi’s triple product identity. Enumeration of trees. Cayley’s formula. Simple inductive proof of Cayley’s formula.

Lecture 23: Two combinatorial proofs of Cayley’s formula.

Lecture 24: Discussion of problem set 2.

Lecture 25: Discussion of problem set 2 (cont.).

Lecture 26: Matrix Tree Theorem. Spanning trees. Laplacian matrix of a graph. Reciprocity formula for spanning trees. Examples: complete graphs, complete bipartite graphs.

Lecture 27: Matrix Tree Theorem (cont.). Products of graphs. Number of spanning trees in the hypercube graph. Oriented incidence matrix.

Lecture 28: Proof of Matrix Tree Theorem using Cauchy-Binnet formula. Weighted and directed version of Matrix Tree Theorem. In-trees and out-trees.

Lecture 29: Proof of Directed Matrix Tree Theorem based on induction.

Lecture 30: Proof of Directed Matrix Tree Theorem via the Involution Principle. Electrical Networks and Kirchhoff’s Laws.

Lecture 31: Electrical networks (cont.). Kirchhoff’s matrix. Relations of electrical networks with Matrix Tree Theorem and spanning trees. Series-parallel connections. Probabilistic interpretation of the electrical potential in terms of random walks on graphs.

Lecture 32: Eulerian cycles in digraphs and B.E.S.T. theorem.

Lecture 33: Parking functions. Tree inversion polynomials.

Lecture 34: Pascal triangle. Bernoulli numbers. Riemann zeta function. Binary trees. Catalan numbers.

Lecture 35: Lindstrom-Gessel-Viennot lemma. Lindstrom Theorem.

Lecture 36: Proof of Lindstrom-Gessel-Viennot lemma. Weighted version of Lindstrom-Gessel-Viennot lemma. Plane partitions.

Lecture 37: MacMahon Proposition. Rhombus tiling. Domino tiling. Kasteleyn Theorem. Temperley Theorem.

Lecture 38: Discussion of problem set 3.

Lecture 39: Plane partitions. Symmetric polynomials. Semi-standard Young tableau. Schur polynomial. Jacobi-Trudi Theorem. Hook-content formula.