Learn / Library / Combinatorics

Labeled trees count

CombinatoricsMedium

How many different trees can be drawn on the labeled vertices $1$ to $7$ ? Trees are different if their sets of edges differ.

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

A tree on labeled vertices matches a code obtained by repeatedly removing the smallest leaf.

Solution

A tree on $n$ labeled vertices corresponds one-to-one to a sequence of length $n - 2$ with entries from $1, \dots, n$ , namely the labels of the neighbours of the removed smallest leaves.
Here $n = 7$ , so the sequences have length $5$ and each entry has $7$ choices.
The number of trees is $7^{5} = 16807$ .

Answer: $16807$