Random mappings, forests, and subsets associated with Abel-Cayley-Hurwitz multinomial expansions

June, 2001
Report Number: 
593
Authors: 
Jim Pitman
Citation: 
S{\'e}minaire Lotharingien de Combinatoire, Issue 46, (45 pp.) 2001
Abstract: 

Various random combinatorial objects, such as mappings, trees, forests, and subsets of a finite set, are constructed with probability distributions related to the binomial and multinomial expansions due to Abel, Cayley and Hurwitz. Relations between these combinatorial objects, such as Joyal's bijection between mappings and marked rooted trees, have interesting probabilistic interpretations, and applications to the asymptotic structure of large random trees and mappings. An extension of Hurwitz's binomial formula is associated with the probability distribution of the random set of vertices of a fringe subtree in a random forest whose distribution is defined by terms of a multinomial expansion over rooted labeled forests.

PDF File: 
Postscript File: