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