# Counting trees

Theorem [Cayley, 1889] The number of trees on $n$ labeled vertices is $n^{n-2}$.

Theorem [Cayley, 1889] The number $T_{n,k}$ of rooted forests on $n$ labeled vertices with $k$ trees is $\binom{n-1}{k-1} n^{n-k}$.

Borchardt (1860), Sylvester (1857) $\sum_{k=1}^n T_{n,k} = (n + 1)^{n-1}$.

The number of rooted forests on $n$ labeled vertices with $k$ trees using only the first $k$ labels as roots is $\frac{\binom{n-1}{k-1} n^{n-k}}{\binom{n}{k}}$ and $\sum_{k=1}^n \frac{\binom{n-1}{k-1} n^{n-k}}{\binom{n}{k}} = \frac{n^n-n}{(n-1)^2}$.

Problem list:

Advertisements