Catalan Number

The Catalan number is the number of unlabelled plane rooted binary trees with internal nodes.

Also, counts the number of Dyck Path between and

Also, counts trinagulations of -gon into triangles.

Theorem

with .

Proof

With internal nodes, excluding the roots, there must be internal nodes in the left branch and in the right branch giving possible trees. Now sum over .

Theorem

They have a Generating Function:

Proof 1

Multiply through by to find

Since has constant term , it equals

so

Proof 2

Let be a Structure of building a plane binary tree on internal nodes. Then it satisfies:

which immediately gives

Theorem

Proof

Apply Formal Binomial Theorem to find