M Theory Lesson 295

A while back we looked at ways of counting constrained paths that give, say, Motzkin or Schroeder numbers.

The Catalan number $C(n)$ counts the number of vertices on an associahedron polytope in dimension $n-3$, which is labelled by an $n$-gon. The generalised Catalan numbers $C(p,n)$ are given by

$C(p,n) = \frac{1}{n - 1} B(p (n - 2); (n - 2))$

for the binomial coefficient $B(n;k)$. The usual Catalan numbers are recovered when $p=2$. For example, $C(5) = 5$ gives the $5$ vertices of the pentagon in dimension $2$. The case $p=2$ is for binary trees. $C(p,n)$ is related to $p$-ary trees. For example, in lesson 284 we looked at the case $p=3$, which divides polygons into square pieces. The generalised Catalan number $C(p,n)$ is also used to count the number of paths on a lattice (from the origin) lying below the line of slope $p-1$.