Combinatorics

Week 9 | Week 10 | Week 11

Tuesday, March 28

Blackboards

• Coloring the faces of a tetrahedron
• Coloring the faces of a cube

Here is a pattern to print twice on cardboard, for building the model tetrahedron that I used in class:

Tetrahedron

Thursday, March 23

Blackboards

• The associahedron and permutahedron
• Cayley’s formula for dissections of an n-gon
• The hook length formula for Young Tableaux

Here is a more detailed PDF drawing of the associahedron:

Associahedron

Here are four papers related to what we’re studying. I’m also making these available on Courseworks.

• 1890 Cayley - On the Partitions of a Polygon
• 2000 Przytycki, Sikora - Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers
• 1979 Greene, Nijenhuis, Wilf - A probabilistic proof of a formula for the number of Young tableaux of a given shape
• 1996 Stanley - Polygon dissections and standard Young tableaux

As a student I became interested in the problem of finding an algorithm to produce Young tableaux uniformly at random. I showed Herb Wilf a construction that lead to the construction in their paper. I had bungled how to use hook lengths. This taught me to always push harder.

As a reminder, I have posted links on our main page to all class notes and exam solutions from Spring 2021 and Spring 2022, combined into single files:

• S21 Notes
• S21 Exams
• S22 Notes
• S22 Exams