Generating function of binary trees by leaves

Builds on Generating function Catalan numbers

Statement

Let $c_n$ be the number of rooted, unlabeled, ordered binary trees with $n$ leaves, for $n \ge 1$ . Here each node that is not a leaf has exactly two children, in a fixed left to right order.

Then the generating function $C(x) = \sum_{n \ge 1} c_n x^n$ is $C(x) = \frac{1 - \sqrt{1 - 4x}}{2} = \sum_{n=1}^{\infty} \frac{1}{n} \binom{2n-2}{n-1} x^n.$

Remarks

So $c_n = \frac{1}{n}\binom{2n-2}{n-1}$ , which is the Catalan number $C_{n-1}$ . Example: $c_1 = 1$ , $c_2 = 1$ , $c_3 = 2$ , $c_4 = 5$ . Splitting a tree at the root gives $C(x) = x + C(x)^2$ , and the square root form is the root of this quadratic that vanishes at $x = 0$ .

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Catalan numbers definition
Generating function concept
Generating function of binary trees by leaves statement

Tag	`G4GSKC69JM`
URI	`m2://G4GSKC69JM`
Kind	statement, theorem
Writing	W0 stub
MSC	05A15, 05C05
Status	This copy of the site has no build data. Run `m2 status G4GSKC69JM`.
Uses	Generating function, Catalan numbers
Changed	4 November 2026

Generating function of binary trees by leaves

Statement

Remarks

Reading path

Further reading

What this page needs for W1

What links here