Catalan Numbers

Now what exactly are these numbers? Here are the first few:

N	Nth Catalan Number
1	1
2	2
3	5
4	14
5	42
6	132
7	429
8	1430
9	4862
10	16796

For the general case, I could for example give you one of these definitions (where C(N) denotes the N-th Catalan number):

1. C(N) := choose(2N,N) / (n+1)
2. C(0) := 1, and C(N+1) := Sum(i=0 to n) C(i)*C(n-i)
3. C(N) := The number of binary trees that can be built with N nodes.
4. C(N) := The number of possible triangulations (with N triangles) of a convex polygon with N+2 sides.

It turns out that all these definitions are equivalent. But there are big differences in quality:

• 1. and 2. give a definition without any meaning. Without meaning, they're senseless. These might be helpful when we need to calculate the values, but they're bad definitions in a deeper sense.
• 3. and 4. are great, and the binary tree problem is probably the problem where most of us first saw the Catalan Numbers. Unfortunately, these don't come with mathematical formulas to calculate the values. But it's fairly easy to prove that the number of binary trees is equivalent to the recursive 2. definition.

On this page, I will therefore use the 3. definition (the one with binary trees).