---
tag: 0Y97E2DMB7
kind: statement
role: theorem
name: Binary trees are counted by Catalan numbers
msc: [05C05]
uses: [092DRBFKMG, 02A8EMC83C]
sources:
  - url: https://en.wikipedia.org/wiki/Catalan_number
    locator: Applications in combinatorics
---

## Statement

Let $n$ be a natural number.
Then the number of [[binary trees|02A8EMC83C]] with exactly $n$ nodes is the [[Catalan number|092DRBFKMG]] $C_n$.

## Remarks

Here a binary tree is either empty or a root node with an ordered pair of binary trees as its left and right subtrees.
For $n = 3$ there are $C_3 = 5$ binary trees.
Proof idea: a nonempty tree with $n + 1$ nodes has a left subtree with $i$ nodes and a right subtree with $n - i$ nodes. This gives the [[Catalan recurrence|0Y1MG9R5VN]].

## Explanations

### L1 human

Remove the root of a binary tree, and you get a left tree and a right tree.
The sizes of the two trees add up to one less than the size of the original tree, and this gives the Catalan recurrence.