Séminaire Lotharingien de Combinatoire, B46h (2001), 45 pp.
Jim Pitman
Random Mappings, Forests, and Subsets Associated with Abel-Cayley-Hurwitz
Multinomial Expansions
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.
Received: March 24, 2001; Revised: June 12; Accepted: Sept. 21, 2001.
The following versions are available: