Exercise 1604Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Catalan applications

#Catalan#applications#structures

Statement

Show that the number of full binary trees with $n$ internal nodes is $C_n=\frac{1}{n+1}\binom{2n}{n}$ .

Hint

A full binary tree has $n$ internal nodes, $n+1$ leaves. Traverse left-to-right and encode: $+1$ for internal node, $-1$ for leaf.

Depth-first traversal. Each prefix has $\#$ internal $\ge\#$ leaves, giving Dyck path condition.

Show solutionHide solution

Solution

Bijection. DFS traversal of binary tree with $n$ internal nodes, $n+1$ leaves produces a Dyck path with $n$ up-steps and $n+1$ down-steps; equivalently (shift) a Dyck path of length $2n$ .

Count. $C_n$ .

Conclusion. $C_n$ counts full binary trees with $n$ internal nodes.

Examples. $n=1$ : $1$ ; $n=2$ : $2$ ; $n=3$ : $5$ .

Catalan applications

Statement

Solution

More problems in Counting principles