A binary tree is a tree where each vertex has a left child or a right child
or both or neither. The Catalan number is the number of binary
trees on vertices.

Lemma 8.6.11

Proof.
On removing the root we get a left subtree of size and a right subtree
of size for
. Summing over gives the result.

This looks like a convolution. In fact, it is
where

We observe that therefore
, where the multiplication by shifts the coefficients
up by and then adjusts for . This equation can be solved
for to get

Since we must have the sign. From the binomial theorem

Thus
. Simplifying
this we obtain
and note the corollary
that
.
Other possible definitions for are:

The number of ways of bracketing variables.

The number of sequences of length with each of such
that all partial sums are non-negative.