We present a very simple new bijective proof of Cayleys formula. The bijection is useful for the analysis of random trees, and we explain some of the ways in which it can be used to derive probabilistic identities, bounds, and growth procedures for such trees. We also introduce a partial order on the degree sequences of rooted trees, and conjecture that it induces a stochastic partial order on heights of random rooted trees with given degrees.
Download