Catalan objects
August 28, 2019
As an undergrad I never learned about the Catalan numbers, and while I naturally picked some things up by osmosis as a grad student, I had never quite felt at home with them the way most enumerators seem to. Earlier this summer, in preparation for the comprehensive exam in enumeration, I decided to try and remedy that. This blog post, which was mostly written during that time, is the result.
The Catalan numbers are defined by the recurrence relation \[ c_n = \sum_{k=1}^n c_{k-1}c_{n-k} \] with the initial condition \(c_0 = 1\). The sequence begins 1, 1, 2, 5, 14, 42.
The recurrence translates into the quadratic equation \[ C(x) = 1 + xC(x)^2 \] for the ordinary generating function \(C(x)\). This is one of the simplest functional equations you can write down which has a power series solution that isn’t a rational function. Using the good old quadratic formula (taking the branch with positive coefficients) we get the closed form \[ C(x) = \frac{1 - \sqrt{1 - 4x}}{2x} \] and messing with binomial identities gives the explicit formula \[ c_n = \frac{1}{n+1} \binom{2n}{n} \] for the coefficients. One can also derive this formula by a routine application of the Lagrange implicit function theorem, which is maybe easier if you ignore the difficulty of actually proving LIFT.
The Catalan numbers have dozens of different combinatorial interpretations. They’re especially nice because most of the objects counted by Catalan numbers can be put in straightforward bijections with one another, despite looking superficially different. Given this, one perspective is that these “different” interpretations are really just cryptomorphic descriptions of the same thing: “Catalan objects”. The remainder of this post will go over some of those descriptions.