Séminaire Lotharingien de Combinatoire 46 (2001), Article B46h

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

multinomial expansions ^{∗}

Jim Pitman

Department of Statistics University of California 367 Evans Hall # 3860 Berkeley, CA 94720-3860

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.

Contents

1 Introduction 2 1.1 Correspondence with results of [72] . . . . . . . . . . . . . . . 4 2 Random mappings and the forest volume formula 4

∗Research supported in part by N.S.F. Grants DMS 97-03961 and DMS-0071448

3 Random Forests 8 3.1 Distribution of the roots of a p-forest . . . . . . . . . . . . . . 10 3.2 Conditioning on the set of roots. . . . . . . . . . . . . . . . . . 11

4 Spanning Subtrees 15 4.1 Joyal’s bijection between marked rooted trees and mappings . 20

5 Hurwitz distributions 21 5.1 Constructions from p-mappings . . . . . . . . . . . . . . . . . 22 5.2 Constructions from p-trees . . . . . . . . . . . . . . . . . . . . 24 5.3 Distribution of tree components . . . . . . . . . . . . . . . . . 25 5.4 A Hurwitz multinomial distribution . . . . . . . . . . . . . . . 27 5.5 Percolation probabilities . . . . . . . . . . . . . . . . . . . . . 28

6 Restrictions of p-forests 30 6.1 Proof of the restriction theorem . . . . . . . . . . . . . . . . . 32 6.2 Variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6.3 Thinning of p-forests . . . . . . . . . . . . . . . . . . . . . . . 37

1 Introduction

Recent research at the interface of probability and combinatorics [70, 24, 6, 5, 7, 3] has exposed a rich probabilistic structure associated with the binomial and multinomial expansions due to Abel [1], Cayley [25] and Hurwitz [43]. The probabilistic meaning of these expansions is brought out by consideration of suitably constructed random subsets, trees, forests, and mappings, and by study of the relations between these various random combinatorial objects. The purpose of this paper is to introduce this subject to combinatorialists with some interest in probability theory, and to probabilists with some interest in combinatorics. Combinatorialists may prefer to look first at the condensed version [72] of this paper, written in more combinatorial language. Section 1.1 of this paper provides a correspondence between polynomial identities of Hurwitz type presented in [72] and their probabilistic expressions in this paper. These Hurwitz identities were all first discovered as byproducts of the solution of natural probabilistic problems discussed here. Probabilists may find motivation in the application of some of the results of this paper to the theory of measure-valued and partition-valued coalescent processes and the asymptotic structure of large random trees and random mappings, as considered in [4, 5, 6, 24, 33, 70, 68, 14, 65, 7, 3].

This paper is organized as follows. Section 2 explains how a simple formula of Burtin [23] for random mappings is equivalent to a very useful form of Cayley’s multinomial expansion over trees, called here the forest volume formula. This formula yields some enumerations of rooted labeled forests which are the basis of everything that follows. Section 3 presents some constructions and properties of a p-forest of k trees, that is a random forest of k rooted trees labeled by some finite set S, whose distribution is proportional to terms in the Cayley expansion of (∑_{s∈S} p_{s})^{n−k} over such forests, where p is some arbitrary probability distribution on S. Properties of such a p-forest, first considered in [70] in connection with the construction of a coalescent process, are closely related to properties of a random p-mapping defined by assigning each point s of S an image in S with distribution p, independently as s varies, as studied in [23, 78, 48, 65, 7]. Section 4 describes the distribution of the subtree spanning a finite number of vertices of a p-tree, that is a p-forest with a single tree component. The result of this section was applied in [5] to describe features of the asymptotic structure of p-trees with a large number of vertices. Section 4.1 shows how results for p-trees can be transferred to p-mappings via Joyal’s bijection [49, p. 16] whereby a p-tree with an independent mark with distribution p corresponds to a p-mapping. As shown in [7], this allows a large number of asymptotic results for p-mappings to be deduced from corresponding results for p-trees obtained in [24]. Section 5 shows how the distributions of various random subsets derived from p-trees and p-forests are related to Hurwitz’s multinomial expansions [43]. This leads in Section 5.5 to consideration of percolation probabilities defined by p-trees and p-forests. These probabilities are related to extensions and variations of Hurwitz’s expansions described in [72]. Section 6 shows that for any subset B of S, the restriction to B of a p-forest is a p(·|B)-forest, where p(·|B) is the probability distribution p conditioned on B. Finally, Section 6.3 shows how the structure of p-forests is preserved under an operation of independent deletion of edges, which generalizes that considered in [70].

1.1 Correspondence with results of [72]

Polynomial identity in [72]

Probabilistic expression in this paper

(2)  Theorem 11 (i)-(iii) and Theorem 12
(3)  Theorem 11 (iv) and Proposition 15 (ii)
(4)  Proposition 18 for k = 1.
(9)  Lemma 3 (i)
(11)  Proposition 15 (i)
(18)  Theorem 4
(19) and (20)  (16)
(24)  Lemma 23
(26)  Proposition 18
(27)  Theorem 7
(28)  Proposition 14
(29)  (33)

2 Random mappings and the forest volume formula

First, a brief review of probabilistic terms used in this paper. A probability distribution on a finite set S is a non-negative real-valued function p := (p_{s}, s ∈ S) with ∑_{s∈S} p_{s} = 1. The definition of p is extended to subsets A of S by p(A) := p_{A} := ∑_{s∈A} p_{s}. Throughout the paper, P denotes a probability distribution on a suitable finite set Ω. A function X : Ω → S is called a random element of S. The distribution of X is the probability distribution p on S defined by

p_{s} := P (X = s) := P ({ω ∈ Ω : X(ω) = s}) (s ∈ S).

If elements of S are for instance subsets of another set, or trees, or mappings, a random element X of S may called a random set, a random tree, or a random mapping, as the case may be, whether or not the distribution of X is uniform, meaning P (X = s) = 1/|S| for all s ∈ S, where |S| is the number of elements of S. Subsets of Ω are called events. For an event B ⊆ Ω with P (B) > 0 and a random element X of S, the conditional distribution of X given B is the probability distribution on S defined by

P (X = s | B) := P ({ω ∈ B : X(ω) = s})/P (B) (s ∈ S).

For X with distribution p, and A ⊆ S with p_{A} > 0, the distribution of X given X ∈ A may be denoted p(·|A). So p(s|A) = p_{s}χ(s ∈ A)/p_{A}, where χ(⋯) is the indicator function which has value 1 if ⋯ and 0 else. For further background, and definitions of other probabilistic terms such as independence and expectation, see [34] or [67].

Random Mappings. Given some probability distribution p on a finite set S, let M := (M_{s}, s ∈ S) be a p-mapping of S. That is to say, the M_{s}, s ∈ S are independent random variables with common probability distribution p, defined on some probability space (Ω, P). See [27, 79, 35, 36] for combinatorial background. There is a large probabilistic literature on the stucture of random mappings for uniform p. See e.g. [56, 4, 41, 64, 3] and papers cited there. The case when all of the p_{s} but one are equal is studied in [83, 63, 18]. Random p-mappings for general p are studied in [23, 78, 48, 65, 7]. See also [23, 31, 44, 45, 16, 17, 19, 50, 13, 74, 40] regarding various other models for random mappings.

For each subset B of S^{S}, the probability

P (M ∈ B) = ∑_{m∈B} ∏_{s∈S} p_{m_{s}}  (1)

is the usual enumerator polynomial of B in variables p_{s}, s ∈ S, as discussed in [27, p. 72], but with the constraints p_{s} ≥ 0 and ∑_{s} p_{s} = 1. A formula for P (M ∈ B) as a function of p = (p_{s}, s ∈ S) therefore amounts to evaluation of an enumerator polynomial. Such probabilistic evaluations are typically simpler than a general expression for the enumerator polynomial of B, because the use of p_{s} subject to ∑_{s∈S} p_{s} = 1 instead of general variables x_{s} typically eliminates some factors of x_{S} := ∑_{s∈S} x_{s}. But such factors can always be recovered by scaling: take p_{s} = x_{s}/x_{S} in the probabilistic identity, and multiply both sides by x_{S}^{|S|} where |S| is the number of elements of S.

To give an example of this translation between probabilistic and combinatorial language, let D(M) ⊆ S ×S be the usual functional digraph associated with a mapping M of S. So D(M) := {(s, M_{s}), s ∈ S} has a directed edge s → M_{s} for each s ∈ S. According to a result of Burtin [23], if M is a p-mapping then

P [no cycle of D(M) is contained in S − R ] = p_{R} (R ⊆ S). (2)

In combinatorial language: the enumerator of the set

{M ∈ S^{S} : no cycle of D(M) is contained in S − R}

is the polynomial x_{R}x_{S}^{|S|−1} in variables x_{s}, s ∈ S. See [12] for six different proofs of (2) with |R| = 1. The result for general R follows from this special case by replacing M by ϕ ∘ M where ϕ : S → (S − R) ∪ {r} collapses R onto some r ∈ R, and leaves S − R fixed.

Rooted forests. Let D̂_{R}(M) denote the digraph with vertex set S derived from D(M) by first deleting the edges r → M_{r} for all r ∈ R, then replacing each of the remaining edges s → M_{s} for s ∈ S − R by its reversal M_{s} → s. Obviously

[no cycle of D(M) is contained in S − R] ⇔ [D̂_{R}(M) ∈ F_{S,R}] (3)

where F_{S,R} is the set of all forests F of rooted trees labeled by S, whose set of root vertices is R, with edges of F directed away from the roots. Call the set

F_{s} := {x : s → x is an edge of F }

the set of children of s in the forest F. For each F ∈ F_{S,R} the F_{s}, s ∈ S form a collection of disjoint, possibly empty sets with union S − R, and s ∉ F_{s} for all s. Note that |F_{s}| is the out-degree of vertex s in the forest F, that each F ∈ F_{S,R} has |R| tree components, some of which may be trivial (i.e. a root vertex with no edges), and that the total number of edges of F is ∑_{s} |F_{s}| = |S| − |R|. For each subset B of the set

F_{S} := ∪_{R⊆S}F_{S,R}

of all rooted forests labeled by S, the enumerator polynomial in variables x_{s}, s ∈ S

V_{S}[F ∈ B] := V_{S}[F ∈ B](x_{s}, s ∈ S) := ∑_{F ∈B} ∏_{s∈S} x_{s}^{|F_{s}|}  (4)

is called here the volume of B, to emphasise that B ↦ V_{S}[F ∈ B] is a measure on subsets B of F_{S}, for each fixed choice of (x_{s}, s ∈ S) with x_{s} ≥ 0. This notion of forest volumes includes both the probabilistic interpretations developed in [70, 68, 69] and in this paper, and Kelmans’ notion of the forest volume of a graph [54, 52, 53]. The previous formula x_{R}x_{S}^{|S|−1} for the mapping enumerator corresponding to (2) amounts, by cancellation of a common factor of x_{S}^{|R|}, to the following generalization of Cayley’s [25] multinomial expansion over trees, which is used repeatedly throughout this paper:

The forest volume formula.

V_{S}[roots(F) = R] = x_{R} x_{S}^{|S|−|R|−1}  where x_{B} := ∑_{s∈B} x_{s}  (5)

and roots(F) denotes the set of root vertices of a forest F ∈ F_{S}.

Cayley [25] gave the special case of (5) for |R| = 1, call it the tree volume formula, as well as the special case x_{s} ≡ 1 of the forest volume formula, that is

|F_{S,R}| = |R| |S|^{|S|−|R|−1}.

See [72] for some alternate derivations and history of the forest volume formula and its consequences. For each subset R of S with |R| = k ≤ n = |S| and each vector c := (c_{s}, s ∈ S) of non-negative integers with ∑_{s} c_{s} = n − k, the identity of coefficients of Π_{s}x_{s}^{c_{s}} in (5) reads

|\{F ∈ F_{S,R} : |F_{s}| = c_{s} for all s ∈ S\}| = \frac{c_{R} (n − k − 1)!}{∏_{s∈S} c_{s}!}  (6)

which summed over R with |R| = k gives the number of forests with outdegree vector c:

|\{F ∈ F_{S} : |F_{s}| = c_{s} for all s ∈ S\}| = \frac{(n − 1)_{n−k}}{∏_{s∈S} c_{s}!}  (7)

with the notation for falling factorials (x)_{m} := ∏_{i=0}^{m−1}(x − i). Formula (7) is the identity of coefficients of Π_{s}x_{s}^{c_{s}} in the result of summing the forest volume formula (5) over all subsets R of S of size k, which gives the volume of all forests of k trees labeled by S with |S| = n, as found in [70, (39)], [69, Theorem 1.6], [82, Theorem 5.3.4]:

V_{S}[F with k tree components] = \binom{n − 1}{k − 1}x_{S}^{n−k}.  (8)

There is also the following generalization of (8), obtained in [68, Lemma 13] and [72, Theorem 3], which reduces to (8) when G is the trivial forest with n singleton components and no edges: for each G ∈ F_{S} with g tree components

V_{S}[F with k trees and F ⊇ G] = \binom{g − 1}{k − 1}x_{S}^{g−k} ∏_{s∈S} x_{s}^{|G_{s}|}.  (9)

Yet another extension of the forest volume formula can be made as follows. Write r ⇝^{F} s if there is a directed path from r to s in F, that is a sequence of one or more edges r →^{F} ⋯ →^{F} s, where s_{1} →^{F} s_{2} means (s_{1}, s_{2}) ∈ F. Then for all R ⊂ S, and each fixed choice of an r ∈ R and an s ∈ S − R,

V_{S}[roots(F) = R and r ⇝^{F} s] = x_{r} x_{S}^{|S|−|R|−1}.  (10)

Since for each fixed s ∈ S − R and each F ∈ F_{S,R} there is is a unique r ∈ R with r ⇝^{F} s, the forest volume formula (5) is recovered from (10) by summation over r ∈ R. A probabilistic formulation and proof of (10) are given later around (32). See also [72, Theorem 2] for a combinatorial proof of (10).

3 Random Forests

Let F_{k} denote a random forest of k trees labeled by S with |S| = n, say F_{k} = (F_{k,s}, s ∈ S) where F_{k,s} is the random set of children of s in the forest F_{k}. Since the random vector of out-degree counts

counts(F_{k}) := (|F_{k,s}|, s ∈ S)

is subject to the constraint ∑_{s} |F_{k,s}| = n − k, the expectation of |F_{k,s}| must equal (n−k)p_{s} for some probability distribution p on S. For given (p_{s}, s ∈ S), the simplest way to construct such a random forest F_{k} is to suppose that F_{k} satisfies conditions (i) and (ii) of the following proposition, which extends [70, (36) and (38)]:

Proposition 1 For each probability distribution p on S with |S| = n, the probability distribution of a random forest F_{k} with k trees, call it a p-forest of k trees, is defined by the formula

P (F_{k} = F) = \binom{n − 1}{k − 1}^{−1} ∏_{s∈S} p_{s}^{|F_{s}|}  (11)

for every forest F of k trees labeled by S. A random forest F_{k} has this distribution if and only if both (i) the distribution of the out-degree count vector is multinomial with parameters n − k and (p_{s}, s ∈ S), meaning that for each vector of counts c = (c_{s}, s ∈ S) with ∑_{s} c_{s} = n − k,

P (counts(F_{k}) = c) = \frac{(n − k)!}{∏_{s∈S} c_{s}!} ∏_{s∈S} p_{s}^{c_{s}}  (12)

and (ii) for each such vector of counts c the conditional distribution of F_{k} given counts(F_{k}) = c is uniform on the set of all forests with the given out-degrees, as enumerated in (7).

Proof. The fact that the probabilities (11) sum to 1, over all F with k tree components, is a probabilistic expression of (8) which was noted in [70, Theorem 11]. The equivalence of (i) and (ii) with (11) follows easily from the enumeration (7). □

If p is uniform on S, a p-forest of k trees has uniform distribution on the set of all rooted forests of k trees labeled by S. See [70, §4] for a review of exact combinatorial results and asymptotic distributions known in this case, and their applications to random graphs. See also [10, 57, 66, 59] concerning other models of random trees and forests and their applications.

Constructions of p-trees. Call a p-forest of one tree a p-tree. So a p-tree is a random element of the set T_{S} of all rooted trees labeled by S. The following two constructions of p-trees are based on a sequence of independent random variables X_{0}, X_{1}, X_{2}, … with common distribution p on S with |S| = n.

(i) Let T : S^{n−1} → T_{S} be the bijection defined by a Prüfer code [75, 27, 62] such that T (s_{1}, …, s_{n−1}) is a tree in which the number of children of s equals the number of j such that s_{j} = s, for every s ∈ S. Then T (X_{1}, …, X_{n−1}) is evidently a p-tree. (ii) [21, Theorem 1],[58, §6.1] Assuming p_{s} > 0 for every s ∈ S, the random set

{(X_{j−1}, X_{j}) : j ≥ 1, X_{j} ∉ {X_{0}, …, X_{j−1}}} ⊆ S × S

defines a p-tree. See [24] for applications of this construction, which is related to the classical birthday problem.

See also (19) and (23) in Section 3.2, which for R = {r} show how to construct a p-tree conditioned to have root r by appropriate conditioning of a p-mapping. The effect of conditioning a p-tree on its root is discussed further in Lemma 5.

Coalescent construction of p-forests. To review a construction from [70], define a coalescing sequence of forests F(0), F(1), …, F(n − 1) as follows, by adding edges one by one in such a way that F(j) has j edges (and hence n − j tree components) for each 1 ≤ j ≤ n − 1. Let F(0) be the trivial forest labeled by S with no edges. Given that F(0), …, F(j − 1) have been defined for some 1 ≤ j ≤ n − 1, define F(j) by adding the edge (X_{j}, Y_{j}) to F(j − 1), where the X_{j} are independent with distribution p on S, and given X_{j} and the (X_{i}, Y_{i}) for 1 ≤ i < j, the random variable Y_{j} has uniform distribution on the set of n − j roots of tree components of F(j − 1) other than the component containing X_{j}. Then F(j) is a p-forest of n − j trees for every 0 ≤ j ≤ n − 1. In particular, F(n − 1) is a p-tree.

As remarked in [70], this coalescent construction can be reversed to recover a p-forest of k trees by deleting k −1 edges picked uniformly at random from the |S| − 1 edges of a p-tree. See Section 6.3 for a generalization.

3.1 Distribution of the roots of a p-forest

For 1 ≤ k < n := |S| let S_{k} be the set of all subsets R of S with |R| = k. It is easily seen that for each a non-negative function w = (w_{s}, s ∈ S) with w_{S} > 0, the formula

P (R_{k} = R) = \binom{n − 1}{k − 1}^{−1} \frac{w_{R}}{w_{S}}  (R ∈ S_{k})  (13)

defines the probability distribution of a random element R_{k} of S_{k}, call it the w-distribution on S_{k}. For each fixed subset A of S with |A| = a, formula (13) implies

P (R_{k} ⊇ A) = \frac{\binom{n−a}{k−a} w_{A} + \binom{n−a−1}{k−a−1} (w_{S} − w_{A})}{\binom{n−1}{k−1} w_{S}}.  (14)

Proposition 2 Let roots(F_{k}) be the random set of k root vertices of a pforest of k trees labeled by S with |S| = n. Then

(i) the distribution of roots(F_{k}) is the p-distribution on S_{k}; in particular, the root of a p-tree has distribution p on S; (ii) the conditional distribution of roots(F_{k}) given counts(F_{k}) = c is the cdistribution on S_{k}, for each count vector c with c_{S} = n − k.

Proof. This is just a probabilistic translation of the forest volume formulae (5), (6) and (7), obtained by using the definition (11) of the distribution of F_{k} and canceling some factorials. □

In particular, according to part (i) of the proposition and (14) for A = {r}, for each r ∈ S

P [r ∈ roots(F_{k})] = \frac{(n − k)p_{r}}{n − 1} + \frac{k − 1}{n − 1}.  (15)

Formula (10), derived later in Theorem 4, allows the two terms on the right side of (15) to be interpreted as follows: for each fixed s ∈ S with s ≠ r, these terms are

P [r ⇝^{F_{k}} s and r ∈ roots(F_{k})] and P [r ⇝̸^{F_{k}} s and r ∈ roots(F_{k})]  (16)

respectively. See [72, §3] for an alternative proof and further discussion. Similarly, part (ii) of the proposition and (14) yield

P [r ∈ roots(F_{k}) | counts(F_{k}) = c] = \frac{c_{r}}{n − 1} + \frac{k − 1}{n − 1}  (17)

where the two terms can again be interpreted like (16). According to part (ii) of Proposition 1, the conditional probability displayed in (17) is just the fraction of forests F of k trees labeled by S with the given out-degrees (c_{s}, s ∈ S) such that r is the root of some tree component of F. As a check, (15) can be recovered from (17) and the multinomial distribution of counts(F_{k}) described in Proposition 1, because c_{r} in (17) is the given value of the binomial(n − k, p_{r}) variable |F_{k,r}| whose expectation is (n − k)p_{r}.

3.2 Conditioning on the set of roots.

For a subset R of S with p_{R} > 0, call a random forest F_{R} a p-forest with roots R if F_{R} is distributed like a p-forest of |R| trees conditioned to have root set R. That is, according to the forest volume formula (5) and (11)

P (F_{R} = F) = p_{R}^{−1} ∏_{s∈S} p_{s}^{|F_{s}|}  (F ∈ F_{S,R}).  (18)

Two alternative constructions from p-mappings can be given as follows.

Conditioning a p-mapping to have no cycles within a given set Recall from around (3) that D(M) is the usual functional digraph with vertex set S associated with a mapping M of S, and that D̂_{R}(M) for R ⊆ S is obtained from D(M) by first deleting all edges leading out of R, then reversing all remaining edges. As a consequence of (3), for R ⊆ S with p_{R} > 0, if M is a p-mapping then

D̂_{R}(M) is a p-forest with roots R, given D̂_{R}(M) ∈ F_{S,R}.  (19)

Conditioning a p-mapping on its set of cyclic points For a mapping M of S and v ∈ S define the set of predecessors of v induced by M by

pred(v, M) := {s ∈ S : M_{s}^{i} = v for some i ≥ 1}  (20)

where s ↦ M_{s}^{i} is the ith iterate of M. The set of all cyclic points of M is

cyclic(M) := {s ∈ S : s ∈ pred(s, M)}.

The usual forest derived from M is F(M) := D̂_{cyclic(M)}(M). So F(M) is a forest of rooted trees labeled by S, with edges directed away from

roots(F(M)) := cyclic(M).  (21)

If cyclic(M) = R, then M is determined by its restriction M^{R} to R, which is a permutation of R, and its forest F(M) with roots(F(M)) = R. So for each forest F ∈ F_{S,R} and each permutation π of R,

P (F(M) = F, M^{R} = π) = (∏_{s∈S} p_{s}^{|F_{s}|}) ∏_{r∈R} p_{r}.  (22)

Hence for each non-empty subset R of S,

F(M) is a p-forest with roots R, given cyclic(M) = R;  (23)
M^{R} is a uniform random permutation of R, given cyclic(M) = R; (24)
F(M) and M^{R} are conditionally independent, given cyclic(M) = R. (25)

Note that the two constructions (19) and (23) of a p-forest with roots R are quite different. In (19) the digraph D̂_{R}(M) may contain some edges from cycles of D(M), which cannot appear in F(M).

By summing (22) over all possible π, the distribution of F(M) for a p-mapping M is given by

P [F(M) = F] = |roots(F)|! ( ∏_{r∈roots(F)} p_{r}) (∏_{s∈S} p_{s}^{|F_{s}|})  (26)

where F ranges over the set F_{S} of all (|S| + 1)^{|S|−1} rooted forests labeled by S. By application of (21), (26) and the forest volume formula (5), the distribution of the random subset cyclic(M) derived from a p-mapping of S is determined by the formula

P (cyclic(M) = R) = |R|! p_{R} ∏_{r∈R} p_{r}  (R ⊆ S).  (27)

Hence for 1 ≤ k ≤ |S| the probability that a p-mapping M of S has exactly k cyclic points is

P (|cyclic(M)| = k) = k! ∑_{|R|=k} p_{R} ∏_{r∈R} p_{r}  (28)

where the sum is over all subsets R of S with |R| = k. Jaworski [48, Theorem 2] found an alternative expression for the same probability which can be recast as

P (|cyclic(M)| ≥ k) = k! ∑_{|R|=k} ∏_{r∈R} p_{r}.  (29)

As a check, either of these formulae (28) and (29) can be deduced from the other. See [24] regarding the asymptotic behaviour of this distribution for large |S|, and [65, 7] for related asymptotic results about p-mappings.

Descriptions of a p-forest with roots R. For a forest F labeled by S with roots(F) = R, and v ∈ S − R let M_{v}(F) ∈ S be the mother of v in F, that is the unique s ∈ S such that s →^{F} v. For A ⊆ S the restriction of F to A is the forest F^{A} labeled by A whose set of edges is the intersection with A × A of the set of edges of F. The following lemma summarizes some basic distributional properties of a p-forest with root set R, which follow easily from these definitions, (11) and (18):

Lemma 3 Let H_{1} := ∪_{r∈R}F_{R,r}, that is the random set of all vertices of height 1 (children of the roots) in a p-forest F_{R} with roots R. Then

(i) the distribution of H_{1} is given by the formula

P (H_{1} = B) = p_{B} p_{S−R}^{|S−R−B|−1}p_{R}^{|B|−1} (B ⊆ S − R)  (30)

(ii) for each non-empty B ⊆ S − R, the restricted forest F_{R}^{S−R} conditioned on H_{1} = B is a p(· | S − R)-forest labeled by S − R with roots B. (iii) Conditionally given H_{1} = B, the restricted forest F_{R}^{S−R} is independent of the random variables M_{b}(F_{R}), b ∈ B, which are independent with common distribution p(· | R). (iv)

the distribution of |H_{1}| − 1 is binomial(|S| − |R| − 1, p_{R})  (31)

(v) given |H_{1}| = k the restricted forest F_{R}^{S−R} is a p(· | S −R)-forest of k trees labeled by S − R, with roots(F_{R}^{S−R}) = H_{1}.

The following consequence of the previous lemma is the basis for the calculation of various oriented percolation probabilities in Section 5.5. The notation r ⇝^{F_{R}} s was defined around (10).

Theorem 4 For F_{R} a p-forest labeled by S with roots R ⊂ S,

P (r ⇝^{F_{R}} s) = p_{r}/p_{R}  (r ∈ R, s ∈ S − R)  (32)

and for all such r and s the event (r ⇝^{F_{R}} s) is independent of the restriction of F_{R} to S − R.

Proof. Given H_{1} = B say let X ∈ B be the root of the subtree containing s in the restriction of F_{R} to S − R. There is a path from r to s in F_{R} if and only if M_{X} = r where M_{X} ∈ R is the mother of X in F_{R}. But according to part (iv) of Lemma 3, given the restricted forest F_{R}^{S−R}, which together with s determines X, the random variables M_{b} for b ∈ B are independent with common distribution p(· | R). Therefore, the conditional distribution of M_{X} given F_{R}^{S−R} is p(· | R), as claimed. □

Distribution of level sets. For a random forest F labeled by S let H_{h}(F) denote the random subset of S defined by the vertices of F at height h from the root. So H_{0}(F) = roots(F), and for each h ≥ 1 the set H_{h}(F) is the set of all children of vertices in H_{h−1}(F). Repeated application of Lemma 3 gives a simple formula for the joint distribution of (H_{i}(F_{R}), 1 ≤ i ≤ h) for any fixed h. In particular, for F_{R} a p-forest with roots R, for each sequence of m non-empty subsets (B_{h}, 1 ≤ h ≤ m) whose union is S − R,

P (H_{h}(F_{R}) = B_{h} for all 1 ≤ h ≤ m) = p_{R}^{|B_{1}|−1} ∏_{h=2}^{m} p_{B_{h−1}}^{|B_{h}|}.  (33)

This is a generalization of a formula of Katz [51] for p uniform and F_{R} derived by conditioning F(M) on cyclic(M) = R for M a uniform random mapping. See [32, 71] regarding asymptotics of the height profile defined by counts of vertices at various levels in a uniform random forest.

4 Spanning Subtrees

Following the approach of Aldous [9, 10, 11] to the asymptotic structure of large random trees, the problem arises of describing the distribution of the subtree spanned by some subset B of the set of vertices of a p-tree T . This problem is most simply treated in terms of the unrooted tree derived from T , whose basic properties are summarized by the following lemma.

Lemma 5 Let U be the unrooted tree obtained by ignoring the direction of edges in a random rooted tree T labeled by S. Then the following two conditions are equivalent:

(i) The rooted tree T is a p-tree, meaning

P (T = T) = ∏_{s∈S} p_{s}^{|T_{s}|}  (T ∈ T_{S})  (34)

where T_{S} is the set of |S|^{|S|−1} rooted trees T labeled by S, with edges directed away from root(T). (ii) The distribution of the unrooted tree U is given by the formula

P (U = U) = ∏_{s∈S} p_{s}^{D_{s}U−1}  (U ∈ U_{S}),  (35)

where U_{S} is the set of |S|^{|S|−2} unrooted trees labeled by S and

D_{s}U := |{v : s ⟷^{U} v}|

is the degree of s in U ∈ U_{S}, and U is independent of root(T ) which has distribution p:

P [root(T ) = r] = p_{r}  (r ∈ S).  (36)

Proof. This follows easily from the tree volume formula, that is (5) for |R| = 1, using the well known bijection between U_{S} and the set T_{S,r} of all trees T ∈ T_{S} with root(T) = r, for any fixed r ∈ S. □

The fact that the probabilities in (35) sum to 1 over all U ∈ U_{S} amounts by scaling to Cayley’s multinomial expansion over unrooted trees [25, 76, 70]

∑_{U∈U_{S}} ∏_{s∈S} x_{s}^{D_{s}U−1} = ( ∑_{s∈S} x_{s})^{|S|−2}  (37)

which for x_{s} ≡ 1 reduces to the Cayley’s formula |U_{S}| = |S|^{|S|−2}.

Let U be an unrooted p-tree labeled by S, meaning that U has distribution (35). For an undirected graph G with vertex set S, the probability P (U ⊆ G) is the sum of probabilities (35) over all spanning trees U of G. Kelmans [54] obtained some results about this polynomial in (p_{s}, s ∈ S), which he called the spanning tree volume of the vertex-weighted graph (G, p). See also [52] for some generalizations which can be interpreted in terms of random rooted forests, as indicated in [72]. Part (iii) of the following theorem yields a formula for P (U ⊇ G) for the only graphs G for which this probability is non-zero, that is unrooted forests G. Parts (i) and (ii) of the theorem are the key to the construction in [5] of a model for random trees with edge lengths related to the asymptotics of p-trees with a large number of vertices.

Theorem 6 Let U be an unrooted p-tree labeled by S.

(i) For each unrooted tree U with vertex set V (U) ⊆ S,

P (U ⊇ U) = p_{V (U)} ∏_{v∈V (U)} p_{v}^{D_{v}U−1}  (38)

where D_{v}U is the degree of vertex v in the tree U.

(ii) Let B be a subset of S of size two or more, and let U_{B} denote the subtree of U spanning B. Then for every unrooted tree U labeled by V (U) with B ⊆ V (U) ⊆ S, such that the set of vertices of U of degree one is contained in B, P (U_{B} = U) = P (U ⊇ U) as given in (38). (iii) For each sequence of unrooted trees U_{i}, 1 ≤ i ≤ m with disjoint sets of vertices V (U_{i}) ⊆ S, the events (U ⊇ U_{i}) are mutually independent:

P (∩_{i=1}^{n}(U ⊇ U_{i}) = ∏_{i=1}^{m} P (U ⊇ U_{i}).  (39)

Proof. Fix a tree U with V (U) = R ⊆ S. Given that U ⊇ U, let F_{R} denote the forest with roots(F_{R}) = R derived from U by first deleting all the edges of U, (which are contained in R × R) then directing the remaining edges away from R. In view of the obvious way that U can then be recovered from U and F_{R}, it is easily checked that for each F ∈ F_{S,R}

P (U ⊇ U, F_{R} = F) = (∏_{s∈S} p_{s}^{|F_{s}|}) ∏_{v∈R} p_{v}^{D_{v}U−1}  (40)

and (38) follows by summation over all F ∈ F_{S,R}, using the forest volume formula (5) and p_{S} = 1. This proves (i), and (ii) follows easily. An alternate proof of (i) can be given by appealing to formula (9), and this argument yields (iii) as well. □

As the notation of the above proof is intended to suggest, formula (40) implies that for each tree U with V (U) = R ⊆ S,

F_{R} is a p-forest with roots R, given U ⊇ U,  (41)

hence also F_{R} is a p-forest with roots R given that the restriction of U to R is a tree. Compare with the alternate constructions from p-mappings given by (19) and (23).

Corollary 7 For distinct u, v ∈ S let R_{u,v} := V (U_{{u,v}}) be the random set of vertices along the path in a p-tree U from u to v, including u and v. Then the distribution of R_{u,v} is determined by the formula

P (R_{u,v} = R) = (|R| − 2)! p_{R} ∏_{r∈R−{u,v}} p_{r}  ({u, v} ⊆ R ⊆ S). (42)

Proof. For B = {u, v} with u ≠ v, the subtree U_{{u,v}} is determined by its set of vertices R_{u,v} and the order of these vertices along the path from u to v in U. For each R ⊇ {u, v} with |R| = k, and each permutation (r_{1}, …, r_{k}) : {1, …, k} → R with r_{1} = u and r_{k} = v, formula (40) shows that the path from u to v in U equals (r_{1}, …, r_{k}) with probability p_{R} ∏_{v∈R−{u,v}} p_{v}. Since there are (k − 2)! possible paths, each with this same probability, (42) follows. □

Since u ⟷^{U} v if and only if R_{u,v} = {u, v}, the particular case of (42) with R = {u, v} gives for u ≠ v

P (u ⟷^{U} v) = p_{u} + p_{v}.  (43)

If U is defined by unrooting a rooted p-tree T , then obviously

P (u ⟷^{U} v) = P (u →^{T} v) + P (v →^{T} u)  (44)

so (43) is implied by the simpler formula

P (u →^{T} v) = p_{u}  (45)

which can be read from (9). A later formula (91) gives the generalization of (45) for a p-forest F instead of a p-tree T . Another extension of (43), which can be read from (38) and (37), is the following formula, valid for arbitrary V ⊆ S:

P (the restriction of U to V is a tree) = p_{V}^{|V |−1},  (46)

and given that this event occurs, the restricted tree is a p(· | V)-tree. See Section 6 for more about restrictions of p-trees and p-forests. As a check, for uniform p formula (43) reduces to the well known result [60],[62, Th. 6.1] that for n ≥ 2 the number of unrooted trees labeled by a set of n vertices which contain a particular edge is 2n^{n−3}. As remarked by Stone [84] this number can be computed in another way to yield an instance of one of Abel’s binomial identities [37]. A variation of this argument, indicated in [72], yields Hurwitz’s generalization of Abel’s identity stated as (55) in the next section, and its multivariate form expressed probabilistically in Proposition 15.

Some useful variations of formula (42) can be formulated as follows, in terms of a rooted p-tree T . See also [24] for closely related formulae.

Corollary 8 For T ∈ T_{S} and v ∈ S let R(T, v) denote the range of the directed path in T from root(T) to v. In particular, R(T, v) = {v} if root(T) = v. Let T be a p-tree with vertex set S. Then

(i) for each fixed v ∈ S

P [R(T , v) = R] = (|R| − 1)! p_{R} ∏_{r∈R−{v}} p_{r}  (v ∈ R ⊆ S); (47)

(ii) if V is a random vertex with distribution p on S, independent of T , then

P [R(T , V) = R] = |R|! p_{R} ∏_{r∈R} p_{r}  (R ⊆ S).  (48)

Proof. (i) Formula (47) can be deduced like (42) from a variant of (40) with rooted trees, or obtained as follows by application of Lemma 5 and Corollary 7. Let U be the unrooted p-tree derived from T , and let R_{u,v} be as in Corollary 7. Then for |R| ≥ 2

P (R(T , v) = R) = ∑_{u∈R−{v}} P (root(T ) = u, R_{u,v} = R)

= ∑_{u∈R−{v}} p_{u}P (R_{u,v} = R)

since root(T ) has distibution p, and root(T ) is independent of U and hence of R_{u,v}, by Lemma 5. Formula (47) now follows from (42). Moreover, (47) holds also in the case |R| = 1, that is for R = {v}, since it then reduces to the previous result (35) that root(T ) has distribution p. (ii) By independence of T and V,

P [R(T , V) = R] = ∑_{v∈R} p_{v}P [R(T , v) = R]

and (48) follows from (47). □

Compare (48) and (27) to see that the range R(T , V) of the path in a p-tree from its root to an independent p-distributed vertex V has the same distribution as the random set of cyclic points of a p-mapping M:

R(T , V) =^{d} cyclic(M)  (49)

and hence

|R(T , V)| =^{d} |cyclic(M)|.  (50)

So formulae (28) and (29) for the distribution of |cyclic(M)|, and the asymptotic results derived from these formulae in [24], apply to R(T , V) as well as to cyclic(M).

4.1 Joyal’s bijection between marked rooted trees and mappings

The coincidence in distribution (49), and numerous further coincidences involving the distributions of functionals of p-trees and p-mappings, are explained by Joyal’s bijection J : (T_{S} × S) → S, which is constructed as follows. First, for each subset R of S with |R| = k ≥ 1, set up a bijective correspondence between the k! permutations

(r_{1}, …, r_{k}) : [k] → R = {r_{1}, …, r_{k}}

and the k! permutations π : R → R, say

π(s) = π_{(r_{1},...,r_{k})}(s) ∈ R = {r_{1}, …, r_{k}}.

One way to do this is to declare π(s) = r_{j} if s is the jth smallest element of R with respect to some total ordering of S. But other choices of the π corresponding to (r_{1}, …, r_{k}) may be useful, as indicated later. Given such a correspondence, for T ∈ T_{S}, v ∈ S define a mapping M = J(T, v) ∈ S^{S} by letting M_{s} be the mother of s in T, except if v lies on the path (r_{1}, …, r_{k}) say in T from r_{1} = root(T) to r_{k} = v, in which case

M_{s} = π_{(r_{1},...,r_{k})}(s) ∈ {r_{1}, …, r_{k}}.

Joyal [49, p. 16] observed that J sets up a bijection between T_{S} × S and S^{S}, and that Cayley’s formula |T_{S}| = |S|^{|S|−1|} is an immediate consequence. By construction, if M = J(T, v) then the set of cyclic points of M is the range of the directed path in T from root(T) to v:

cyclic(M) = R(T, v),  (51)

and furthermore the forest derived from M is

F(M) = T − {edges of T on the path in T from root(T) to v}. (52)

The coincidence in distribution (49) is now explained by the following proposition.

Proposition 9 Let T be a p-tree with vertex set S, and V an S-valued random variable independent of T , with distribution p on S. Then M := J(T , V) is a p-mapping of S.

Proof. Since M is determined by its forest F(M) and the its action as a permutation of roots(F(M)) = cyclic(M), it suffices to check that the joint distribution of F(M) and the restriction M to cyclic(M) is given by the same formula (22) as if M were a p-mapping. But this formula (22) is readily verified by a variation of formula (40) for rooted trees, using (51) and (52), where the factor of p_{v} required in the formula appears from P (V = v) = p_{v}. □

Proposition 9 provides a powerful method for transferring results on the asymptotic structure of p-trees to corresponding results for p-mappings. See [7].

5 Hurwitz distributions

Hurwitz [43] studied sums of the form

H_{n}^{γ,δ} := H_{n}^{γ,δ}(x, y; z_{s}, s ∈ [n]) := ∑_{A⊆[n]}(x + z_{A})^{|A|+γ}(y + zĀ)^{|Ā|+δ}  (53)

for integers γ and δ, where the sum is over all 2^{n} subsets A of [n], and Ā := [n] − A. Hurwitz used recurrences to obtain the identities

xH_{n}^{−1,0} = yH_{n}^{0,−1} = (x + y + z_{[n]})^{n},  (54)
xyH_{n}^{−1,−1} = (x + y)(x + y + z_{[n]})^{n−1}  (55)

which follows easily from (54), and

H_{n}^{0,0} = ∑_{A⊆[n]} |A|!(∏_{s∈A} z_{s})(x + y + z_{[n]})^{|Ā|}.  (56)

As noted by Hurwitz, for z_{s} ≡ 1 these formulae yield evaluations of corresponding Abel sums [1]

A_{n}^{γ,δ}(x, y) := ∑_{a=0}^{n} \binom{n}{a}(x + a)^{a+γ}(y + n − a)^{n−a+δ}.  (57)

Strehl [86] explains how Hurwitz was led to such identities via the combinatorial problem, which arose in the theory of Riemann surfaces [42], of counting the number of ways a given permutation can be written as a product of a minimal number of transpositions which generate the full symmetric group. For various combinatorial interpretations of these identities and related formulae see [2, 47, 55, 36, 22, 77, 80, 85, 87].

Definition 10 Let p be a probability distribution on the interval of integers [0, n + 1] := {0, 1, …, n, n + 1}. Say that a random subset V of [n] has the Hurwitz distribution of index (γ, δ) with parameters p_{0}, p_{1}, …, p_{n+1}, abbreviated H_{n}^{γ,δ}(p), if P (V = A) is proportional to the Ath term of the Hurwitz sum H_{n}^{γ,δ}(p) = H_{n}^{γ,δ}(p_{0}, p_{n+1}; p_{s}, s ∈ [n]) defined by (53) as A ranges over subsets of [n]. That is to say

P (V = A) = H_{n}^{γ,δ}(p)^{−1}(p_{0} + p_{A})^{|A|+γ}(p_{n+1} + pĀ)^{|Ā|+δ}  (A ⊆ [n]). (58)

where in particular, according to (54) and (55),

H_{n}^{−1,0}(p) = \frac{1}{p_{0}} and H_{n}^{−1,−1}(p) = \frac{p_{0} + p_{n+1}}{p_{0}p_{n+1}}  (59)

Call the distribution of |V | on [0, n] induced by such a random subset V of [n] the H_{n}^{γ,δ}(p)-binomial distribution.

These formulae should be interpreted by continuity in the limit cases when either p_{0} or p_{n+1} equals 0. In the Abel case

p_{0} = x/Σ; p_{n+1} = y/Σ; p_{i} = 1/Σ for i ∈ [n]  (60)

where Σ := x + y + n for arbitrary x, y ≥ 0, the H_{n}^{γ,δ}(p)-binomial distribution on [0, n] is obtained by normalization of the terms of the corresponding Abel sum A_{n}^{γ,δ}(x, y) defined by (57). Call this the Abel-binomial distribution or A_{n}^{γ,δ}(x, y)-binomial distribution to indicate the parameters. The Abelbinomial distributions A_{n}^{−1,−1}(x, y) and A_{n}^{−1,0}(x, y) are known in the statistical literature as quasi-binomial distributions [30, 29, 28, 26].

5.1 Constructions from p-mappings

Recall from (20) that pred(v, M) is the set of predecessors of v induced by a mapping M. The following theorem summarizes some natural constructions from random mappings of random subsets of [n] with Hurwitz distributions: See also Berg and Mutafchiev [18] for a closely related appearance of Abelbinomial distributions in connection with random mappings.

Theorem 11 Let M be a p-mapping of [0, n+1]. Then each of the following three random subsets of [n] has the Hurwitz distribution H_{n}^{−1,0}(p):

(i) (Françon [36, p. 339]) assuming p_{0}p_{n+1} > 0, the random set pred(0, M) conditionally given that both 0 and n + 1 are fixed points of M; (ii) (Jaworski [48, Theorem 3]) assuming p_{n+1} = 0, the random set [n] ∩ pred(0, M); (iii) assuming p_{n+1} > 0, the random set pred(0, M) conditionally given that n + 1 is the unique cyclic point of M. Moreover, assuming p_{0}p_{n+1} > 0, a random subset of [n] with the Hurwitz distribution H_{n}^{−1,−1}(p) is obtained from (iv) (Françon [36, Prop. 3.5]) assuming p_{0}p_{n+1} > 0, the random set pred(0, M) conditionally given that both 0 and n + 1 are the unique fixed points of M.

Proof. Parts (i), (ii) and (iv) can be read from the sources cited. Part (iii) is equivalent to the result formulated and proved for a p-tree in Theorem 12 below. All parts are easily checked using the forest volume formula (5). □

Before discussing the translation of (iii) in terms of a p-tree, it is worth noting some striking differences between the first three cases of Theorem 11. Each connected component C of D(M) contains a unique cycle C_{0}, and C decomposes further into a collection of tree components of F(M) whose set of roots is C_{0}. In case (i) of the proposition, the conditioning forces pred(0, M)∪{0} to be a connected component of D(M) which is a single tree component of F(M) rooted at 0, while n + 1 is forced to be the unique cyclic point of another component of D(M). In case (ii) the set pred(0, M) ∪ {0} may be either the union of a tree component of F(M) and a cycle of arbitrary size, or just a subtree of a tree component, according to whether or not 0 ∈ cyclic(M). In case (iii) the conditioning forces F(M) to be a tree rooted at n + 1, and pred(0, M) ∪ {0} is a fringe subtree of this tree, as discussed below. As discussed in [15], it is possible to pass between the various cases of Theorem 11 using Joyal’s bijection between random mapppings and marked trees, as described in Section 4.

5.2 Constructions from p-trees

For a forest F labeled by S let V_{s}(F) := {v ∈ S −{s} : s ⇝^{t} v} denote the set of non-root vertices of the fringe subtree of T rooted at s, that is the tree T (s) labeled by {s} ∪ V_{s}(T) whose edge relation is the restriction to {s} ∪ V_{s}(T) of the edge relation of T. See [8] for background and further references to fringe subtrees. If T is a tree component of the forest F(M) derived from a mapping M, so T is rooted at some vertex r ∈ cyclic(M), then for each non-root vertex s of T the set pred(s, M) of predecessors of s induced by M is identical to V_{s}(T). As remarked below (23), conditioning a p-mapping M to have a unique cyclic point r makes F(M) a p-tree with root r. Case (iii) of Theorem 11 can thus be reformulated as follows in terms of trees instead of mappings:

Theorem 12 Let T_{n+1} be a p-tree labeled by [0, n + 1] with root n + 1, where p is a probability distribution on [0, n + 1] with p_{n+1} > 0. Then the random set V_{0}(T_{n+1}) of non-root vertices of the fringe subtree of T_{n+1} rooted at 0 has the Hurwitz distribution H_{n}^{−1,0}(p) on subsets of [n]. That is, for all A ⊆ [n], with Ā := [n] − A.

P (V_{0}(T_{n+1}) = A) = p_{0}(p_{0} + p_{A})^{|A|−1}(p_{n+1} + pĀ)^{|Ā|}.  (61)

Proof. Fix an arbitrary subset A of [n]. The probability P (V_{0}(T_{n+1}) = A) is the sum of the probabilities P (T_{n+1} = T) over all T such that (i) the restriction of T to A ∪ {0} is a tree with root 0, and (ii) the restriction of T to Ā ∪ {0} ∪ {n + 1} is a tree with root n + 1 which has 0 as a leaf. Each of these probabilities factorizes into one product involving (p_{s}, s ∈ A∪{0}) and another involving (p_{s}, s ∈ Ā ∪ {n + 1}). The sum of products is therefore the product of two sums which can be evaluated using the tree volume formula (5), first with r = 0 and S = A ∪ {0}, then with r = n + 1 and S = Ā ∪ {0} ∪ {n + 1} with x_{0} = 0. □

The same technique yields the following variation of Theorem 12:

Theorem 13 Let V_{0}(F_{k}) ⊆ [n] be the set of non-root vertices of the fringe subtree of F_{k} rooted at 0, for F_{k} a p-forest of k trees labeled by [0, n]. Then for A ⊆ [n], with Ā := [n] − A,

P (V_{0}(F_{k}) = A) = \binom{n}{k − 1}^{−1}p_{0}(p_{0} + p_{A})^{|A|−1}\binom{|Ā|}{k − 1}p|Ā|−(k−1) ; Ā.  (62)

Proof. This is similar to the proof of the previous proposition. Fix A ⊆ [n]. A forest F has V_{0}(F) = A if and only if (i) the restriction of F to A∪{0} is a tree with root 0, and (ii) the restriction of F to Ā ∪ {0} is a forest of k trees with 0 as a leaf vertex. The relevant sum of products is therefore factorizes into a product of two sums, the first of whichwhich can be evaluated using the forest volume formula (5) with R = {0}, S = A ∪ {0}, and the second of which yields to (8) with S = Ā ∪ {0} and x_{0} = 0. □

5.3 Distribution of tree components

Formulae for the distributions of variously defined tree components of a pforest follow easily from the forest volume formula. The next two propositions are typical examples.

Proposition 14 Let p be a probability distribution on [0, n], and let 2 ≤ k ≤ n. For F_{k} with the distribution induced by p on forests of k trees labeled by [0, n], let W_{0}(F_{k}) ⊆ [n] be the random set of all vertices other than 0 in the tree component of F_{k} containing 0. Then for A ⊆ [n], with Ā := [n] − A,

P (W_{0}(F_{k}) = A) = \binom{n}{k − 1}^{−1}\binom{|Ā| − 1}{k − 2}(p_{0} + p_{A})^{|A|}p|Ā|−(k−1) ; Ā (A ⊆ [n])

(63)

The first part of the following proposition spells out the probabilistic interpretation of Hurwitz’s multinomial theorem [43, VI] [72, (16)] in terms of a p-forest with roots R, as defined by (18).

Proposition 15 Let F_{R} be a p-forest with roots R and vertex set R ∪ [n], with R disjoint from [n]. For r ∈ R let V_{r}(F_{R}) be the random subset of [n] defined by the non-root vertices of the tree component of F_{R} containing r. Then

(i) for each of |R|^{n} possible choices of disjoint subsets (B_{r}, r ∈ R) whose union is [n]

P (V_{r}(F_{R}) = B_{r} for all r ∈ R) = p_{R}^{−1} ∏_{r∈R} p_{r}(p_{r} + p_{B_{r}})^{|B_{r}|−1}  (64)

(ii) for each subset B of R the random set V_{B}(F_{R}) := ∪_{r∈B}V_{r}(F_{R}) has the Hurwitz distribution H_{n}^{−1,−1}(p^{B}) on subsets of [n], where p_{0}^{B} = p_{B}, p_{n+1}^{B} = p_{R−B}, and p_{s}^{B} = p_{s} for s ∈ [n].

For V_{B}(F_{R}) defined as in the previous Proposition, there is the remarkably simple formula

E(|V_{B}(F_{R})|) = np_{B}/p_{R}  (65)

because V_{B}(F_{R}) is the sum of the indicator variables χ(r ⇝^{F_{R}} s) over all r ∈ B and s ∈ [n], so formula (32) can be applied to compute:

E(|V_{B}(F_{R})|) = ∑_{r∈B} ∑_{s=1}^{n} P (r ⇝^{F_{R}} s) = ∑_{r∈B} np_{r}/p_{R} = np_{B}/p_{R}.  (66)

On the other hand, Proposition 15(ii) shows that (65) amounts to:

Proposition 16 The mean of the H_{n}^{−1,−1}(p)-binomial distribution of |V_{n,p}|, where V_{n,p} is a random subset of [n] with the Hurwitz H_{n}^{−1,−1}(p) distribution, is

E (|V_{n,p}|) = n (\frac{p_{0}}{p_{0} + p_{n+1}} ) .  (67)

This formula can also be checked as follows. Differentiate Hurwitz’s formula (54) with respect to x to obtain

∑_{A⊆[n]} y |A| (x + z_{A})^{|A|−1}(y + zĀ)^{|Ā|−1} = n(x + y + z_{[n]})^{n−1}.  (68)

From the definition (10) of the H_{n}^{−1,−1}(p) distribution,

E(|V_{n,p}|) = ∑_{A⊆[n]} \frac{|A| p_{0} p_{n+1}}{(p_{0} + p_{n+1})}(p_{0} + p_{A})^{|A|−1}(p_{n+1} + pĀ)^{|Ā|−1}

and (67) follows by application of (68) with x = p_{0}, y = p_{n+1} and z_{s} = p_{s} for s ∈ [n]. □

Formula (67) is a generalization of the known result [26] that the Abel A_{n}^{−1,−1}(x, y)-binomial distribution has mean nx/(x + y). The proof of (67) just indicated via (66) provides a probabilistic explanation for this otherwise mysterious exception to the general rule that moments of Abel-binomial distributions are not simple functions of the parameters. See for instance [26] where a complicated expression is obtained for the second factorial moment of the A_{n}^{−1,−1}(x, y)-binomial distribution. In view of this difficulty in the Abel case, it does not seem possible to simplify the Hurwitz sums for higher moments of the H_{n}^{−1,−1}(p)-binomial distribution. For the H_{n}^{0,−1}(p)-binomial distribution, the Hurwitz sum for the mean does not simplify even in the Abel case.

5.4 A Hurwitz multinomial distribution

Riordan [77] considers multinomial forms of Abel’s binomial theorem. See Berg and Mutafchiev [18] for the appearance of an Abel-trinomial distribution in the context of random mappings. The following definition is motivated by Proposition 15.

Definition 17 For a probability distribution p on [n]∪R with p_{R} > 0, where R is a finite set disjoint from [n], say that a random vector of non-negative integers N_{R} := (N_{r}, r ∈ R) has the Hurwitz(p)-multinomial distribution if for all vectors of non-negative integers n_{R} := (n_{r}, r ∈ R) with ∑_{r} n_{r} = n

P (N_{R} = n_{R}) = p_{R}^{−1} ∑_{(B_{r})} ∏_{r∈R} p_{r}(p_{r} + p_{B_{r}})^{n_{r}−1}  (69)

where the sum is over all n!/(∏_{r} n_{r}!) possible choices of disjoint subsets B_{r} of [n] whose union is [n] with |B_{r}| = n_{r}, r ∈ R.

According to Proposition 15, a random vector N_{R} with this distribution is obtained by letting N_{r} be the size of the tree rooted at r in a p-forest with roots R and vertex set [n]∪R. The usual multinomial distribution with parameters n and (p_{r}, r ∈ R) corresponds to the case when p_{s} = 0 for all s ∈ [n]. Then in the forest F_{R}, each vertex s ∈ [n] is a leaf attached to a root M_{s} ∈ R where the M_{s} are independent with common distribution p. According to Lemma 3, in the general model the restricted forest F_{R}^{[n]} clusters the elements of [n] into a random number K of subtrees such that K − 1 has binomial(n − 1, p_{R}) distribution. Given K the forest F_{R}^{[n]} is a p(· | [n])-forest of K trees labeled by [n], and each of these subtrees is attached to a root picked independently from R according to p(· | R). The size N_{r} of the tree rooted at r is then the sum of the sizes of those subtrees of F_{R}^{[n]} that happen to have r chosen as their root. From this construction of a random vector N_{R} with the Hurwitz(p)-multinomial distribution it follows without calculation that this family of multivariate distributions shares with the usual family of multinomial distributions the following basic rule for merging of categories. That is, if Ψ is a map from R to Q say, and N_{Q} is derived from N_{R} by merging categories according to Ψ, so the qth component of N_{Q} is the sum of N_{r} over r with Ψ(r) = q, then N_{Q} has the Hurwitz(p′)-multinomial distribution, where p′ is the probability distribution on Q ∪ [n] defined by p′_{s} = p_{s} if s ∈ [n] and p′_{q} is the sum of p_{r} over r with Ψ(r) = q.

5.5 Percolation probabilities

Write u ∼^{f} v if there is a path from u to v in the undirected graph obtained by ignoring edge directions in a rooted forest F, that is if T_{u}(F) = T_{v}(F), where T_{v}(F) denotes the set of vertices of the tree component of F containing

v. Write u ≁^{f} v if there is no such path, meaning T_{u} and T_{v} are disjoint. This Section treats the problem of finding expressions for the percolation probability P (s ∼^{F_{k}} v) and the oriented percolation probability P (s ⇝^{F_{k}} v) for two vertices s and v of a p-forest F_{k}. See [23, 73, 46] for closely related studies of such percolation probabilities for the digraph of a random mapping, and [39] for a study of such problems for other models of random forests, and applications to reliability of networks.

Unriented percolation. By a suitable relabeling, it suffices to consider P (0 ∼^{F_{k}} n + 1) in the case S := [0, n + 1] and 2 ≤ k ≤ n + 1. By an argument similar to the proof of Proposition 14,

P (0 ∼^{F_{k}} n + 1) = ∑_{A⊂[n]} \binom{n + 1}{k − 1}^{−1}(p_{0} + p_{n+1} + p_{A})^{|A|+1}\binom{|Ā| − 1}{k − 2}p|Ā|−k+1 ; Ā (70)

where Ath term is P (T_{0}(F_{k}) = T_{n+1}(F_{k}) = {0} ∪ {n + 1} ∪ A). Similarly

P (0 ≁^{F_{k}} n + 1) = ∑_{A⊂[n]} \binom{n + 1}{k − 1}^{−1}(p_{0} + p_{A})^{|A|}\binom{|Ā|}{k − 2}(p_{n+1} + pĀ)^{|Ā|−k+2} (71)

where the Ath term is P (T_{0}(F_{k}) = {0} ∪ A). Another expression for the same probability is obtained by switching p_{0} and p_{n+1}, since the Ath term is then P (V_{n+1}(F_{k}) = {n + 1} ∪ A). The consequent equality of polynomials in p_{s}, s ∈ S is a non-trivial identity, even in the Abel case (60). So is the equality between either of these expressions and 1 minus the right hand expression in (70), where 1 must be replaced by (∑_{i=0}^{n+1} p_{s})^{n−k+2} to obtain the general polynomial identity.

Oriented percolation. By a relabeling of vertices, the problem of finding P (s ⇝^{F_{k}} v) for two arbitrary vertices s and v of a p-forest F_{k} is reduced to the case when S = [0, n+1], s = 0 and v = n+1, as in the following proposition.

Proposition 18 Let F_{k} be a p-forest of k trees labeled by [0, n + 1]. Then

P (0 ⇝^{F_{k}} n + 1) = ∑_{A⊆[n]} \frac{(|Ā|)_{k−1}}{(n + 1)_{k−1}} p_{0}(p_{0} + p_{A})^{|A|}(p_{n+1} + pĀ)^{|Ā|−(k−1)} (72)

where the Ath term equals P (0 ⇝^{F_{k}} n + 1, V_{k} = A) for V_{k} the random set of all v ∈ [n] such that there exists a directed path from 0 to v in F_{k} that does not pass via n + 1. Also

P (0 ⇝^{F_{k}} n + 1) = ∑_{A⊆[n]} \frac{(|Ā|)_{k−1}}{(n + 1)_{k−1}} |A|! p_{0} ∏_{s∈A} p_{s}  (73)

where the Ath term equals P (0 ⇝^{F_{k}} n + 1, L_{k} = A) for L_{k} the random set of all v ∈ [n] such that v lies on the path which joins 0 to the root of its tree component in F_{k}.

Proof. These formulae are obtained by application of the forest volume formula, with the help of Theorem 4. See [72] for details. □

For k = 1, Proposition 18 yields Hurwitz’s expression (56) for H_{n}^{0,0}, along with the following probabilistic interpretation: for T_{n} a p-tree labeled by [0, n + 1]

P (0 ⇝^{T_{n}} n + 1) = p_{0}H_{n}^{0,0}(p_{0}, p_{n+1}; p_{j}, j ∈ [n]).  (74)

In the Abel case (60) with x = y = 1 this implies that A_{n}^{0,0}(1, 1) is the number of rooted trees labeled by [0, n + 1] in which there is a directed path from u to v, for arbitrary distinct u, v ∈ [0, n + 1]. It is easy to deduce from this the result of Moon [61, Theorem 1], that for T_{n} with uniform distribution on rooted trees labeled by [0, n + 1], the conditional expectation of the size |{v : 0 ⇝^{T_{n}} v}| of the fringe subtree of T_{n} with root 0, given that T_{n} has some root other than 0, is A_{n}^{0,0}(1, 1)/(n + 2)^{n}. As observed by Moon, this conditional expectation is also the expected distance in T between any two distinct vertices u, v ∈ S, which is asymptotically equivalent to \sqrt{πn/2} for large n. See [14] for a study of the asymptotic behaviour for large n of the distribution of the size of the fringe tree {v : 0 ⇝^{T} v} for T distributed according to a non-uniform forest volume distribution on trees labeled by S, and [5, 24] for further study of the asymptotics of large random trees of this kind.

6 Restrictions of p-forests

Call a random forest F with a random number of trees a p-forest if F is a p-forest of k trees conditionally given that F has k trees. Put another way, a random element F of the set F_{S} of all forests of rooted trees labeled by S is a p-forest if and only if the distribution of F is given by the formula

P (F = F) = w_{|F |} ∏_{s∈S} p_{s}^{|F_{s}|}  (F ∈ F_{S})  (75)

for some sequence of weights (w_{m}, 1 ≤ m ≤ |S| − 1), where |F | = ∑_{s} |F_{s}| is the number of edges of F. Note. By Proposition 2 (i) and (27), the forest F(M) derived from a pmapping is a p-forest if and only if p is uniform on S. However, Corollary 20 below shows how a p(·|B)-forest for B ⊂ S can be obtained by suitable conditioning of a p-mapping.

The following restriction theorem is proved in the next subsection.

Theorem 19 For B a non-empty subset of S and F a p-forest labeled by S, the restriction F^{B} of F to B is a p(· | B)-forest. The distribution of |F^{B}| on 0, …, |B|−1 is determined by p_{B} and the distribution of the random number |F| of edges of F by the falling factorial moments

E(|F^{B}|)_{r} = E(|F|)_{r} \frac{(|B| − 1)_{r}}{(n − 1)_{r}} p_{B}^{r} (r = 1, 2, …).  (76)

In particular, if |F| has binomial (|S|−1, q_{0}) distribution for some q_{0} ∈ [0, 1], then |F^{B}| has binomial (|B| − 1, q_{0} p_{B}) distribution.

To be more explicit, the distribution of |F^{B}| is determined by the factorial moments (76) via the well known sieve formula [20, p. 17]

P (|F^{B}| = ℓ) = ∑_{r=ℓ}^{|B|−1} \binom{r}{ℓ}(−1)^{r−ℓ} \frac{E(|F^{B}|)_{r}}{r!} (0 ≤ ℓ ≤ |B| − 1). (77)

Before the proof of Theorem 19, here is a corollary obtained by simply combining this theorem and Lemma 3, followed by some examples to illustrate formula (77). The corollary shows in particular how a q-forest labeled by B can be derived from a p-tree with root 0 ∉ B, for any distribution p on a superset S of B ∪ {0} such that q = p(·|B).

Corollary 20 For R and B disjoint non-empty subsets of a finite set S, with p_{R} > 0, the restriction to B of p-forest with roots R is a p(· | B)-forest with a binomial(|B| − 1, p_{B}) number of edges. In particular, if F(M) is the forest derived from a p-mapping M of S, then conditionally given cyclic(M) = R the restriction of F(M) to B is a p(· | B)-forest with a binomial(|B| − 1, p_{B}) number of edges for each B ⊆ S − R.

Examples. According to (76) and (77), assuming that F = F_{k} has a fixed number k of tree components, so E(|F|)_{r} = (n−k)_{r}, for each B with |B| = b the restriction of F_{k} to B is a tree with probability

P (|F_{k}^{B}| = b − 1) = \frac{(n − k)_{b−1}}{(n − 1)_{b−1}} p_{B}^{b−1}.  (78)

The restriction has two tree components with probability

P (|F_{k}^{B}| = b − 2) = (b − 1) (\frac{(n − k)_{b−2}}{(n − 1)_{b−2}} p_{B}^{b−2} − \frac{(n − k)_{b−1}}{(n − 1)_{b−1}} p_{B}^{b−1}) (79)

and so on. For p uniform, p_{B} = b/n, and the above probabilities are fractions of the total number \binom{n−1}{k−1}n^{n−k} of forests of k rooted trees labeled by [n]. To illustrate with (78), the number of forests of k trees labeled by [n] whose restriction to [b] is a tree is

\frac{(n − k)_{b−1}}{(n − 1)_{b−1}} (\frac{b}{n})^{b−1} \binom{n − 1}{k − 1}n^{n−k} = b^{b−1}\binom{n − b}{k − 1}n^{1+n−b−k}.  (80)

Since b^{b−1} is the number of rooted trees labeled by [b], (80) agrees with the formula of Stanley [81, Ex. 2.11.a] for the number of forests of k trees labeled by [n] which contain a particular forest of 1 + n − b trees, applied to any of the b^{b−1} forests with one tree component equal to [b] and n − b singleton roots. The following proof of Theorem 19 involves formula (9), which is a generalization of the formula of Stanley just mentioned.

6.1 Proof of the restriction theorem

Lemma 21 Let F be a p-forest with restriction F^{B} to B ⊆ S with |B| = b. Then for each G ∈ F_{B} and each vector of non-negative counts (c_{i}, i ∈ B) with P (|F_{i}| = c_{i} for all i ∈ B) > 0

P (F^{B} = G | |F_{i}| = c_{i} for all i ∈ B) = \frac{(n − 1 − c_{B})_{b−|G|−1}}{(n − 1)_{b−1}} ∏_{i∈B}(c_{i})_{|G_{i}|}. (81)

Proof. Assume for convenience that S = [n] := {1, …, n} and B = [b] for some b ∈ [n]. It is easily seen, as in the proof of [70, Thm. 1.6], that conditionally given |F_{i}| = c_{i} for all i ∈ [n], the random set F_{1} of children of 1 has uniform distribution over all subsets of size c_{1} of {2, …, n}, and for each 2 ≤ i < n given also the subsets F_{j} of [n] for all j < i, the random set F_{i} has uniform distribution over all subsets of size c_{i} of some subset of [n] of size n − 1 − c_{1} − ⋯ − c_{i−1}, this subset of [n] being determined by the F_{j} for j < i and the constraint that F is a forest. The event F^{[b]} = G is identical to the event that F_{i} ∩ B = G_{i} for all i ∈ [b]. So conditionally given |F_{i}| = c_{i} for all i ∈ [b] there are

∏_{m=1}^{b} \binom{n − 1 − c_{[m−1]}}{c_{m}} = \frac{(n − 1)!}{(n − 1 − c_{[b]})! ∏_{i=1}^{b} c_{i}!}  (82)

equally likely possible choices of the sets F_{i} for i ∈ [b]. The number of these choices that make the event (F^{[b]} = G) occur is

∏_{m=1}^{b} \binom{n − b − c_{[m−1]} − a_{[m−1]}}{c_{m} − a_{m}} = \frac{(n − b)!}{(n − b − c_{[b]} − a_{[b]}))! ∏_{i=1}^{b}(c_{i} − a_{i})!} (83)

where a_{i} := |G_{i}|, and the ratio of (83) to (82) simplifies to yield (81). To check the left-hand formula in (83), observe that given choices of the F_{i} have been made for i < m in such a way that |F_{i}| = c_{i} and F_{i} ∩ [b] = G_{i} for all i < m, the choice of the set F_{m} of size c_{m} is subject firstly to the constraint that F is a forest, and secondly to the constraint that F_{m} ∩ [b] = G_{m}. This means that there c_{m} − a_{m} elements of [n] − [b] to be chosen. The forest constraint forbids the choice of any of the c_{[m−1]} children of vertices 1, …, m − 1. But due to previous choices, a_{[m−1]} of these forbidden vertices are contained in [b], so there are c_{[m−1]} −a_{[m−1]} forbidden vertices within [n]−[b], and the c_{m} −a_{m} vertices of F_{m}∩([n]−[b]) are chosen from an allowed set of n−b−c_{[m−1]}−a_{[m−1]} vertices. Therefore, no matter what the F_{i} for i < m such that |F_{i}| = c_{i} and F_{i} ∩ [b] = G_{i} for all i < m, the number of possible choices of F_{m} such that F_{m} ∩ [b] = G_{m} is the mth factor on the left side of (83). □

For the rest of this section let C_{B} denote the total number of children of all vertices in B in the p-forest F:

C_{B} := |F ∩ (B × S)| = ∑_{s∈B} |F_{s}|.

Lemma 22 For each G ∈ F_{B} with j tree components and each c with P (C_{B} = c) > 0,

P (F^{[b]} = G | C_{B} = c) = \frac{(n − 1 − c)_{j−1}}{(n − 1)_{b−1}} (c)_{b−j} ∏_{s∈B} (\frac{p_{s}}{p_{B}} )^{|G_{s}|} . (84)

Proof. Again, take S = [n], B = [b], and let C_{i} := |F_{i}| for i ∈ [n]. By application of (81),

P (F^{[b]} = G | C_{B} = c) = \frac{(n − 1 − c)_{j−1}}{(n − 1)_{b−1}} E_{c} (∏_{i=1}^{b}(C_{i})_{|G_{i}|})  (85)

where E_{c} denotes expectation relative to the conditional law of (C_{1}, …, C_{b}) given C_{B} = c, which by Proposition 1 is a multinomial distribution with parameters c and (p_{1}/p_{B}, …, p_{b}/p_{B}). But this expectation can be evaluated by a calculation with the generating function of the multinomial distribution, and the result is (84). □

Lemma 23 For F a p-forest labeled by S, and G a rooted forest labeled by S with r edges,

P (F ⊇ G) = \frac{E(|F|)_{r}}{(|S| − 1)_{r}} ∏_{s∈S} p_{s}^{|G_{s}|}.  (86)

Proof. This can be read from formula (9). □

Completion of the proof. Lemma 22 shows that for each c ∈ [n − 1] the conditional distribution of F^{[b]} given C_{B} = c is that of a p(· | B)-forest, hence so is the unconditional distribution of F^{[b]}. To verify formula (76), recall that for indicator random variables X_{i}, i ∈ I and r = 0, 1, 2, … there is the formula

E\binom{∑_{i∈I} X_{i}}{r} = ∑_{J⊆I:|J|=r} P (∩_{j∈J}(X_{j} = 1)).  (87)

Since

|F^{B}| = ∑_{(s,t)∈B×B} 1(s →^{F} t)  (88)

formula (87) gives for r = 1, 2, …, b − 1

E\binom{|F^{B}|}{r} = ∑_{G⊆B×B:|G|=r} P (F ⊇ G).  (89)

The probability P (F ⊇ G) is zero unless G is a rooted forest labeled with r edges, in which case this probability is given by (86). Thus

E\binom{|F^{B}|}{r} = ∑_{G∈F_{B}: |G|=r} \frac{E(|F|)_{r}}{(|S| − 1)_{r}} ∏_{s∈B} p_{s}^{|G_{s}|} = \frac{E(|F|)_{r}}{(|S| − 1)_{r}} \binom{b − 1}{r}p_{B}^{r} (90)

where the second equality is due to (8). The claim in the binomial case follows easily because the rth factorial moment of the binomial (n − 1, q_{0}) distribution is (n)_{r}q_{0}^{r}. □

6.2 Variations

To illustrate formula (86), for any two distinct s and s′ in S, the probability that a p-forest F contains a particular edge (s, s′) is

P (s →^{F} s′) = \frac{E|F|}{(|S| − 1)} p_{s}.  (91)

For distinct t and t′ in S, with (s, s′) ≠ (t′, t) and s′ ≠ t′, the probability that F contains both (s, s′) and (t, t′) is

P ((s →^{F} s′) ∩ (t →^{F} t′)) = \frac{E(|F|(|F| − 1))}{(|S| − 1)(|S| − 2)} p_{s}p_{t}.  (92)

In particular, for such (s, s′) and (t, t′) the events (s →^{F} s′) and (t →^{F} t′) are independent if F is a p-tree, and negatively correlated if F is a p-forest of k trees for k ≥ 2.

The formula (86) for P (F ⊇ G) may be compared to a determinantal formula of Pemantle [66, Th. 4.2] for such a probability for F a uniform random spanning tree of a graph. In contrast to (86), there is no simple general formula for P (F ⊆ G) for a general directed graph G ⊆ S × S. For instance, in the simplest case when p is uniform on S and F = T say is a tree, then P (T ⊆ G) = t(G)/|S|^{|S|−1} where t(G) is the number of spanning subtrees of G. Some references to the classical problem of evaluating t(G) are [62, Chapter 6] and [Ex. 2.11.a][81]. See also [52] for a technique for finding P (F ⊆ G) for graphs G with special structure.

Lemma 22 has another consequence which is worth recording. Recall that for 1 ≤ n ≤ N and 0 ≤ K ≤ N the hypergeometric (n, N, K) distribution is the distribution of the number of good elements that appear in a random subset of size n picked from a set of K good elements and N −K bad elements [34].

Proposition 24 For F a p-forest labeled by S with |S| = n, and

C_{B}F := ∑_{s∈B} |F_{s}|,

(i) the distribution of C_{B} given |F| = m is binomial (m, p_{B}); (ii) given |F| and C_{B} = c, the distribution of |F^{B}| is hypergeometic (b − 1, n − 1, c); in particular, (iii) if the number of edges of F has binomial (n − 1, q) distribution for some q ∈ [0, 1], then the number |F^{B}| of edges of F in B × B, and the number of edges of F in B × B^{c} are independent, with binomial (b − 1, qp_{B}) and binomial (n − b, qp_{B}) distributions respectively.

Proof. The first part can be read from Proposition 1. Sum the expression (84) over all forests G ∈ F (B) with ℓ edges and simplify using (8) to see that

P (|F^{B}| = ℓ | C_{B} = c) = \frac{(n − 1 − c)_{b−ℓ−1}(c)_{ℓ}}{(n − 1)_{b−1}} \binom{b − 1}{ℓ}

= \binom{c}{ℓ}\binom{n − 1 − c}{b − 1 − ℓ}\binom{n − 1}{b − 1}^{−1}

which yields (ii). Part (iii) is a standard consequence of (i) and (ii). □

An alternative proof of the factorial moment formula (76) can be based on Proposition (24). By standard applications of (87), for S_{n,p} with binomial(n, p) distribution and H_{n,N,G} with hypergeometric(n, N, G) distribution there are the formulae

E\binom{S_{n,p}}{r} = \binom{n}{r}p^{r}; E\binom{H_{n,N,G}}{r} = \binom{n}{r}\frac{(G)_{r}}{(N)_{r}} .  (93)

By application of these formulae and Proposition 24, for F with m edges the binomial moments of N_{B} are

E\binom{N_{B}}{r} = E (E [\binom{N_{B}}{r}| C_{B}]) = \frac{(b − 1)_{r}}{(n − 1)_{r}} E\binom{C_{B}}{r} = \frac{(b − 1)_{r}}{(n − 1)_{r}} \binom{m}{r} p_{B}^{r}

and (76) follows.

Proposition 24 implies the following alternate expression for the distribution of |F^{[b]}|:

P (|F^{[b]}| = ℓ) = \binom{n − 1}{b − 1}^{−1}E [\binom{n − 1 − C_{B}}{b − ℓ − 1}\binom{C_{B}}{ℓ}]  (94)

where C_{B} has binomial (m, p_{B}) distribution given that |F| = m. Compare (94), (77) and (93) to see that the following moment identity (95) must hold for a binomially distributed random variable Y, with some restrictions on x:

E [\binom{x − Y}{a}\binom{Y}{b}] = ∑_{j=0}^{a}(−1)^{j}\binom{b + j}{j}\binom{x − b − j}{a − j}E\binom{Y}{b + j}  (95)

It follows easily that this formula must hold for any random variable Y with all moments finite, for all real x and all non-negative integers a and b. This can be checked as follows. By linearity of the expectation operator E, it suffices to check the formula for a constant random variable Y, say Y = y for some real y. Then the formula reduces easily to

\binom{x − y}{a} = ∑_{j=0}^{a}(−1)^{j}\binom{x − b − j}{a − j}\binom{y − b}{j}.  (96)

Replace x − b by x and y − b by −z to see that this amounts to

\binom{x + z}{a} = ∑_{j=0}^{a} \binom{x − j}{a − j}\binom{z + j − 1}{j}  (97)

for all real x and z, which is a known identity for binomial coefficients (replace n by a, x by z − 1 and y by x − a in Gould [38][(3.2)]). These identities (96) and (97), when written in terms of the hypergeometric function _{2}F_{1}, can be read from the Chu-Vandermonde summation formula.

6.3 Thinning of p-forests

Let T be a p-tree with n vertices. For 0 ≤ q ≤ 1 call F a q-thinning of T if given T the forest F is derived from T by retaining each of the n−1 edges of T independently with probability q. Then, as shown in [70], F is a p-forest whose number of edges has binomial (n − 1, q) distribution. Compare with the conclusion of Corollary 20 to deduce

Corollary 25 The restriction to B of a q-thinning of a p-tree is a p(·|B)- forest with the same distribution as a qp_{B}-thinning of a p(· | B)-tree.

Even for p uniform and q = 1 this result does not seem evident without calculation. Neither does the independence property in part (iii) of Proposition 24 seem obvious even in this case. In the same vein, there is also the following generalization of results in [70]:

Theorem 26 Suppose that F is p-forest. Given F, let each edge s →^{F} t be marked red with probability r_{s}, independently as (s, t) ranges over all directed edges of F. Let F_{red} denote the forest of red edges so obtained, and let p_{∗} := ∑_{s∈S} p_{s}r_{s}. Then F_{red} is a p′-forest, where p′_{s} := p_{s}r_{s}/p_{∗}, and given F has m edges the number of edges of F_{red} has a binomial(m, p_{∗}) distribution.

Proof. This is established by a straightforward calculation using formula (9). □

In particular, if F is a random tree with uniform distribution on the set of all rooted trees labeled by S, then F_{red} obtained by the above construction is a p′-forest with p′_{s} proportional to r_{s}.

Acknowledgment

Thanks to Jürgen Bennies, Ira Gessel, Richard Stanley, Volker Strehl and some anonymous referees for helpful suggestions and remarks on earlier versions of this paper.

References

[1] N.H. Abel. Beweis eines Ausdrucks von welchem die Binomial-Formel einer einzelner Fall ist. Crelle’s J. Reine Angew. Math., 1:159–160, 1826.

[2] H. D. Abramson. A note on a result of Knuth or identities grow on trees. J. Combinatorial Theory, 7:371–373, 1969.

[3] D. Aldous and J. Pitman. Two recursive decompositions of Brownian bridge related to the asymptotics of random mappings. Technical Report 595, Dept. Statistics, U.C. Berkeley. Preliminary Draft. April 27 2001.

[4] D. Aldous and J. Pitman. Brownian bridge asymptotics for random mappings. Random Structures and Algorithms, 5:487–512, 1994.

[5] D. Aldous and J. Pitman. A family of random trees with random edge lengths. Random Structures and Algorithms, 15:176–195, 1999.

[6] D. Aldous and J. Pitman. Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent. Probab. Th. Rel. Fields, 118:455–482, 2000.

[7] D. Aldous and J. Pitman. Brownian bridge asymptotics for non-uniform random mappings. Technical Report 594, Dept. Statistics, U.C. Berkeley, 2001. In preparation.

[8] D.J. Aldous. Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab., 1:228–266, 1991.

[9] D.J. Aldous. The continuum random tree I. Ann. Probab., 19:1–28, 1991.

[10] D.J. Aldous. The continuum random tree II: an overview. In M.T. Barlow and N.H. Bingham, editors, Stochastic Analysis, pages 23–70. Cambridge University Press, 1991.

[11] D.J. Aldous. The continuum random tree III. Ann. Probab., 21:248–289, 1993.

[12] S. Anoulova, J. Bennies, J. Lenhard, D. Metzler, Y. Sung, and A. Weber. Six ways of looking at Burtin’s lemma. Amer. Math. Monthly, 106(4):345–351, 1999.

[13] J. Arney and E.A. Bender. Random mappings with constraints on coalescence and number of origins. Pacific J. Math., 103:269–294, 1982.

[14] J. Bennies and J. Pitman. Asymptotics of the Hurwitz binomial distribution related to mixed Poisson Galton-Watson trees. Combinatorics, Probability and Computing, 10:203–211, 2001.

[15] J. Bennies and A. Weber. A bijection between marked trees and random mappings. Preprint. Dept. Math., Univ. of Frankfurt., 1999.

[16] S. Berg and J. Jaworski. Modified binomial and Poisson distributions with applications in random mapping theory. Journal of Statistical Planning and Inference, 18:313 – 322, 1988.

[17] S. Berg and J. Jaworski. Probability distributions related to the local structure of a random mapping. In A. Frieze and T. Łuczak, editors, Random Graphs, volume 2, pages 1–21. Wiley, 1992.

[18] S. Berg and L. Mutafchiev. Random mappings with an attracting center: Lagrangian distributions and a regression function. J. Appl. Probab., 27:622 – 636, 1990.

[19] S. Berg and K. Nowicki. Statistical inference for a class of modified power series distributions with applications to random mapping theory. Journal of Statistical Planning and Inference, 28:247 – 261, 1991.

[20] B. Bollobás. Random Graphs. Academic Press, London, 1985.

[21] A. Broder. Generating random spanning trees. In Proc. 30’th IEEE Symp. Found. Comp. Sci., pages 442–447, 1989.

[22] A.Z. Broder. A general expression for Abelian identities. In L.J. Cummings, editor, Combinatorics on words, pages 229–245. Academic Press, New York, 1983.

[23] Y. D. Burtin. On a simple formula for random mappings and its applications. J. Appl. Probab., 17:403 – 414, 1980.

[24] M. Camarri and J. Pitman. Limit distributions and random trees derived from the birthday problem with unequal probabilities. Electron. J. Probab., 5:Paper 2, 1–18, 2000.

[25] A. Cayley. A theorem on trees. Quarterly Journal of Pure and Applied Mathematics, 23:376–378, 1889. (Also in The Collected Mathematical Papers of Arthur Cayley. Vol XIII, 26-28, Cambridge University Press, 1897).

[26] Ch. A. Charalambides. Abel series distributions with applications to fluctuations of sample functions of stochastic processes. Communications in Statistics, Part A–Theory and Methods, 19:317–335, 1990.

[27] L. Comtet. Advanced Combinatorics. D. Reidel Pub. Co., Boston, 1974. (translated from French).

[28] P. C. Consul. On some properties and applications of quasi-binomial distribution. Communications in Statistics, Part A–Theory and Methods, 19:607, 1990.

[29] P. C. Consul and S. P. Mittal. A new urn model with predetermined strategy. Biometrical Journal. Journal of Mathematical Methods in Biosciences., 17:67 – 76, 1975.

[30] P.C. Consul. A simple urn model dependent upon a predetermined strategy. Sankhya Ser. B, 36:391–399, 1974.

[31] C. C. Y. Dorea. Connectivity of random graphs. J. Appl. Probab., 19:880 – 884, 1982.

[32] M. Drmota and B. Gittenberger. Strata of random mappings—a combinatorial approach. Stochastic Process. Appl., 82(2):157–171, 1999.

[33] S.N. Evans and J. Pitman. Construction of Markovian coalescents. Ann. Inst. Henri Poincaré, 34:339–383, 1998.

[34] W. Feller. An Introduction to Probability Theory and its Applications, Vol 1, 3rd ed. Wiley, New York, 1968.

[35] D. Foata and A. Fuchs. Réarrangements de fonctions et dénombrement. J. Comb. Theory, 8:361–375, 1970.

[36] J. Françon. Preuves combinatoires des identités d’Abel. Discrete Mathematics, 8:331–343, 1974.

[37] I. Gessel. Letter to the editor: “Trees and power-sums” [Amer. Math. Monthly 92 (1985), no. 5, 328–331; MR 87e:05016a] by A. H. Stone. Amer. Math. Monthly, 93(4):323–324, 1986.

[38] H.W. Gould. Combinatorial Identities: A standardized set of tables listing 500 binomial coefficient summations. West Virginia University, Morgantown, W. Va., 1972.

[39] W. Gutjahr. Connection reliabilities in stochastic acyclic networks. Random Structures and Algorithms, 5:57–72, 1994.

[40] J. Hansen and J. Jaworski. Large components of bipartite random mappings. In Proceedings of the Ninth International Conference “Random Structures and Algorithms” (Poznan, 1999), volume 17, pages 317–342, 2000.

[41] B. Harris. A survey of the early history of the theory of random mappings. In Probabilistic methods in discrete mathematics (Petrozavodsk, 1992), pages 1–22. VSP, Utrecht, 1993.

[42] A. Hurwitz. Über Riemann’sche Flächen mit gegebenen Verzweigungspunkten. Math. Annalen, 39:1–66, 1891.

[43] A. Hurwitz. Über Abel’s Verallgemeinerung der binomischen Formel. Acta Math., 26:199–203, 1902.

[44] J. Jaworski. A random bipartite mapping. Ann. Discrete Math., 28:137– 158, 1985.

[45] J. Jaworski. Random mappings with independent choices of images. In J. Jaworski M. Karoński and A. Ruciński, editors, Random graphs ’87, pages 89–101, Chichester, 1990. Wiley.

[46] J. Jaworski. Epidemic processes on digraphs of random mappings. J. Appl. Probab., 36(3):780–798, 1999.

[47] J.L.W. Jensen. Sur une identité d’abel et sur autres formules analogues. Acta Math., 26:307–318, 1902.

[48] J.Jaworski. On a random mapping (T, P_{j}). J. Appl. Probab., 21:186 – 191, 1984.

[49] A. Joyal. Une théorie combinatoire des séries formelles. Adv. in Math., 42:1–82, 1981.

[50] I.B. Kalugin. A class of random mappings. Proc. Steklov Inst. Math., 177:79–110, 1986.

[51] L. Katz. Probability of indecomposability of a random mapping function. Ann. Math. Statist., 26:512–517, 1955.

[52] A. Kelmans, I. Pak, and A. Postnikov. Tree and forest volumes of graphs. Technical Report 47-99, RUTCOR, 1999.

[53] A. Kelmans and A. Postnikov. On generalizations of Abel’s and Hurwitz’s identities. Technical Report 48-99, RUTCOR, 1999.

[54] A. K. Kelmans. Spanning trees of extended graphs. Combinatorica, 12(1):45–51, 1992.

[55] D.E. Knuth. Discussion on Mr. Riordan’s paper. In R.C. Bose and T.A. Dowling, editors, Combinatorial Mathematics and its Applications, pages 91–97. Univ. of North Carolina Press, Chapel Hill, 1969.

[56] V.F. Kolchin. Random Mappings. Optimization Software, New York, 1986. (Translation of Russian original).

[57] T. Łuczak and B. Pittel. Components of random forests. Combinatorics, Probability and Computing, 1:35–52, 1992.

[58] R. Lyons and Y. Peres. Probability on trees and networks. Book in preparation, available at http://www.ma.huji.ac.il/ lyons/prbtree.html, 1996.

[59] J.A. Mann, B. Pittel, and W. A. Woycznski. Random tree-type partitions as a model for acyclic polymerization: Holtsmark (3/2 stable) distribution of the supercritical gel. Ann. Probab., 18:319–341, 1990.

[60] J. W. Moon. Enumerating labelled trees. In F. Harary, editor, Graph Theory and Theoretical Physics, pages 261–272. Academic Press, 1967.

[61] J. W. Moon. Two problems on random trees. In Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), pages 197–206. Lecture Notes in Math., Vol. 303. Springer, Berlin, 1972.

[62] J.W. Moon. Counting Labelled Trees. Canadian Mathematical Congress, 1970. Canadian Mathematical Monographs No. 1.

[63] L.R. Mutafchiev. On random mappings with a single attracting centre. J. Appl. Probab., 24:258 – 264, 1987.

[64] L. Mutafciev. Probability distributions and asymptotics for some characteristics of random mappings. In W. Grossman et al., editor, Proc. 4th Pannonian Symp. on Math. Statist., pages 227–238, 1983.

[65] C. A. O’Cinneide and A. V. Pokrovskii. Nonuniform random transformations. Ann. Appl. Probab., 10(4):1151–1181, 2000.

[66] R. Pemantle. Uniform random spanning trees. In J. L. Snell, editor, Topics in Contemporary Probability, pages 1–54, Boca Raton, FL, 1995. CRC Press.

[67] J. Pitman. Probability. Springer-Verlag, New York, 1993.

[68] J. Pitman. The multinomial distribution on rooted labeled forests. Technical Report 499, Dept. Statistics, U.C. Berkeley, 1997. Available via www.stat.berkeley.edu/users/pitman.

[69] J. Pitman. Enumerations of trees and forests related to branching processes and random walks. In D. Aldous and J. Propp, editors, Microsurveys in Discrete Probability, number 41 in DIMACS Ser. Discrete Math. Theoret. Comp. Sci, pages 163–180, Providence RI, 1998. Amer. Math. Soc.

[70] J. Pitman. Coalescent random forests. J. Comb. Theory A., 85:165–193, 1999.

[71] J. Pitman. The SDE solved by local times of a Brownian excursion or bridge derived from the height profile of a random tree or forest. Ann. Probab., 27:261–283, 1999.

[72] J. Pitman. Forest volume decompositions and Abel-Cayley-Hurwitz multinomial expansions. Technical Report 591, Dept. Statistics, U.C. Berkeley, 2001. To appear in J. Comb. Theory A. Available via www.stat.berkeley.edu/users/pitman.

[73] B. Pittel. On distributions related to transitive closures of random finite mappings. The Annals of Probability, 11:428 – 441, 1983.

[74] G. V. Proskurin. Limit distributions of the number of cyclic points of a stable random mapping. Diskret. Mat., 6(2):74–87, 1994.

[75] H. Prüfer. Neuer Beweis eines Satzes über Permutationen. Archiv für Mathematik und Physik, 27:142–144, 1918.

[76] A. Rényi. On the enumeration of trees. In R. Guy, H. Hanani, N. Sauer, and J. Schonheim, editors, Combinatorial Structures and their Applications, pages 355–360. Gordon and Breach, New York, 1970.

[77] J. Riordan. Combinatorial Identities. Wiley, New York, 1968.

[78] S. M. Ross. A random graph. J. Appl. Probab., 18:309–315, 1981.

[79] G.-C. Rota and R. Mullin. On the foundation of combinatorial theory III: Theory of binomial enumeration. In B. Harris, editor, Graph Theory and its Applications, pages 167–213. Academic Press, New York, 1970.

[80] L.W. Shapiro. Voting blocks, reluctant functions, and a formula of Hurwitz. Discrete Mathematics, 87:319–322, 1991.

[81] R. Stanley. Enumerative Combinatorics, Vol. 1. Cambridge University Press, 1997.

[82] R. Stanley. Enumerative Combinatorics, Vol. 2. Cambridge University Press, 1999.

[83] V.E. Stepanov. Random mappings with a single attracting center. Theory Probab. Appl., 16:155–162, 1971.

[84] A. H. Stone. Trees and power-sums. Amer. Math. Monthly, 92(5):328– 331, 1985.

[85] V. Strehl. Identities of the Rothe-Abel-Schläfli-Hurwitz-type. Discrete Math., 99:321–340, 1992.

[86] V. Strehl. Minimal transitive products of transpositions: the reconstruction of a proof of A. Hurwitz. Séminaire Lotharingien de Combinatoire, B37c: 12 pp., 1996. Available at http://cartan.u-strasbg.fr/∼slc.

[87] J. Zeng. Multinomial convolution polynomials. Discrete Math., 160:219– 228, 1996.