Next: Bell numbers Up: Special Sequences of Integers Previous: Second Method   Contents

## Catalan numbers

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.

Next: Bell numbers Up: Special Sequences of Integers Previous: Second Method   Contents
root 2002-06-10