M Theory Lesson 137

We have seen how the Catalan numbers come up in many places. For example, they count the number of vertices of the $n$th associahedron, which is fully labelled by chorded $n+3$-gons. The full list of the number of codimension $k$ elements of the $n$th associahedron is given by sequence A033282 at the integer database. For instance, the left diagonal row

$2, 5, 9, 14, 20, 27, \cdots$

counts two ends to an interval, five edges on a pentagon, nine faces of the 3d Stasheff polytope, and so on. These codimension 1 faces are labelled by an $n$-gon with a single diagonal, splitting the $n$-gon into two parts.

Another way of viewing the particular row above is in terms of Young diagrams with only two rows. For example, the 3d and 4d polytopes have faces labelled by the following Young diagrams. Observe how the recursion is visible in the complements of the white tiles. For $n = 3$, by omitting both the full white diagram and the yellow diagrams one obtains five remaining purple diagrams corresponding to the Young pictures for the $n = 2$ pentagon edges. The recursion relation for codimension 1 faces must therefore be

$F_{n} = F_{n - 1} + n + 1 = \frac{n(n+3)}{2}$

Recall that codimension 1 elements are also labelled by trees with two internal vertices. For example, the whole pentagon is labelled by a single vertex tree with four leaves, but the pentagon edges are labelled by four leaved trees with two internal vertices. The homework problem is to figure out how these trees correspond to the Young diagrams.

The full list of left diagonals for A033282, with the above row as the $k = 1$ entry, gives the number of codimension $k$ faces. The general formula for these numbers takes the form

$F_{n} (k) = \frac{1}{k + 1} B(n + k + 2,k) B(n,k)$

for binomial coefficients $B(n,m)$. The sequence A126216 is a mirror image of A033282, which counts the number of Schroeder paths. These arose in the construction of Abel sums and interesting maps between sets of trees.

Update: It turns out that R. P. Stanley worked out a relation between trees and Young tableaux (numbered Young diagrams) in the short 1996 paper Polygon dissections and standard Young tableaux in J. Comb. Theory A76, pages 175-177.