Tags: #theorem

Statement

The number of plane binary trees with $n$ vertices is equal to the Catalan numbers $C_n$.

Proof

We shall build a bijection between plane binary trees with $n$ vertices and complete binary trees with $n+1$ leaves and use this to conclude.

Given a plane binary tree, we may add all the leaves required to make it a complete binary tree. Note that it would then have $n+1$ leaves.

Given a complete binary tree, we may remove all the leaves to create a plane binary tree with $n$ vertices.