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: