**Theorem [Cayley, 1889]** The number of trees on labeled vertices is .

**Theorem [Cayley, 1889]** The number of rooted forests on labeled vertices with trees is .

**Borchardt (1860), Sylvester (1857)** .

The number of rooted forests on labeled vertices with trees using only the first labels as roots is and .

- http://en.wikipedia.org/wiki/Cayley%27s_formula
- http://www.math.ucla.edu/~pak/lectures/bij-trees-talk1.pdf
- http://en.wikipedia.org/wiki/Double_counting_(proof_technique)#Counting_trees [proof of Cayley’s formula by double counting]

Problem list:

Advertisements