A short proof of Cayley's tree formula

Abstract

We give a short proof of Cayley's tree formula for counting the number of different labeled trees on $n$ vertices. The following nonlinear recursive relation for the number of labeled trees on $n$ vertices is deduced from a combinatorial argument, $$T_n=\frac{n}{2}\sum _{k=0}^{n-2}\left(\begin{array}{c}n-2\\ k\end{array}\right)T_{k+1}{T}_{n-k-1};forn>1and{T}_1=1,$$ and then it is proved that $T_n=n^{n-2}$, which gives yet another proof of the celebrated Cayley's tree formula.

arXiv comment4 pages, 2 figures

Cited by in corpus (2)

• Polynomial properties of Jack connection coefficients and generalization of a result by Dénes
• Enumerating labeled graphs with a k-cycle