An Elementary Proof of the Cayley Formula Using Random Maps

2014/09/04 by Hao, Steven, He, Andrew, Li, Ray +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1409.1614

Abstract

Cayley's formula states that the number of labelled trees on n vertices is n^n-2, and many of the current proofs involve complex structures or rigorous computation. We present a bijective proof of the formula by providing an elementary calculation of the probability that a cycle occurs in a random map from an n-element set to an n+1-element set.

Related

• A Simple Proof of the Cayley Formula using Random Graphs
• A telescopic proof of Cayley's formula
• The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses
• A note on counting labeled and unlabeled trees
• Cayley's formula from middle school math