The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses
Preprint
Abstract
We present a very simple bijective proof of Cayley's formula due to Foata and Fuchs (1970). This bijection turns out to be very useful when seen through a probabilistic lens; we explain some of the ways in which it can be used to derive probabilistic identities, bounds, and growth procedures for random trees with given degrees, including random d-ary 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.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Growing Random Uniform d-ary TreesAnnals of Combinatorics, 2022
- Most trees are short and fatProbability Theory and Related Fields, 2018
- Random graphs from a block-stable classEuropean Journal of Combinatorics, 2016
- A generalized enumeration of labeled trees and reverse Prüfer algorithmJournal of Combinatorial Theory, Series A, 2007
- Building uniformly random subtreesRandom Structures & Algorithms, 2004
- The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin’s local time identityProbability Theory and Related Fields, 2004
- Coalescent Random ForestsJournal of Combinatorial Theory, Series A, 1999
- Two counting problems solved via string encodings1985
- Une théorie combinatoire des séries formellesAdvances in Mathematics, 1981
- Réarrangements de fonctions et dénombrementJournal of Combinatorial Theory, 1970