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\left(n\right)$ 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\left(p\right(n-2);(n-2\left)\right)$

for the binomial coefficient $B(n;k)$. The usual Catalan numbers are recovered when $p=2$. For example, $C\left(5\right)=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$.