2.1. Tree evolution processes

In [Reference Mahmoud and Smythe18] a stochastic growth rule for bucket recursive trees has been given, generalising the rule for ordinary random recursive trees (which are the special instance $b=1$ ): a bucket tree grows by progressive attraction of increasing integer labels: when inserting element $n+1$ into an existing bucket recursive tree containing n elements (i.e., containing the labels $\{1, 2, \dots, n\}$ ) all n existing elements in the tree compete to attract the element $n+1$ , where all existing elements have equal chance to recruit the new element. If the element winning this competition is contained in a node with less than b elements (an unsaturated bucket or node), element $n+1$ is added to this node, otherwise if the winning element is contained in a node with already b elements (a saturated bucket or node), element $n+1$ is attached to this node as a new bucket containing only the element $n+1$ . Starting with a single bucket as root node containing only element 1 leads after $n-1$ insertion steps, where the labels $2, 3, \dots, n$ are successively inserted according to this growth rule, to a so called random bucket recursive tree with n elements and maximal bucket size b. Of course, the above growth rule for inserting the element $n+1$ could also be formulated by saying that, for an existing bucket recursive tree T with n elements, the probability that a certain node $v \in T$ attracts the new element $n+1$ is proportional to the number of elements contained in v, let us say k with $1 \le k \le b$ , and is thus given by $\frac{k}{n}$ . Summarising this procedure we obtain the following definition.

Definition 1 (Bucket recursive trees). We start with a single bucket as root node containing only label 1. Given a tree T of size $n\ge 1$ . Let $p(v)={\mathbb{P}}(n+1 <_t v \mid c(v)\}$ denote the probability that node $v\in {T}$ attracts label $n+1$ conditioned on its capacity c(v). The family of random bucket recursive trees is generated according to the probabilities

\[ p(v) = \frac{c(v)}{n},\]

with capacity $1\le c(v)\le b$ , thus independent of the out-degree $\text{deg}^{+}(v)\ge 0$ of node v.

Note that here and throughout this work the capacities $c(v)=c_n(v)$ and the out-degree $\text{deg}^{+}(v)=\text{deg}^{+}_n(v)$ of a node v in a tree T are always dependent on the size $|T|=n$ .

In the following we present two new stochastic growth rules. They generate families of random bucket increasing trees with bucket size $b\ge 1$ . Concerning the created trees, they are by definition unordered. For both rules there is an additional dependence on the out-degree $\text{deg}^{+}(v)$ of the nodes.

The family of random (b,d)-ary increasing trees, with $d\in\mathbb{Q}$ such that $(d-1)b\in\mathbb{N}$ , is generated according to the probabilities

\[ p(v) =\displaystyle{ \frac{(d-1)c(v)+1-\text{deg}^{+}(v)}{(d-1)n+1}},\]

with $1\le c(v)\le b$ and $\text{deg}^{+}(v)\ge 0$ .

Definition 3 ( $(\mathrm{b},\alpha)$ -plane oriented recursive trees). We start, case $n=1$ , with a single bucket as root node containing only label 1. Given a tree T of size $n\ge 1$ . The family of random (b, $\alpha$ )-plane oriented recursive trees, with $\alpha>0$ , is generated according to the probabilities p(v) that node $v\in T$ attracts label $n+1$ :

\[ p(v) = \displaystyle{ \frac{\text{deg}^{+}(v)+(\alpha+1)c(v)-1}{(\alpha+1)n-1}},\]

with $1\le c(v)\le b$ and $\text{deg}^{+}(v)\ge 0$ .

In the spirit of Pittel, we can define linear bucket increasing trees as follows. Given a tree T of size $n\ge 1$ , a label $n+1$ is attracted by a node $v\in T$ that is chosen with probability proportional to

\[\alpha\cdot (c(v)-1)+\beta\cdot\text{deg}^{+}(v)+m,\]

with $1\le c(v)\le b$ and $\text{deg}^{+}(v)\ge 0$ . Here $\alpha,\beta,m\in{\mathbb{R}}$ denote real parameters such that the sum is non-negative. For $b=1$ we have $c(v)=1$ and we reobtain Pittel’s linear increasing trees.

2.2 Combinatorial description of bucket increasing tree families

Our basic objects are rooted ordered trees $T\in\mathcal{B}$ . Here, the order of the subtrees of a node is of relevance. The nodes of the trees are buckets with an integer capacity c, with $1 \le c \le b$ for a given maximal integer bucket size $b \ge 1$ . We assume that all internal nodes (i.e., non-leaves) in the tree must be saturated, while the leaves might be either saturated or unsaturated. Here $\mathcal{B}$ denotes the family of all bucket ordered trees with maximal bucket size b. A tree T defined in this way is called a bucket ordered tree with maximal bucket size b. As already mentioned we define for bucket ordered trees the size $|T|$ of a tree T via $|T| = \sum_{v} c(v)$ , where c(v) ranges over all vertices of T. An increasing labelling $\ell(T)$ of a bucket ordered tree T is then a labelling of T, where the labels $\{1, 2,\dots, |T|\}$ are distributed amongst the nodes of T, such that the following conditions are satisfied: (i) every node v contains exactly c(v) labels, (ii) the labels within a node are arranged in increasing order, (iii) each sequence of labels along any path starting at the root is increasing. A bucket ordered increasing tree $\tilde{T}$ is given by a pair $\tilde{T}=(T,\ell(T))$ .

Then a class $\mathcal{T}$ of a family of bucket increasing trees with maximal bucket size b can be defined in the following way. A sequence of non-negative numbers $(\varphi_{k})_{k \ge 0}$ with $\varphi_{0} > 0$ and a sequence of non-negative numbers $\psi_{1}, \psi_{2}, \dots, \psi_{b-1}$ is used to define the weight w(T) of any bucket ordered tree T by $w(T) \,:\!=\, \prod_{v} w(v)$ , where v ranges over all vertices of T. The weight w(v) of a node v is given as follows, where $\text{deg}^{+}(v)$ denotes the out-degree (i.e., the number of children) of node v:

\begin{equation*} w(v) = \begin{cases} \varphi_{\text{deg}^{+}(v)}, & \quad \text{if} \enspace c(v)=b, \\ \psi_{c(v)}, & \quad \text{if} \enspace c(v) < b. \end{cases}\end{equation*}

Thus, for saturated nodes the weight depends on the out-degree $\text{deg}^{+}(v)$ and is described by the sequence $\varphi_{k}$ , whereas for unsaturated nodes the weight depends on the capacity c(v) and is described by the sequence $\psi_{k}$ .

Furthermore, $\mathcal{L}(T)$ denotes the set of different increasing labellings $\ell(T)$ of the tree T with distinct integers $\{1, 2, \dots, |T|\}$ , where $L(T) \,:\!=\, \big|\mathcal{L}(T)\big|$ denotes its cardinality. The family $\mathcal{T}$ consists of all trees $\tilde{T}=(T,\ell(T))$ , with their weights w(T) and the set of increasing labellings $\mathcal{L}(T)$ and we define $w(\tilde{T})\,:\!=\,w(T)$ . Concerning bucket ordered increasing trees, note that the left-to-right order of the subtrees of the nodes is relevant. E.g., the trees and are forming two different trees.

For a given degree-weight sequence $(\varphi_{k})_{k \ge 0}$ with a degree-weight generating function $\varphi(t) \,:\!=\, \sum_{k \ge 0} \varphi_{k} t^{k}$ and a bucket-weight sequence $\psi_{1}, \dots, \psi_{b-1}$ , we define now the total weights $T_n$ by

\[T_{n} \,:\!=\, \sum_{T\in\mathcal{B}\colon |T|=n}w(T)\cdot L(T)=\sum_{\tilde{T}=(T,\ell(T))\in\mathcal{T}\colon |T|=n} w(\tilde{T}).\]

It is advantageous for such enumeration problems to describe a family of increasing trees $\mathcal{T}$ by the following formal recursive equation:

where denotes a bucket of capacity k labelled by $1, 2, \dots, k$ , $\times$ the cartesian product, $\ast$ the partition product for labelled objects, and $\varphi(\mathcal{T})$ the substituted structure. On the other hand, we can use standard notation [Reference Flajolet and Segdewick6]. Let $\mathcal{Z}$ denote the atomic class (i.e., a single (uni)labelled node), $\mathcal{A}^{\Box} \ast \mathcal{B}$ the boxed product (i.e., the smallest label is constrained to lie in the $\mathcal{A}$ component) of the combinatorial classes $\mathcal{A}$ and $\mathcal{B}$ . Then,

\begin{align*} \mathcal{T} & = \psi_1\cdot \mathcal{Z}^{\Box} + \psi_2\cdot \left(\mathcal{Z}^{\Box}\right)^2+ \dots+ \psi_{b-1}\cdot \left(\mathcal{Z}^{\Box}\right)^{b-1} + \left(\mathcal{Z}^{\Box}\right)^{b}\ast \varphi(\mathcal{T})\\ & = \sum_{k=1}^{b-1}\psi_{k}\cdot \left(\mathcal{Z}^{\Box}\right)^{k} + \left(\mathcal{Z}^{\Box}\right)^{b}\ast \varphi(\mathcal{T}).\end{align*}

Here the meaning of $(\mathcal{Z}^{\Box})^{k} \ast \mathcal{B}$ is $\mathcal{Z}^{\Box} \ast \big(\mathcal{Z}^{\Box} \ast \big(\cdots \ast \big(\mathcal{Z}^{\Box} \ast \mathcal{B}\big)\big)\big)$ , with k occurrences of $\mathcal{Z}^{\Box}$ .

Using above formal description, one can show that the exponential generating function $T(z) \,:\!=\, \sum_{n \ge 1} T_{n} \frac{z^{n}}{n!}$ of the total weights $T_{n}$ is characterised by the following result of [Reference Kuba and Panholzer13].

Proposition 6. The exponential generating function T(z) of bucket increasing trees with degree-weight generating function $\varphi(t)$ satisfies an ordinary differential equation of order b:

(2) \begin{align} \frac{d^{b}}{d z^{b}} T(z) & = \varphi\big(T(z)\big),\end{align}

with initial conditions

\[ T(0)=0, \qquad T^{(k)}(0) = \psi_{k}, \quad \text{for} \enspace 1 \le k \le b-1.\]

Example 7 (Bucket size one – ordinary increasing trees). In the case of bucket size $b=1$ we obtain ordinary increasing trees. We have a simple description using the boxed product:

(3) \begin{equation} \mathcal{T} = \mathcal{Z}^{\Box}\ast \varphi\big(\mathcal{T}\big).\end{equation}

The exponential generating function T(z) of bucket increasing trees with degree-weight generating function $\varphi(t)$ is implicitly defined by

\[\int_0^{T(z)}\frac{dt}{\varphi(t)} = z.\]

Prominent varieties include recursive trees, binary increasing and plane-oriented recursive trees; for an overview see, e.g., [Reference Drmota5, Reference Flajolet and Segdewick6].

Example 8 (Bucket size two – bilabelled trees). Trees with bucket size $b=2$ , degree-weight generating function $\varphi(t)$ and weight $\psi=\psi_1\ge 0$ correspond to so-called bilabelled trees. The family $\widehat{\mathcal{T}}$ can be described by the following symbolic equation:

(4) \begin{equation} \mathcal{T} = \mathcal{Z}^{\Box} \ast \left(\mathcal{Z}^{\Box} \ast \varphi\big(\mathcal{T}\big)\right),\end{equation}

The differential equation $T''(z)=\varphi(T(z))$ can be readily translated to a first-order equation. Namely, multiplication with $T^{\prime}(z)$ and integration leads to the first-order differential equation

(5) \begin{equation} T'(z) = \sqrt{\psi^2+2\cdot\Phi(T(z))}, \quad T(0)=0,\end{equation}

with $\Phi(x)=\int_{0}^{x} \varphi(t)dt$ . Hence, $T=T(z)$ is implicitly given via

\[\int_{0}^{T}\frac{dx}{\sqrt{\psi^2+2\cdot\Phi(x)}}=z.\]

The special choice $\psi=0$ leads to so-called strict bilabelled increasing tree families. Here, due to the choice $\psi=0$ , all nodes have to be saturated. Such tree families naturally give rise to hook-length formulas; see [Reference Kuba and Panholzer15] for many examples.

3.1 Random tree models

For each class $\mathcal{T}$ of bucket increasing trees associated to a given degree-weight sequence $(\varphi_{k})_{k \ge 0}$ and bucket-weight sequence $\psi_{1}, \dots, \psi_{b-1}$ we define in a natural way probability models for random (ordered) bucket increasing trees $\mathcal{T}_n$ of size n. We assume that each increasingly labelled bucket ordered increasing tree $\tilde{T} = \big(T,\ell(T)\big)\in\mathcal{T}_n$ of size n is chosen with a probability proportional to its weight $w(\tilde{T})$ .

Definition 10 (Random bucket ordered increasing trees). A probability measure on ordered bucket increasing trees $\tilde{T}\in\mathcal{T}_n$ of size n is defined by

\begin{equation*} {\mathbb{P}}{^{[\mathcal{T}]}}\big(\big\{\tilde{T}\big\}\big) = \frac{w\left(\tilde{T}\right)}{T_{n}} =\frac{\displaystyle{\left(\prod_{v\in \tilde{T}\colon c(v)<b} \psi_{c(v)} \right) \cdot \left(\prod_{v\in \tilde{T}\colon c(v)=b}\varphi_{\text{deg}^{+}(v)}\right)}}{T_{n}}.\end{equation*}

We speak then about random ordered bucket increasing trees of size n of the family $\mathcal{T}$ under the random tree model.

From a combinatorial point of view it is often convenient to work with ordered trees. However, the trees generated by the tree evolution processes are by definition unordered. Thus, we turn our attention to unordered trees. Our basic objects are unordered bucket trees $T{^{[U]}}$ together with an increasing labelling $\ell\big(T{^{[U]}}\big)$ . In order to obtain a measure on unordered bucket increasing trees $\mathcal{T}{^{[U]}}$ we proceed in a standard way embedding unordered trees into ordered trees. Each unordered bucket increasing tree $\tilde{T}{^{[U]}} =\big(T{^{[U]}},\ell\big(T{^{[U]}}\big)\big)$ corresponds to

\[\prod_{v\in T{^{[U]}}}\text{deg}^{+}(v)!\]

different ordered bucket increasing trees. We obtain a canonical ordered representative $\tilde{T}\in\mathcal{T}$ of the unordered tree $\tilde{T}{^{[U]}}=\big(T{^{[U]}},\ell\big(T{^{[U]}}\big)\big)$ by ordering the subtrees of each node $v\in\tilde{T}{^{[U]}}$ in an increasing left-to-right way according to the smallest labels contained in the respective subtrees taking into account the labelling $\ell\big(T{^{[U]}}\big)$ . Let $f\colon \mathcal{T}{^{[U]}}\to \mathcal{T}$ denote this injective ordering map.

Definition 11 (Random unordered bucket increasing trees). A probability measure ${\mathbb{P}}{^{[\mathcal{T}]}}$ on unordered bucket increasing trees $\tilde{T}{^{[U]}}\in\mathcal{T}{^{[U]}}_{n}$ of size n is defined by

\begin{equation*} {\mathbb{P}}{^{[\mathcal{T}]}}\big\{\tilde{T}{^{[U]}}\big\} = \frac{(w\circ f)\left(\tilde{T}{^{[U]}}\right) \cdot \prod_{v\in T{^{[U]}}}\text{deg}^{+}(v)! }{T_{n}}.\end{equation*}

We speak then about random unordered bucket increasing trees of size n of the family $\mathcal{T}{^{[U]}}$ under the random tree model.

Possibly different models of randomness are introduced when generating an unordered tree of size n according to one of the three tree evolution processes described before. Given an integer $j\ge 2$ and any tree $\tilde{T}{^{[U]}}=\big(T{^{[U]}},\ell\big(T{^{[U]}}\big)\big)$ , we denote by $\text{attr}(j)$ the node in $\tilde{T}{^{[U]}}$ that attracted label j, and by $\tilde{T}_{< j}{^{[U]}}$ the tree obtained from $\tilde{T}{^{[U]}}$ when restricting to labels less than j. Then we define $\pi^{(j)}$ as the map $\pi^{(j)}\colon \tilde{T}{^{[U]}} \to [0,1]$ that gives the probability that label j will be attracted by node $\text{attr}(j)$ in $\tilde{T}_{< j}{^{[U]}}$ :

\[\pi^{(j)}(\tilde{T}{^{[U]}})=\begin{cases}{\mathbb{P}}\big\{j<_t \text{attr}(j) \: \big| \: \tilde{T}_{< j} {^{[U]}}\big\},\qquad |\tilde{T}{^{[U]}}|\ge j,\\[6pt]0, \qquad |\tilde{T}{^{[U]}}|<j,\end{cases}\]

with ${\mathbb{P}}\big\{j<_t \text{attr}(j) \: \big| \: \tilde{T}_{< j}{^{[U]}}\big\}$ being determined by the tree evolution processes.

The point-wise product ${\mathbb{P}}^{[e]}=\prod_{j=2}^{n}\pi^{(j)}$ is then a probability measure on unordered bucket increasing trees $\mathcal{T}_{n}{^{[U]}}$ of size n. In the following we denote with a superscript the source of randomness on $\mathcal{T}_n$ : ${\mathbb{P}}{^{[\mathcal{T}]}}$ for the random tree model and ${\mathbb{P}}{^{[e]}}$ for the tree evolution process. It holds

\[{\mathbb{P}}{^{[e]}}\left\{\tilde{T}{^{[U]}}\right\}=\prod_{j=2}^{n}\pi^{(j)}\left(\tilde{T}{^{[U]}}\right).\]

Let $\text{deg}^{+}_{< j}(v)$ be the out-degree of node v when restricting to labels less than j. Then, a probability measure on ordered trees is obtained via

\[{\mathbb{P}}{^{[e]}}\{\tilde{T}\}=\prod_{j=2}^{n}\frac{\pi^{(j)}\left(\tilde{T}{^{[U]}}\right)}{\text{deg}^{+}_{< j}(\text{attr}(j))}.\]

3.2 Combinatorial models

It was already proven in [Reference Kuba and Panholzer13] that bucket recursive trees generated according to the growth process as stated in Subsection 2.1 can be considered as a certain bucket increasing tree family. In the following we extend this result, where, for the sake of completeness, we also collect the findings of [Reference Kuba and Panholzer13] for bucket recursive trees.

Consequently, both models of randomness for (un)ordered trees coincide: ${\mathbb{P}}{^{[e]}}={\mathbb{P}}{^{[\mathcal{T}]}}$ .

1. 1. Bucket recursive trees: a combinatorial model can be obtained from the sequences

   \begin{equation*} \varphi_{k} = \frac{(b-1)! b^{k}}{k!}, \quad \text{for} \enspace k \ge 0, \qquad \psi_{k} = (k-1)!, \quad \text{for} \enspace 1 \le k \le b-1,\end{equation*}
   such that $\varphi(t)=\sum_{k\ge 0}\varphi_k t^k=(b-1)! \cdot \exp(b t)$ . For this model of bucket recursive trees the exponential generating function T(z) and the total weights $T_n$ are given by
   \begin{equation*}T(z)=\log\left(\frac{1}{1-z}\right),\quad T_n=(n-1)!.\end{equation*}

2. 2. (b,d)-ary increasing trees: a combinatorial model can be obtained from the sequences

   \begin{equation*}\begin{split} \varphi_{k} &= (b-1)!(d-1)^{b-1}\binom{b-1+\frac{1}{d-1}}{b-1}\binom{b(d-1)+1}{k}, \quad \text{for} \enspace k \ge 0,\\ \psi_{k} &= (k-1)!(d-1)^{k-1}\binom{k-1+\frac{1}{d-1}}{k-1}, \quad \text{for} \enspace 1 \le k \le b-1,\end{split}\end{equation*}
   such that $\varphi(t)= (b-1)!(d-1)^{b-1}\binom{b-1+\frac{1}{d-1}}{b-1}(1+t)^{b(d-1)+1}$ . For this model of (b,d)-ary increasing trees the exponential generating function T(z) and the total weights $T_n=[z^n]T(z)$ are given by
   \begin{equation*} T(z)=\frac{1}{(1-(d-1)z)^{\frac1{d-1}}}-1,\quad T_n=(n-1)!(d-1)^{n-1}\binom{n-1+\frac{1}{d-1}}{n-1}.\end{equation*}

3. 3. $(\mathrm{b},\alpha)$ -plane oriented recursive trees: a combinatorial model can be obtained from the sequences

   \begin{equation*}\begin{split} \varphi_{k} &=(b-1)!(\alpha+1)^{b-1}\binom{b-1-\frac{1}{\alpha+1}}{b-1}\binom{(\alpha+1)b-2+k}{k}, \quad \text{for} \enspace k \ge 0,\\ \psi_{k} &= (k-1)!(\alpha+1)^{k-1}\binom{k-1-\frac{1}{\alpha+1}}{k-1}, \quad \text{for} \enspace 1 \le k \le b-1,\end{split}\end{equation*}
   such that $\varphi(t)=\frac{(b-1)!(\alpha+1)^{b-1}\binom{b-1-\frac{1}{\alpha+1}}{b-1}}{(1-t)^{(\alpha+1)b-1}}$ . For this model of $(\mathrm{b},\alpha)$ -plane oriented recursive trees the exponential generating function T(z) and the total weights $T_n=[z^n]T(z)$ are given by
   \begin{equation*}T(z)=1-(1-(\alpha+1)z)^{\frac1{\alpha+1}},\quad T_n=(n-1)!(\alpha+1)^{n-1}\binom{n-1-\frac{1}{\alpha+1}}{n-1}.\end{equation*}

Proof. To prove that these choices of sequences $(\varphi_k)_{k\in{\mathbb{N}}}$ and $(\psi_k)_{1\le k\le b-1}$ are actually models for bucket increasing trees generated according to the stochastic growth rules defined in Subsection 2.1, we have to show that the combinatorial families $\mathcal{T}$ of bucket increasing trees have the same stochastic growth rules as the counterparts created probabilistically. Given an arbitrary bucket increasing tree $T \in \mathcal{T}$ of size $|T|=n$ , then the probability that a new element $n+1$ is attracted by a node $v \in T$ with capacity $c(v)=k$ has to coincide with the corresponding probability stated in Definitions 1–3.

We use now the notation $T \to T'$ to denote that $ T^{\prime}$ is obtained from T with $|T|=n$ by incorporating element $n+1$ , i.e., either by attaching element $n+1$ to a saturated node $v \in T$ at one of the $\text{deg}^{+}(v)+1$ possible positions (recall that bucket increasing trees are per definition ordered trees and thus the order of the subtrees is of relevance) by creating a new bucket of capacity 1 containing element $n+1$ or by adding element $n+1$ to an unsaturated node $v \in T$ by increasing the capacity of v by 1. If we want to express that node $v \in T$ has attracted the element $n+1$ leading from T to $ T^{\prime}$ we use the notation $T \xrightarrow{v} T'$ . If there exists a stochastic growth rule for a bucket increasing tree family $\mathcal{T}$ , then it must hold that for a given tree $T \in \mathcal{T}$ of size $|T|=n$ and a given node $v \in T$ the probability $p_{T}(v)$ , which gives the probability that element $n+1$ is attracted by node $v \in T$ , is given as follows:

(6) \begin{equation} p_{T}(v) = \frac{\sum_{T' \in \mathcal{T} : T \xrightarrow{v} T'} w(T')}{\sum_{\tilde{T} \in \mathcal{T} : T \to \tilde{T}} w(\tilde{T})} = \frac{\sum_{T' \in \mathcal{T} : T \xrightarrow{v} T'} \frac{w\left(T'\right)}{w(T)}}{\sum_{\tilde{T} \in \mathcal{T} : T \to \tilde{T}} \frac{w(\tilde{T})}{w(T)}}.\end{equation}

The remaining task is to simplify the expression above into the form stated in Definitions 1–3. For a certain tree $\tilde{T}$ with $T \xrightarrow{u} \tilde{T}$ and $u \in T$ the quotient of the weight of the trees $\tilde{T}$ and T is due to the definition of bucket increasing trees given as follows, where we define for simplicity $\psi_{b} \,:\!=\, \varphi_{0}$ :

\begin{equation*} \frac{w(\tilde{T})}{w(T)} = \begin{cases} \psi_{1} \frac{\varphi_{k+1}}{\varphi_{k}}, & \quad \text{for} \enspace c(u)=b \quad \text{and} \quad \text{deg}^{+}(u)=k, \\[5pt] \frac{\psi_{k+1}}{\psi_{k}}, & \quad \text{for} \enspace c(u)=k < b. \end{cases}\end{equation*}

For a given tree $T \in \mathcal{T}$ we define by $m_{k} \,:\!=\, |\{u \in T : c(u)=k<b\}|$ the number of unsaturated nodes of T with capacity $k<b$ and by $n_{k} \,:\!=\, |\{u \in T : c(u)=b \enspace \text{and} \enspace \text{deg}^{+}(u)=k\}|$ the number of saturated nodes of T with out-degree $k \ge 0$ . It holds then

(7) \begin{equation} n = \sum_{u \in T} c(u) = \sum_{k=1}^{b-1} k m_{k} + b \sum_{k \ge 0} n_{k}\end{equation}

and (where we use that there are $k+1$ possibilities of attaching a new node to a saturated node $u \in T$ with out-degree $\text{deg}^{+}(u)=k$ ):

\begin{equation*} \sum_{\tilde{T} \in \mathcal{T} : T \to \tilde{T}} \frac{w(\tilde{T})}{w(T)} = \sum_{k=1}^{b-1} m_{k} \frac{\psi_{k+1}}{\psi_{k}} + \sum_{k \ge 0} n_{k} (k+1) \psi_{1} \frac{\varphi_{k+1}}{\varphi_{k}}.\end{equation*}

Moreover, we also have the relation

(8) \begin{equation} 1 = \sum_{k=1}^{b-1} m_{k} - \sum_{k \ge 0} (k-1)n_{k},\end{equation}

which follows as the difference between the node-sum and edge-sum equation for the tree T:

\begin{equation*}\text{$\#$ nodes} = \sum_{k=1}^{b-1} m_{k} + \sum_{k \ge 0} n_{k}, \qquad \text{$\#$ edges} = \text{$\#$ nodes} - 1 = \sum_{k \ge 0} k n_{k}.\end{equation*}

First we turn our attention to the family of (b,d)-ary increasing trees and the weights as given in Theorem 12. We have

\begin{equation*} \sum_{T' \in \mathcal{T} : T \xrightarrow{v} T'} \frac{w(T')}{w(T)} = \begin{cases} (k+1) \psi_{1} \frac{\varphi_{k+1}}{\varphi_{k}} = b(d-1)+1-k, & \quad \text{for} \enspace c(v)=b \quad \text{and} \quad \text{deg}^+(v)=k, \\[12pt] \frac{\psi_{k+1}}{\psi_{k}} = k(d-1)+1, & \quad \text{for} \enspace c(v)=k < b, \end{cases}\end{equation*}

and consequently

\begin{equation*}\begin{split} \sum_{\tilde{T} \in \mathcal{T} : T \to \tilde{T}} \frac{w(\tilde{T})}{w(T)} &= \sum_{k=1}^{b-1} (k(d-1)+1) m_{k} + \sum_{k \ge 0} n_{k} (b(d-1)+1-k)\\ &= (d-1)\left(\sum_{k=1}^{b-1} k m_{k} + b \sum_{k \ge 0} n_{k}\right) + \sum_{k=1}^{b-1} m_{k} - \sum_{k \ge 0} (k-1)n_{k} =(d-1)n+1,\end{split}\end{equation*}

due to equations (7) and (8). Thus, with this choice of weight sequences $(\varphi_k)_k$ and $(\psi_k)_k$ , the probability $p_{T}(v)$ that in a bucket increasing tree T of size $|T|=n$ the node v with capacity $c(v)=k$ attracts element $n+1$ coincides with the corresponding probability of the stochastic growth rule for (b,d)-ary increasing trees given in Definition 2.

We obtain then from equation (2) that the exponential generating function $T(z)\,:\!=\,\sum_{n\ge 1}T_n\frac{z^{n}}{n!}$ of the total-weight $T_{n}$ of bucket increasing trees of size n satisfies the differential equation

(9) \begin{equation} \frac{d^b}{dz^b}T(z)=(b-1)!(d-1)^{b-1}\binom{b-1+\frac{1}{d-1}}{b-1} (1+T(z))^{b(d-1)+1},\end{equation}

with initial conditions $T(0)=0$ and $\left.\frac{d^k}{dz^k}T(z)\right|_{z=0}\!=(k-1)!(d-1)^{k-1}\binom{k-1+\frac{1}{d-1}}{k-1}$ , for $1\le k \le b-1$ . The solution of this equation is given by

(10) \begin{equation} T(z)=\frac{1}{(1-(d-1)z)^{\frac1{d-1}}}-1=\sum_{n\ge 1}(n-1)!(d-1)^{n-1}\binom{n-1+\frac{1}{d-1}}{n-1} \frac{z^{n}}{n!},\end{equation}

as can be checked easily Hence the total weight of all size n (b,d)-ary increasing trees is given by $T_n=(n-1)!(d-1)^{n-1}\binom{n-1+\frac{1}{d-1}}{n-1}$ as stated in Theorem 12.

For $(\mathrm{b},\alpha)$ -plane oriented recursive trees and weights as given in Theorem 12 we obtain

\begin{equation*} \sum_{T' \in \mathcal{T} : T \xrightarrow{v} T'} \frac{w(T')}{w(T)} = \begin{cases} (k+1) \psi_{1} \frac{\varphi_{k+1}}{\varphi_{k}} = (\alpha+1)b-1+k, & \quad \text{for} \enspace c(v)=b \quad \text{and} \quad \text{deg}^+(v)=k, \\ \frac{\psi_{k+1}}{\psi_{k}} = k(\alpha+1)-1, & \quad \text{for} \enspace c(v)=k < b, \end{cases}\end{equation*}

and consequently

\begin{equation*}\begin{split} \sum_{\tilde{T} \in \mathcal{T} : T \to \tilde{T}} \frac{w(\tilde{T})}{w(T)} &= \sum_{k=1}^{b-1} (k(\alpha+1)-1) m_{k} + \sum_{k \ge 0} n_{k} ((\alpha+1)b-1+k)\\ &= (\alpha+1)\left(\sum_{k=1}^{b-1} k m_{k} + b \sum_{k \ge 0} n_{k}\right) - \left(\sum_{k=1}^{b-1} m_{k} - \sum_{k \ge 0} (k-1)n_{k}\right) =(\alpha+1)n-1,\end{split}\end{equation*}

due to equations (7) and (8). Again, with this choice of weight sequences $(\varphi_k)_k$ and $(\psi_k)_k$ , it follows that the probability $p_{T}(v)$ that in a bucket increasing tree T of size $|T|=n$ the node v with capacity $c(v)=k$ attracts element $n+1$ coincides with the corresponding probability in the stochastic growth rule for $(\mathrm{b},\alpha)$ -plane oriented recursive trees given in Definition 3.

We obtain then from equation (2) that the exponential generating function $T(z)\,:\!=\,\sum_{n\ge 1}T_n\frac{z^{n}}{n!}$ of the total-weight $T_{n}$ of $(\mathrm{b},\alpha)$ -plane oriented recursive trees of size n satisfies the differential equation

(11) \begin{equation} \frac{d^b}{dz^b}T(z)=(b-1)!(\alpha+1)^{b-1}\binom{b-1-\frac{1}{\alpha+1}}{b-1} \frac{1}{(1-T(z))^{b(\alpha+1)-1}},\end{equation}

with initial conditions $T(0)=0$ and $\left.\frac{d^k}{dz^k}T(z)\right|_{z=0}\!\!=(k-1)!(\alpha+1)^{k-1}\binom{k-1-\frac{1}{\alpha+1}}{k-1}$ , for $1\le k \le b-1$ . Again it can be checked easily that the solution of this equation is given by

(12) \begin{equation} T(z)=(1-(\alpha+1)z)^{\frac1{\alpha+1}}-1=\sum_{n\ge 1}(n-1)!(\alpha+1)^{n-1}\binom{n-1-\frac{1}{\alpha+1}}{n-1} \frac{z^{n}}{n!}.\end{equation}

Hence the total weight of all size n $(\mathrm{b},\alpha)$ -plane oriented recursive trees is given by $T_n=(n-1)!(\alpha+1)^{n-1}\binom{n-1-\frac{1}{\alpha+1}}{n-1}$ , which finishes the proof of Theorem 12

In Tables 1–2 we summarise the combinatorial properties as well as the growth processes of the bucket increasing tree families considered in this work.

Table 1 Summary: bucket increasing tree families and their growth processes

Table 2 Summary: bucket increasing tree families and their combinatorial properties

5.1 Symbolic description and bijections

We consider trees with bucket size $b=2$ , degree-weight generating function $\varphi(t)$ and weight $\psi = \psi_{1} = 1$ . As stated in Example 8 they allow the symbolic description

(16) \begin{equation}\mathcal{T} = \mathcal{Z}^{\Box} +\mathcal{Z}^{\Box} \ast \left(\mathcal{Z}^{\Box} \ast \varphi\big(\mathcal{T}\big)\right).\end{equation}

The exponential generating function T(z) satisfies the first-order differential equation

\[ T'(z) = \sqrt{1+2\cdot\Phi(T(z))}, \quad T(0)=0,\]

with $\Phi(x)=\int_{0}^{x} \varphi(t)dt$ . Moreover, $T=T(z)$ is implicitly given via

\[\int_{0}^{T}\frac{dx}{\sqrt{1+2\cdot\Phi(x)}}=z.\]

On the other hand, increasing diamonds as proposed in [Reference Bodini, Dien, Fontaine, Genitrini and Hwang4] are defined by the symbolic equation

(17) \begin{equation}\mathcal{F} = \mathcal{Z}^{\Box} +\mathcal{Z}^{\Box} \ast \varphi\big(\mathcal{F}\big) \ast \mathcal{Z}^{\blacksquare},\end{equation}

where the latter boxed product constrains the largest label. They constitute a combinatorial family of labelled, directed acyclic graphs (DAGs) with a source and a sink such that the labels along any path are increasing. The functional operation $\varphi$ occurring in (17) is here specifying possible degrees respectively their weights, see [Reference Bodini, Dien, Fontaine, Genitrini and Hwang4] for more details. Figure 3 illustrates two examples of increasing diamonds.

Figure 3. Two different increasing diamonds of size nine and fourteen, respectively.

The symbolic description (17) of increasing diamonds leads to exactly the same exponential generating function as for bucket increasing trees with bucket size $b=2$ described formally via (16). Thus, it is natural to ask for a bijection between these combinatorial objects of a given size, where the size of an increasing diamond is given by the number of its nodes.

Before stating such a bijection we note that it is convenient to think of an increasing diamond $F\in\mathcal{F}$ as having three types of nodes stemming from the recursive combinatorial construction given in (17), which partitions the set of nodes into small nodes, inner nodes and large nodes, i.e.,

\begin{equation*} V(F) = V_{S}(F) \: \dot{\cup} \: V_{I}(F) \: \dot{\cup} \: V_{L}(F).\end{equation*}

Namely, if F has size one its only vertex is assigned to an inner node. Otherwise, the smallest node and the largest node of F are assigned to the respective node type; furthermore by removing these two nodes of F we obtain a (possibly empty) sequence of increasing diamonds $F_{1}, \dots, F_{r}$ , and to each of these structures we apply this assignment recursively.

The bijection $\mathcal{M}$ together with the characterisation given in Theorem 12 provides a characterisation of families $\mathcal{F}$ of increasing diamonds with a total weight $T_n$ , resembling the weights of ordinary increasing trees and thus leading to simple counting formulas. In particular, this explains the strikingly simple formula observed in [Reference Bodini, Dien, Fontaine, Genitrini and Hwang4], which we collect in the next statement.

Corollary 19. The number $T_n$ of increasing diamonds of size n with degree-weight generating function $\varphi(t)=1/(1-t)^{3}$ equals the number of plane-oriented recursive trees of size n. It is given by the simple formula

\[T_n=(2n-3)!!=\frac{(2n-2)!!}{2^{n-1}(n-1)!},\quad n\ge 1.\]

Proof of Corollary 19. By bijection $\mathcal{M}$ in Theorem 18 increasing diamonds $\mathcal{F}$ with degree-weight generating function $\varphi(t)=1/(1-t)^{3}$ are mapped to three-bundled bilabelled bucket ordered increasing trees $\mathcal{B}_3$ with the same degree-weight generating function. Furthermore, the refined clustering map $\mathcal{C}_\ast$ maps the family $\mathcal{B}_3$ bijectively to a family of ordinary increasing trees $\mathcal{T}^{[1]}$ , called plane-oriented recursive trees, with degree-weight generating function $\phi(t)=1/(1-t)$ . Symbolically, we have

\[\big(\mathcal{C}_\ast^{-1}\circ\mathcal{M}\big)(\mathcal{F})=\mathcal{T}^{[1]}.\]

The number of plane-oriented recursive trees of size n is well known [Reference Bergeron, Flajolet and Salvy3, Reference Drmota5, Reference Flajolet and Segdewick6, Reference Prodinger23, Reference Prodinger24] and obtained from the the classical generating function of the total numbers $T(z)=1-\sqrt{1-2z}$ , satisfying

\[T'(z)=\phi\big(T(z)\big)=\frac{1}{1-T(z)},\quad T(0)=0.\]

Extraction of coefficients gives

\[T_n = n! [z^n]T(z) = (2n-3)!!\]

Proof. Our bijection $\mathcal{M} : \mathcal{F}_{n} \to \mathcal{T}_{n}$ uses two steps: first we construct recursively intermediate objects that we call increasing-decreasing bilabelled trees, where each bucket holds the smallest as well as the largest label in its subtree. Thus, when considering a tree $\hat{T} \in \mathcal{ID}$ of this family and restricting to the smaller or larger labels in each bucket, it is an increasing or decreasing tree, respectively. Then we give a recursive procedure that transforms, by using cyclic permutations of the labels, such trees to bucket increasing trees of the same shape. These recursive procedures are given as Algorithms 3–4; combining them leads to Algorithm 2 and thus the map $\mathcal{M}$ . We further observe that the weight sequence $(\varphi_k)_{k\ge 0}$ is not involved in the bijection, as the weights are directly preserved: if a certain substructure of an increasing diamonds F decomposes into the node with smallest label, the node with largest label and $r \ge 0$ increasing subdiamonds, then the corresponding subtree in the bucket increasing tree $\tilde{T} = \mathcal{M}(F)$ decomposes into the root bucket and exactly r subtrees. We also note that the reverse map $\mathcal{M}^{-1}$ is readily obtained by inverting the recursive procedures in a natural way.

The bijection $\mathcal{M}$ is illustrated in Figures 4–5 for the increasing diamonds given in Figure 3.

Figure 4. The increasing diamond of size nine from Figure 2 with three different label types is mapped to an increasing-decreasing bilabelled tree and then to a bucket increasing tree.

Figure 5. The increasing diamond from Figure 2 of size 14 with three different label types is mapped to an increasing-decreasing bilabelled tree and then to a bucket increasing tree.

The map also gives a correspondence between quantities in increasing diamonds and bucket increasing trees. Let $I_{n}$ denote the random variable counting the number of inner nodes in a random increasing diamond of size n. Moreover, let $N_n$ denote the number of nodes with capacity one in a random bucket increasing tree of size n. Then we get the following corollary.

We note that a refined enumeration of increasing diamonds according to the number of inner nodes is possible in a rather direct way. Let

\[f(z,u)=\sum_{n\ge 1}\sum_{j=1}^{n}\frac{T_{n,j}}{n!}z^n u^j=\sum_{n\ge 1}\frac{T_n\cdot {\mathbb{E}}\left(u^{I_n}\right)}{n!}z^n\]

denote the refined generating function with $f(z,1)=T(z)$ .

Then from the symbolic equation (17) and the resulting differential equation for f(z,u) one gets that $f=f(z,u)$ is characterised implicitly via

\[\int_{0}^{f}\frac{dx}{\sqrt{u^2+2\cdot\Phi(x)}}=z.\]

Many interesting concrete generating functions and examples can be obtained by specialising $\varphi(t)$ ; the authors are currently investigating into this matter.

6.1. The generating functions approach

In order to study $K_{n}$ for bucket increasing trees we introduce the bivariate generating function

(18) \begin{equation} N(z,v) \,:\!=\, \sum_{n \ge 0} \sum_{m \ge 0} \mathbb{P}\{K_{n+1} = m\} T_{n+1} \frac{z^{n}}{n!} v^{m}.\end{equation}

To establish a functional equation for N(z,v) from the formal recursive equation (1) it is now convenient to think of specifically bicoloured bucket increasing trees, where the colouring is as follows: exactly one element, namely the element with largest label, is coloured red, and all elements having a label smaller than the red element are coloured black. Let us first assume that the red element of T is not contained in the root node. Then the red element is located in one of the r subtrees of the root of T; let us assume that it is in the j-th subtree. Let us now consider these r subtrees. After order preserving relabellings, each subtree $S_{1}, \dots, S_{r}$ is an bucket increasing tree by itself, where one of the r subtrees contains the red element. Note the obvious fact that the size of the bucket of the red element is the same in T and in the respective subtree $S_{j}$ .

We introduce now generating functions, with exponential variable z, where z marks the black elements, $f(z) = \sum_{n \ge 0} f_{n} \frac{z^n}{n! }$ for sequences $f_{n}$ and $f(z,v)=\sum_{n,m \ge 0} f_{n,m} \frac{z^n }{n!}v^m$ for sequences $f_{n,m}$ , where v counts the initial bucket size of the red element. With this setting, the total weight of all suitably bicoloured bucket increasing trees, where the initial bucket size of the red element is exactly m, is given by ${\mathbb{P}}\{K_{n+1} = m\} T_{n+1}$ , and thus its generating function is given by

\begin{equation*} \sum_{n \ge 0} \sum_{m \ge 0} \mathbb{P}\{K_{n+1}=m\} T_{n+1} \frac{z^{n}}{n!} v^{m} = N(z,v),\end{equation*}

whereas the total weight of suitably monocoloured ordinary bucket increasing trees is $T_{n}$ and its generating function is given by

\begin{equation*} \sum_{n \ge 1} T_{n} \frac{z^{n}}{n!} = T(z).\end{equation*}

The $r-1$ monocoloured trees and the bicoloured bucket tree lead then to the expression $T(z)^{r-1} \cdot N(z,v)$ . Since the red element can be in the first, second, $\dots$ , r-th subtree, we additionally get a factor r. Furthermore, the event that the root has out-degree r leads to a factor $\varphi_r$ . Summing over all $r \ge 1$ leads thus to $\sum_{r\ge 1} r \varphi_r T(z)^{r-1} N(z,v) =\varphi'(T(z)) N(z,v).$ Since the elements labelled by $1, 2, \dots, b$ contained in the root node are all coloured black (which again means that b elements in a labelled object are fixed), equation (1) leads thus to the following differential equation of order b for N(z,v):

(19) \begin{equation} \frac{\partial^b}{\partial z^b}N(z,v) = \varphi'(T(z)) \cdot N(z,v).\end{equation}

The cases, where the red element is contained in the root of the tree do not appear explicitly in the differential equation itself, but will be described by the initial conditions. Since $\mathbb{P}\{K_{n}=n\}=1$ , for $1 \le n \le b$ (if element n is contained in the root node then all elements with a label $\le n$ are also contained in the root node), we obtain the following initial conditions, for $0 \le \ell \le b-1$ :

\begin{align*} \left.\frac{\partial^{\ell}}{\partial z^{\ell}} N(z,v)\right|_{z=0} & = \sum_{m \ge 0} \mathbb{P}\{K_{\ell+1}=m\} T_{\ell+1} v^{m}=T_{\ell+1} v^{\ell+1}, \end{align*}

with $T_{n} = n! [z^{n}] T(z)$ and T(z) as characterised in Proposition 12 for the particular tree families.

Now we can specify the sequences according to the tree family of interest. Note that for bucket recursive trees the initial bucket size of node n was already (implicitly) characterised in [Reference Kuba and Panholzer13], hence we will skip this case. For (b,d)-ary increasing trees we obtain the following Cauchy-Euler type differential equation together with the initial conditions for the bivariate generating function N(z,v):

(20) \begin{align} \frac{\partial^{b}}{\partial z^{b}} N(z,v) = \frac{T_{b+1}}{(1-(d-1)z)^{b}}N(z,v), \quad \left.\frac{\partial^{\ell}}{\partial z^{\ell}} N(z,v)\right|_{z=0} = T_{\ell+1}v^{\ell+1}, \quad \text{for} \enspace 0 \le \ell \le b-1.\nonumber\\\end{align}

For $(\mathrm{b},\alpha)$ -plane oriented recursive trees we obtain a very similar Cauchy-Euler type differential equation together with the initial conditions for the bivariate generating function N(z,v):

(21) \begin{align} \frac{\partial^{b}}{\partial z^{b}} N(z,v) = \frac{T_{b+1}}{(1-(\alpha+1)z)^{b}}N(z,v), \quad \left.\frac{\partial^{\ell}}{\partial z^{\ell}} N(z,v)\right|_{z=0} = T_{\ell+1}v^{\ell+1}, \quad \text{for} \enspace 0 \le \ell \le b-1.\nonumber\\\end{align}

6.2. The distribution of the initial bucket size

In order to obtain the exact distribution of the r.v. $K_{n}$ we will give the exact solution of the homogeneous differential equations (20), (21), which are of Cauchy-Euler-type. Plugging in the Ansatz $N(z,v) = \frac{1}{(1-(d-1)z)^{\lambda}}$ for (b,d)-ary increasing trees, and $N(z,v) = \frac{1}{(1-(\alpha+1)z)^{\lambda}}$ for $(\mathrm{b},\alpha)$ -plane oriented recursive trees, with unspecified $\lambda$ , into equations (20), (21) leads to the indicial equation

(22) \begin{equation} \lambda^{\overline{b}} = \begin{cases} \displaystyle{\frac{T_{b+1}}{(d-1)^{b}}},\\[15pt]\displaystyle{\frac{T_{b+1}}{(\alpha+1)^{b}}}, \end{cases} \quad \text{or equivalently} \quad \binom{\lambda+b-1}{b} = \begin{cases} \displaystyle{\binom{b+\frac{1}{d-1}}{b}},\quad\textrm{(b,d)}\text{-ary ITs},\\[15pt]\displaystyle{\binom{b-\frac{1}{\alpha+1}}{b}},\quad (\text{b},\alpha)\text{-PORTs}. \end{cases}\end{equation}

Similar equations have been studied in [Reference Mahmoud and Smythe18] for bucket recursive trees. It is convenient to give a unified analysis of the indicial equations for all three models. Let

(23) \begin{equation}\quad \kappa=\begin{cases} \displaystyle{0}, & \quad \text{bucket recursive trees}, \\[5pt] \displaystyle{\frac{1}{d-1}}, & \quad \text{(b,d)}\text{-ary ITs}, \\[14pt] \displaystyle{-\frac{1}{\alpha+1}}, & \quad (\text{b},\alpha)\text{-PORTs}. \end{cases}\end{equation}

Then, the indicial equations can be written in a unified way:

(24) \begin{equation} \lambda^{\overline{b}} = {(b+\kappa)^{\underline{b}}}.\end{equation}

Equations of this or similar kind have been treated in [Reference Kuba and Panholzer13, Reference Kuba and Panholzer17, Reference Mahmoud and Smythe18]. It follows from these considerations that, for $\kappa$ given in (23), all solutions $\lambda_{1}, \lambda_{2}, \dots, \lambda_{b}$ of (24) are simple, and when arranging them in descending order of real parts it further holds $1+\frac{1}{d-1}=\lambda_{1} > \Re(\lambda_{2}) \ge \Re(\lambda_{3}) \ge \cdots\ge \Re(\lambda_{b})$ for (b,d)-ary increasing trees and $1-\frac{1}{\alpha+1}=\lambda_{1} > \Re(\lambda_{2}) \ge \Re(\lambda_{3}) \ge \cdots\ge \Re(\lambda_{b})$ for $(\mathrm{b},\alpha)$ -plane oriented recursive trees. Thus the general solutions of (20), (21) are given by

(25) \begin{equation} N(z,v) = \begin{cases} \displaystyle{\sum_{i=1}^{b} \frac{\beta_{i}(v)}{(1-(d-1)z)^{\lambda_{i}}}},\quad \text{(b,d)} \text{-ary ITs},\\[15pt]\displaystyle{\sum_{i=1}^{b} \frac{\beta_{i}(v)}{(1-(\alpha+1)z)^{\lambda_{i}}}},\quad(\text{b},\alpha)\text{-PORTs}, \end{cases}\end{equation}

with certain functions $\beta_{i}(u,v)$ , which are specified by the initial conditions as given in (20), (21). When these initial conditions are plugged into (25) this leads to the following system of linear equations for the unknown functions $\beta_{i}(v)$ , $1 \le i \le b$ :

\begin{equation*} \sum_{i=1}^{b} \lambda_{i}^{\overline{\ell}} \beta_{i}(v)= \begin{cases} \displaystyle{v^{\ell+1}l!\binom{\ell+\frac{1}{d-1}}{\ell}},\quad\text{(b,d)}\text{-ary ITs},\\[15pt]\displaystyle{v^{\ell+1}l!\binom{\ell-\frac{1}{\alpha+1}}{\ell}},\quad(\text{b},\alpha)\text{-PORTs}. \end{cases}\end{equation*}

Using the abbreviations

(26) \begin{equation} s_{\ell} \,:\!=\, s_{\ell}(v) \,:\!=\, \begin{cases} \displaystyle{v^{\ell+1}\binom{\ell+\frac{1}{d-1}}{\ell}},\quad\text{(b,d)}\text{-ary ITs},\\[15pt]\displaystyle{v^{\ell+1}\binom{\ell-\frac{1}{\alpha+1}}{\ell}},\quad(\text{b},\alpha)\text{-PORTs}, \end{cases}\end{equation}

we obtain the following system of linear equations for the unknown $\beta_{i}=\beta_i(v)$ , $1 \le i \le b$ :

(27) \begin{equation} \sum_{i=1}^{b} \binom{\lambda_{i}+\ell-1}{\ell} \beta_{i} = s_{\ell}, \quad \text{for} \enspace 0 \le \ell \le b-1.\end{equation}

To obtain the solution of (27) we can use results and respective computations given in [Reference Kuba and Panholzer13, equations (22) and (30)], slightly adapted to $\kappa$ occurring in the indicial equation (24) of the tree families considered.

Lemma 21 ([Reference Kuba and Panholzer13]). For given numbers $\lambda_i$ , with $1\le i\le b$ , specified as the solutions of equation (24), and numbers $s_{\ell}$ , $0\le \ell\le b-1$ , the system of linear equations with unknowns $\beta_i$ ,

\begin{equation*}\sum_{i=1}^{b} \binom{\lambda_{i}+\ell-1}{\ell-1}\beta_{i}=s_{\ell},\quad 0\le \ell\le b-1,\end{equation*}

has the exact solution

\begin{equation*}\beta_i=\begin{cases}\displaystyle{\sum_{r=0}^{b-1}s_r \frac{\binom{\lambda_i+b-1}{b-r-1}}{\binom{b}{r}(b-r)\binom{b+\frac{1}{d-1}}{b}\left(H_{\lambda_i+b-1}-H_{\lambda_i-1}\right)}},\quad 1\le i\le b,\quad\text{(b,d)}\text{-ary ITs},\\[22pt]\displaystyle{\sum_{r=0}^{b-1}s_r \frac{\binom{\lambda_i+b-1}{b-r-1}}{\binom{b}{r}(b-r)\binom{b-\frac{1}{\alpha+1}}{b}\left(H_{\lambda_i+b-1}-H_{\lambda_i-1}\right)}},\quad 1\le i\le b,\quad(\text{b},\alpha)\text{-PORTs}.\end{cases}\end{equation*}

An application of Lemma 21 immediately gives the values $\beta_i(v)$ with respect to the initial conditions (26). Thus extracting coefficients yields

\begin{equation*}[z^{n-1}v^m]N(z,v)={\mathbb{P}}\{K_{n}=m\}\frac{T_{n}}{(n-1)!}=\begin{cases} \displaystyle{\sum_{i=1}^{b}\binom{\lambda_i+n-2}{n-1}(d-1)^{n-1}[v^m]\beta_i(v)},\quad\text{(b,d)}\text{-ary ITs},\\[15pt] \displaystyle{\sum_{i=1}^{b}\binom{\lambda_i+n-2}{n-1}(\alpha+1)^{n-1}[v^m]\beta_i(v)},\quad(\text{b},\alpha)\text{-PORTs}, \end{cases}\end{equation*}

and by specifying $T_{n}$ as given in Theorem 12 and $s_{\ell}(v)$ as given in (26) we obtain the exact distribution of $K_{n}$ stated in the following theorem.

Theorem 22. The probability mass function of the random variable $K_n$ counting the initial bucket size of node n in a random bucket tree of size n is given by the following closed formula.

\begin{equation*}{\mathbb{P}}\{K_n=m\}=\begin{cases}\displaystyle{\sum_{i=1}^{b}\frac{\binom{\lambda_i+n-2}{n-1}\binom{\lambda_i+b-1}{b-m}\binom{m-1+\frac{1}{d-1}}{m-1}}{\binom{n-1+\frac{1}{d-1}}{n-1}\binom{b}{m-1}(b-m+1)\binom{b+\frac{1}{d-1}}{b}\left(H_{\lambda_i+b-1}-H_{\lambda_i-1}\right)}},\quad\text{for }\text{(b,d)}\text{-ary ITs},\\[25pt]\displaystyle{\sum_{i=1}^{b}\frac{\binom{\lambda_i+n-2}{n-1}\binom{\lambda_i+b-1}{b-m}\binom{m-1-\frac{1}{\alpha+1}}{m-1}}{\binom{n-1-\frac{1}{\alpha+1}}{n-1}\binom{b}{m-1}(b-m+1)\binom{b-\frac{1}{\alpha+1}}{b}\left(H_{\lambda_i+b-1}-H_{\lambda_i-1}\right)}},\quad\text{for }(\text{b},\alpha)\text{-PORTs},\end{cases}\end{equation*}

for $1\le m\le b$ .

For n tending to infinity the random variable $K_n$ converges in distribution to a limit K, whose discrete distribution is given as follows.

\begin{equation*}{\mathbb{P}}\{K=m\}=\begin{cases}\displaystyle{\frac{\binom{b+\frac{1}{d-1}}{b-m}\binom{m-1+\frac{1}{d-1}}{m-1}}{\binom{b}{m-1}(b-m+1)\binom{b+\frac{1}{d-1}}{b}\left(H_{b+\frac{1}{d-1}}-H_{\frac{1}{d-1}}\right)}},\quad {(b,d)}{-ary ITs},\\[25pt]\displaystyle{\frac{\binom{b-\frac{1}{\alpha-1}}{b-m}\binom{m-1-\frac{1}{\alpha+1}}{m-1}}{\binom{b}{m-1}(b-m+1)\binom{b-\frac{1}{\alpha+1}}{b}\left(H_{b-\frac{1}{\alpha+1}}-H_{-\frac{1}{\alpha+1}}\right)}},\quad({b},\alpha){-PORTs},\end{cases}\end{equation*}

for $1\le m \le b$ .

Remark 23. The corresponding results for bucket recursive trees were already derived in [Reference Kuba and Panholzer13] (although not stated explicitly):

\begin{equation*} \mathbb{P}\{K_{n}=m\} = \sum_{i=1}^{b} \frac{\binom{\lambda_{i}+b-1}{b-m} \binom{\lambda_{i}+n-2}{n-1}} {\binom{b}{m-1} (b-m+1) \left(H_{\lambda_{i}+b-1} - H_{\lambda_{i}-1}\right)},\end{equation*}

for $1\le m\le b$ . Furthermore, for bucket recursive trees the random variable $K_n$ converges, for $n \to \infty$ , in distribution to a Zipf-distributed limit K:

\[{\mathbb{P}}\{K=m\}=\frac{1}{m H_b},\quad 1\le m \le b.\]

Proof. It remains to show the stated limiting distribution results. We apply Stirling’s formula for the Gamma-function

\[ \Gamma(z) = \left(\frac{z}{e}\right)^{z}\frac{\sqrt{2\pi }}{\sqrt{z}} \left(1+\mathcal{O}\left(\frac{1}{z}\right)\right),\]

and get

\[ \binom{n-1+\frac{1}{d-1}}{n-1}=\frac{\Gamma\left(n+\frac{1}{d-1}\right)}{\Gamma\left(1+\frac{1}{d-1}\right)\Gamma(n)}=\frac{n^{\frac{1}{d-1}}}{\Gamma\left(1+\frac{1}{d-1}\right)}\left(1+\mathcal{O}\left(n^{-1}\right)\right),\]

as well as

\[ \binom{n-1-\frac{1}{\alpha+1}}{n-1}=\frac{\Gamma\left(n-\frac{1}{\alpha+1}\right)}{\Gamma\left(1-\frac{1}{\alpha+1}\right)\Gamma(n)}=\frac{n^{-\frac{1}{\alpha+1}}}{\Gamma\left(1-\frac{1}{\alpha+1}\right)}\left(1+\mathcal{O}(n^{-1})\right).\]

Concerning the roots of the indicial equations recall from remarks stated past equation (24) that

\[\lambda_1=\begin{cases}1+\frac{1}{d-1},\quad\text{(b,d)}\text{-ary ITs},\\[9pt]1-\frac{1}{\alpha+1},\quad(\text{b},\alpha)\text{-PORTs}.\end{cases}\]

For (b,d)-ary increasing trees we obtain the following asymptotic expansions:

\begin{align*} \binom{n-2+\lambda_{i}}{n-1} & = \frac{n^{\lambda_{i}-1}}{\Gamma(\lambda_{i})} \left(1+\mathcal{O}(n^{-1})\right) = \begin{cases} \frac{n^{\frac{1}{d-1}}}{\Gamma\left(1+\frac{1}{d-1}\right)}\left(1+\mathcal{O}(n^{-1})\right), & \quad i=1, \\[18pt] \mathcal{O}\left(n^{\Re \lambda_{i}-1}\right), & \quad 2 \le i \le b. \end{cases}\end{align*}

For $(\mathrm{b},\alpha)$ -plane oriented recursive trees we have the corresponding results

\begin{align*} \binom{n-2+\lambda_{i}}{n-1} = \begin{cases} \frac{n^{-\frac{1}{\alpha+1}}}{\Gamma\left(1-\frac{1}{\alpha+1}\right)}\left(1+\mathcal{O}(n^{-1})\right), & \quad i=1, \\[18pt] \mathcal{O}\left(n^{\Re \lambda_{i}-1}\right), & \quad 2 \le i \le b. \end{cases}\end{align*}

Thus, for $n\to\infty$ , the dominant contribution in the asymptotic expansions of ${\mathbb{P}}\{K_n=m\}$ and the finite sum stems from the index $i=1$ and $\lambda_1$ , leading to the stated result.

6.3 Relation to node types in bucket increasing trees

Let $N_{n,j}$ denote the random variable counting the number of nodes with capacity $c(v)=j$ , $1\le j \le b$ . Furthermore, let ${\textbf{N}}_n$ denote the random vector $(N_{n,1},\dots,N_{n,b})$ . Mahmoud and Smythe [Reference Mahmoud and Smythe18] considered bucket recursive trees. They proved a multivariate central limit theorem for ${\textbf{N}}_n$ for trees with bucket size $b \le 26$ . For trees with $b > 26$ a phase change in the limiting distribution of ${\textbf{N}}_n$ was detected and the central limit theorem does not hold anymore. In the following we are going to analyse the limiting distribution of the random vector ${\textbf{N}}_n$ for (b,d)-ary increasing trees and $(\mathrm{b},\alpha)$ -plane oriented recursive trees. We also summarise the main results for bucket recursive trees. There is a close connection between the random variables $K_n$ and ${\textbf{N}}_n$ . The distribution of the initial bucket size $K_{n+1}$ depends on the different node types present at time n, $n\ge 1$ . Let $v_{k}=v_{n,m,k}$ denote the buckets of capacity m contributing to $N_{n,m}$ , with $1\le m\le b$ and $1\le k\le N_{n,j}$ . Then, by definition of the growth processes

\[{\mathbb{P}}\left\{K_{n+1}=1 \mid {\textbf{N}}_n\right\}=\sum_{k=1}^{N_{n,b}}{\mathbb{P}}\left\{n+1<_t v_{n,b,k}\right\}\]

and, for $2\le m\le b$ ,

\[{\mathbb{P}}\left\{K_{n+1}=m \mid {\textbf{N}}_n\right\}=\sum_{k=1}^{N_{n,m-1}}{\mathbb{P}}\left\{n+1<_t v_{n,m-1,k}\right\}.\]

Of course, for each k, the probabilities ${\mathbb{P}}\{n+1<_t v_{n,b,k}\}$ coincide and are given according to Definitions 1–3:

\[{\mathbb{P}}\{n+1<_t v_{n,m,k}\}=\begin{cases}\dfrac{m}{n}, & \text{bucket recursive trees},\\[12pt]\dfrac{(d-1)m+1-\text{deg}^{+}(v)}{(d-1)n+1}, & \text{(b,d)}\text{-ary ITs},\\[12pt]\dfrac{\text{deg}^{+}(v)+(\alpha+1)m-1}{(\alpha+1)n-1}, & (\text{b},\alpha)\text{-PORTs}.\\\end{cases}\]

Note that for $1\le m\le b-1$ the individual nodes $v_{k}=v_{n,m,k}$ are unsaturated, such that $\text{deg}^+(v_{n,m,k})=0$ . Consequently, summation leads to the following result.

Proposition 24. The random variable $K_n$ counting the initial size of the bucket containing label n is related to the number of nodes ${\textbf{N}}_n=(N_{n,1},\dots,N_{n,b})$ with respective capacities as follows. For $2\le m\le b$ it holds

\[{\mathbb{P}}\{K_{n+1}=m\}={\mathbb{E}}(N_{n,m-1})\cdot\begin{cases}\dfrac{m-1}{n}, & \text{bucket recursive trees},\\[15pt]\dfrac{(d-1)(m-1)+1}{(d-1)n+1}, & \text{(b,d)}\text{-ary ITs},\\[15pt]\dfrac{(\alpha+1)(m-1)-1}{(\alpha+1)n-1}, & (\text{b},\alpha)\text{-PORTs}.\end{cases}\]

and

\[{\mathbb{P}}\{K_{n+1}=1\}=\begin{cases}{\mathbb{E}}\left(N_{n,b}\right)\cdot \dfrac{b}{n}, & \text{bucket recursive trees},\\[15pt]{\mathbb{E}}(N_{n,b})\cdot \dfrac{(d-1)b+1}{(d-1)n+1}+\dfrac{1-\sum_{j=1}^b{\mathbb{E}}(N_{n,j})}{(d-1)b+1}, & \text{(b,d)}\text{-ary ITs},\\[15pt]{\mathbb{E}}(N_{n,b})\cdot \dfrac{(\alpha+1)b-1}{(\alpha+1)n-1}+\dfrac{-1+\sum_{j=1}^b{\mathbb{E}}\left(N_{n,j}\right)}{(\alpha+1)n-1}, & (\text{b},\alpha)\text{-PORTs}.\end{cases}\]

In the following we consider generalised Pólya-Eggenberger urn models (see, e.g., [Reference Janson7]) with b different types of balls. For bucket recursive trees Mahmoud and Smythe [Reference Mahmoud and Smythe18] studied the following urn model.

Urn 25 (Bucket recursive trees) Consider a balanced urn with balls of b colours and let $Q_{n,m}$ denote the number of balls of type m, $1\le m\le b$ , in the urn after n draws. $(Q_{n,1},\dots,Q_{n,b})$ denotes the corresponding random vector at time n. At each time step, draw one ball at random from the urn, observe its colour, and add balls according to the ball replacement matrix

\[M=\left(\begin{matrix}-1 & \quad 2 & \quad 0 & \quad \dots & \quad 0\\[3pt]0 & \quad -2 & \quad 3 & \quad \dots & \quad 0\\[3pt]\vdots & & \quad \ddots & & \quad \vdots\\[3pt]0 & \quad \dots & \quad 0& \quad -(b-1) & \quad b \\[3pt]1 & \quad 0 & \quad 0 & \quad \dots &\quad 0 \\\end{matrix}\right)\]

and initial composition a single ball of type one. Then, the random variables $Q_{n,m}$ are related to the node types via

\[N_{n,m} = \frac{Q_{n,m}}{m},\quad 1\le m\le b.\]

The characteristic polynomial of M is given

(28) \begin{equation}\chi_M(\lambda)=\det(M-\lambda I)=(-1)^b\left({\lambda^{\overline{b}}}-b!\right).\end{equation}

For $b\le 26$ and $b > 26$ , respectively, there occurs a phase change: the limit law changes from normal to non-normal, which is due to the structure of the characteristic polynomial and the general results revealed in [Reference Janson7]. We assume that the eigenvalues $\lambda_1,\dots,\lambda_b$ are indexed according to their real parts

\[1=\Re \lambda_1 \ge \Re \lambda_2 \dots \ge \Re \lambda_b.\]

If the real part of $\lambda_2$ exceeds $\frac12$ then the limit law changes. In the following we denote the random vector of ball types as ${\textbf{Q}}_{n}=(Q_{n,1},\dots,Q_{n,b})$ .

Here we introduce two new urn models.

Urn 27 ( $(\mathrm{b},\alpha)$ -plane oriented recursive trees) Consider the urn with ball replacement matrix

\[M=\left(\begin{matrix}-\alpha & \quad 2\alpha +1 & \quad 0 & \quad \dots & \quad 0\\[4pt]0 & \quad -(2\alpha +1) & \quad 3\alpha +2 & \quad \dots & \quad 0\\[4pt]\vdots & \quad & \quad \ddots & \quad & \quad \vdots\\[4pt]0 & \quad \dots & \quad 0& \quad -((b-1)\alpha +b-2) & \quad b\alpha +b-1 \\[4pt]\alpha & \quad 0 & \quad 0 & \quad \dots & \quad 1 \\[4pt]\end{matrix}\right)\]

and initial composition $\alpha$ balls of type one. Then, the random variables $Q_{n,m}$ are related to the node types by

\[N_{n,m} = \frac{Q_{n,m}}{m\alpha +m-1},\quad 1\le m\le b.\]

The characteristic polynomial of M is given

(29) \begin{equation}\chi_M(\lambda)=\det(M-\lambda I)=(-1)^{b}(\alpha+1)^{b}\left({{\left(\frac{\lambda-1}{\alpha+1}\right)}^{\overline{b}}}-{\left(\frac{\alpha}{\alpha+1}\right)}^{\overline{b}}\right).\end{equation}

Urn 28 ((b,d)-ary increasing trees) Consider the urn with ball replacement matrix

\[M=\left(\begin{matrix}-d & \quad 2d-1 & \quad 0 & \quad \dots & \quad 0\\[4pt]0 & \quad -(2d-1) & \quad 3d-2 & \quad \dots & \quad 0\\[4pt]\vdots & \quad & \quad \ddots & \quad & \quad \vdots\\[4pt]0 & \quad \dots & \quad 0& \quad -((b-1)d -(b-2)) & \quad bd-(b-1) \\[4pt]d & \quad 0 & \quad 0 & \quad \dots & \quad -1 \\[4pt]\end{matrix}\right)\]

and initial composition d balls of type one. Then, the random variables $Q_{n,m}$ are related to the node types by

\[N_{n,m} = \frac{Q_{n,m}}{md -(m-1)},\quad 1\le m\le b.\]

The characteristic polynomial of M is given

(30) \begin{equation}\chi_M(\lambda)=\det(M-\lambda I)=(-1)^b(d-1)^b\left({\left(\frac{\lambda+1}{d-1}\right)}^{\overline{b}}-{\left(\frac{d}{d-1}\right)}^{\overline{b}}\right).\end{equation}

As indicated by the connection between $K_n$ and ${\textbf{N}}_n$ , there is also a close connection between the characteristic polynomials (28), (29), (30) and the indicial equation (24):

\[ \lambda^{\overline{b}} = {(b+\kappa)^{\underline{b}}}.\]

In particular, there is an affine transformation between these two polynomials. We note in passing that the general theorems of Janson [Reference Janson7] and Müller [Reference Müller20] allow to describe a phase change in the limit laws for $\textbf{N}_n$ similar to the results of Mahmoud and Smythe [Reference Mahmoud and Smythe18].

7.1 Descendants in bucket increasing trees

In order to avoid degeneracy we assume that $j\ge b+1$ (for $1\le j\le b$ it holds $Y_{n,j}=n+1-j$ ). Explicit results for the probability mass functions and the moments of both r.v. $Y_{n,j}$ and $X_{n,j}$ can be obtained in principle by purely combinatorial means and a generating functions approach similar to the parameter initial bucket size treated above. However, here we take a different point of view utilising the previous results for the initial bucket size to provide concise decompositions of the random variables based on results already known in the literature. Such decompositions readily lead to limit laws and seem to be more difficult to obtain by using a purely analytic combinatorial approach.

In order to obtain to analyse $Y_{n,j}$ , we introduce a refinement of this r.v.: let $Y_{n,\ell,j}=Y_{n,j}\mid K_j=\ell$ denote $Y_{n,j}$ conditioned on the event $K_j=\ell$ . According to the stochastic growth processes defined in Subsection 2.1 we obtain the recurrence relation

\begin{align*} {\mathbb{P}}\{Y_{n+1,\ell,j}=m\} = \frac{c_1(m+\ell-2)+c_2}{c_1n+c_2}{\mathbb{P}}\{Y_{n,\ell,j}=m-1\}+\frac{c_1(n+1-m-\ell)}{c_1n+c_2}{\mathbb{P}}\{Y_{n,\ell,j}=m\},\end{align*}

for $m\ge 1$ and the initial value $Y_{j,\ell,j}=1$ . The parameters $c_1,c_2$ occurring in this description of the law of $Y_{n,\ell,j}$ are determined by the fraction $\frac{c_2}{c_1}=\kappa$ as given in (23). Alternatively, $Y_{n,\ell,j}$ can be described as follows.

Proposition 29. The r.v. $Y_{n,\ell,j}$ can be described by a sum of dependent random variables $A_{i,\ell,j}$ , $i\ge j$ , all taking values in $\{0,1\}$ , and initial value $A_{j,\ell,j}=1$ , where $A_{i,\ell,j}$ denotes the indicator variable of the event that label i is a descendant of label j conditioned on the event $K_{j}=\ell$ , and we get

(31) \begin{equation}Y_{n,\ell,j}= \sum_{i=j}^{n}A_{i,\ell,j},\quad {\mathbb{P}}\{A_{i+1,\ell,j}=1 \mid Y_{i,\ell,j}\}= \frac{c_1\left(\ell-1+Y_{i,\ell,j}\right)+c_2}{c_1 i+c_2}.\end{equation}

Proof. It suffices to show that the probabilities ${\mathbb{P}}\{A_{i+1,\ell,j}=1 \mid Y_{i,\ell,j}\}$ are indeed given as stated above. Given $K_j$ assume that node v containing label j has $m\ge 1$ descendants at time $i\ge j$ . If $m< b+1-K_j$ then node v has out-degree zero and capacity $c(v)=K_j+m-1$ . It attracts a new label $i+1$ with probability $p(v)=p_{i+1}(v)$ determined directly by the stochastic growth rules:

\[p(v)=\begin{cases} \displaystyle{\frac{K_j+m-1}{i}}, & \quad \text{bucket recursive trees}, \\[10pt] \displaystyle{\frac{(d-1)(K_j+m-1)+1}{(d-1)i+1}}, & \quad \text{(b,d)}\text{-ary ITs}, \\[15pt] \displaystyle{\frac{(\alpha+1)(K_j+m-1)-1}{(\alpha+1)i-1}}, & \quad (\text{b},\alpha)\text{-PORTs}.\end{cases}\]

Otherwise, assume that the number of descendants is given by $m\ge b+1-K_j$ . Thus, node v is saturated and the remaining $m-(b+1-K_j)$ labels are distributed amongst the r non-root nodes $u_1,\dots,u_r$ in the subtree rooted at v. The probability ${\mathbb{P}}\{i+1 <_d j\}$ that label $i+1$ is a descendant of label j is given by

\[{\mathbb{P}}\{i+1 <_d j\}= {\mathbb{P}}\{i+1 <_c v\}+ \sum_{k=1}^{r}{\mathbb{P}}\{i+1 <_c u_k\},\]

where ${\mathbb{P}}\{i+1 <_c x\}$ denotes the probability that label $i+1$ is contained in the node x. We note that

\[\sum_{k=1}^{r}c(u_k)=m-\left(b+1-K_j\right),\qquad\text{deg}^{+}(v)+\sum_{k=1}^{r}\text{deg}^{+}(u_k)=r.\]

For bucket recursive trees we obtain

\[{\mathbb{P}}\left\{i+1 <_d j\right\}= \frac{b}i + \sum_{k=1}^{r}\frac{c(u_k)}{i}= \frac{b+m-\left(b+1-K_j\right)}{i}=\frac{K_j+m-1}{i}.\]

For (b,d)-ary increasing trees we have

\begin{align*}{\mathbb{P}}\{i+1 <_d j\} &= \frac{(d-1)c(v)+1-\text{deg}^{+}(v)}{(d-1)i+1} + \sum_{k=1}^{r}\frac{(d-1)c(u_k)+1-\text{deg}^{+}(u_k)}{(d-1)i+1}\\[5pt]&= \frac{(d-1)b+r+1 + (d-1)(m-(b+1-K_j))-r}{(d-1)i+1}=\frac{(d-1)(K_j+m-1)+1}{(d-1)i+1}.\end{align*}

Finally, for $(\mathrm{b},\alpha)$ -plane oriented recursive trees we get

\begin{align*}{\mathbb{P}}\left\{i+1 <_d j\right\} &= \frac{\text{deg}^{+}(v)+(\alpha+1)c(v)-1}{(\alpha+1)i-1} + \sum_{k=1}^{r}\frac{\text{deg}^{+}(u_k)+(\alpha+1)c(u_k)-1}{(\alpha+1)i-1}\\[8pt]&= \frac{r+(\alpha+1)(b+m-(b+1-K_j))-r-1}{(\alpha+1)i-1}=\frac{(\alpha+1)(K_j+m-1)-1}{(\alpha+1)i-1}.\end{align*}

Summarising we obtain the probabilities

\begin{equation*} {\mathbb{P}}\left\{i+1 <_d j \mid Y_{i,\ell,j}=m\right\} = \begin{cases} \displaystyle{\frac{\ell-1+m}{i}}, & \quad \text{bucket recursive trees}, \\[10pt] \displaystyle{\frac{(d-1)(\ell-1+m)+1}{(d-1)i+1}}, & \quad \text{(b,d)}\text{-ary ITs}, \\[17pt] \displaystyle{\frac{(\alpha+1)(\ell-1+m)-1}{(\alpha+1)i-1}}, & \quad (\text{b},\alpha)\text{-PORTs},\end{cases}\end{equation*}

thus leading to the decomposition stated in (31).

We remark in passing that, alternatively, $Y_{n,\ell,j}$ can also be described via a generalised Pólya urn model; see [Reference Kuba and Panholzer16].

It is a key observation that the distribution of $Y_{n,\ell,j}$ is identical to the distribution of a r.v. $D_{n,\ell,j}$ , counting so-called generalised descendants $D_{n,\ell,j}$ in ordinary families of increasing trees, which has been introduced and studied in [Reference Kuba and Panholzer12]. Namely, the r.v. $D_{n,\ell,j}$ also admits a description as a sum of dependent r.v. equivalent to (31), see [12, equations (7)–(8)], thus $Y_{n,\ell,j} \stackrel{(d)}{=} D_{n,\ell,j}$ . Unconditioning immediately leads to the following result.

Proposition 30 (Decomposition of the number of descendants). The random variable $Y_{n,j}$ counting the number of descendants of label j in a bucket increasing tree of size n for the families bucket recursive trees, (b,d)-ary increasing trees, and $(\mathrm{b},\alpha)$ -plane oriented recursive trees is related to the random variable $D_{n,\ell,j}$ , counting generalised descendants with parameter $\ell$ for the corresponding ordinary increasing tree families as studied in [Reference Kuba and Panholzer12], where the parameter $\ell$ is given by the random variable $K_j$ measuring the initial bucket size of label j:

\[Y_{n,j} {\stackrel{(d)}=} D_{n,K_j,j}.\]

The probability mass function of $D_{n,\ell,j}$ as well as limit laws have been obtained in [Reference Kuba and Panholzer12] using lattice path counting arguments. Using them this easily leads to the following limiting distribution result of $Y_{n,j}$ , also slightly refining the results of [Reference Kuba and Panholzer13] for bucket recursive trees. We thus omit the details.

7.2 Node degrees in bucket increasing trees

Let $X_{n,j}$ denote the random variable counting the out-degree of the bucket containing label j in a size n random bucket increasing tree. By definition, we can decompose $X_{n,j}$ into a sequence of dependent indicator variables

\[X_{n,j}=\sum_{\ell=j+1}^{n}{\mathbb{I}}\{\ell <_a j\},\]

where $\{\ell <_a j\}$ denotes the event that label $\ell$ is attached as a new node to the node containing label j. Similar to the case $b=1$ , see for example [Reference Kuba and Panholzer11], the random variable $X_{n,j}$ does not obey a uniform behaviour, but it is similar to the r.v. number of descendants considered before. Basically, we will observe that for $b>1$ the random variable $X_{n,j}$ behaves similar to the case $b=1$ once the bucket containing the label j is fully saturated. Compared to the two “stages” of $Y_{n,j}$ , insertion of label j into a node of size $K_j$ and then attraction of new labels, we have three stages: first, label j is inserted into a node v of size $K_j$ ; second, node v attracts new labels until it is fully saturated; then, until time n the node v attracts new labels and its out-degree increases. In order to state the precise decompositions of $X_{n,j}$ we utilise our previous results for $K_j$ and $Y_{n,j}$ . We also collect known results about additional random variables.

We introduce first the stopping time $\tau_{n,j}\,:\!=\,\min_{j\le\ell\le n}\{Y_{\ell,j}=b+1-K_j\}$ until the node containing label j is saturated. Let $\nabla$ denote the backward difference operator, i.e., $\nabla x_{k} \,:\!=\, x_{k} - x_{k-1}$ . The random variable $\tau_{n,j}$ can be expressed in terms of indicator variables as follows:

\[\tau_{n,j}=\sum_{k=j}^{n}{\mathbb{I}}\left\{Y_{k,j}= b+1-K_j,\,\nabla Y_{k,j}=1\right\}\cdot k + {\mathbb{I}}\left\{Y_{n,j}< b+1-K_j\right\} \cdot n,\]

where $Y_{j-1,j}=0$ . Let ${\mathbb{P}}\{m<_t v \mid c(v)=b-1\}$ denote the conditional probability that node v, containing label j, attracts label m conditioned on the event $c(v)=b-1$ , as determined by the stochastic growth processes of the three tree families considered:

\[{\mathbb{P}}\{m<_t v\mid c(v)=b-1\}=\begin{cases} \displaystyle{\frac{b-1}{m-1}}, & \quad \text{bucket recursive trees}, \\[16pt] \displaystyle{\frac{(d-1)(b-1)+1}{(d-1)(m-1)+1}}, & \quad \text{(b,d)}\text{-ary ITs}, \\[16pt] \displaystyle{\frac{(\alpha+1)(b-1)-1}{(\alpha+1)(m-1)-1}}, & \quad (\text{b},\alpha)\text{-PORTs}.\end{cases}\]

The probability mass function ${\mathbb{P}}\{\tau_{n,j}=m\}$ is readily obtained in terms of the probability mass functions of $K_j$ , $Y_{n,j}$ and thus $Y_{n,\ell,j}$ , where the constants $c_1,c_2$ are determined by (23) via $c_{2}/c_{1} = \kappa$ .

For $j\ge b+1$ the probability mass function ${\mathbb{P}}\{\tau_{n,j}=m\}$ is given as follows:

For $m=j$ we have

\[{\mathbb{P}}\{\tau_{n,j}=j\}={\mathbb{P}}\{K_j=b\},\]

for $j+1\le m<n$ we get

\[{\mathbb{P}}\{\tau_{n,j}=m\}=\sum_{\ell=1}^{b-1}{\mathbb{P}}\{K_j=\ell\}\cdot{\mathbb{P}}\{Y_{m-1,\ell,j}=b-\ell\}\cdot {\mathbb{P}}\{m<_t v \mid c(v)=b-1\},\]

whereas for $m=n$ we obtain

\[{\mathbb{P}}\{\tau_{n,j}=n\}=\sum_{\ell=1}^{b-1}{\mathbb{P}}\{K_j=\ell\}\cdot \big( {\mathbb{P}}\{Y_{n,\ell,j}< b+1-\ell\}+{\mathbb{P}}\{Y_{n-1,\ell,j}=b-\ell\}\cdot {\mathbb{P}}\{n<_t v\mid c(v)=b-1\}\big).\]

Proof. For $1\le j\le b$ there is only one bucket present. It is saturated after the insertion of label b. Assume that $j\ge b+1$ . The probability ${\mathbb{P}}\{\tau_{n,j}=j\}$ is given by

\[{\mathbb{P}}\left\{Y_{j,j}= b+1-K_j,\,\nabla Y_{j,j}=1\right\}={\mathbb{P}}\left\{1=b+1-K_j,\,Y_{j,j}-Y_{j-1,j}=1\right\}={\mathbb{P}}\{K_j=b\}.\]

For $j<m<n$ we obtain the probability of the event $\{Y_{k,j}= b+1-K_j,\,\nabla Y_{k,j}=1\}$ by conditioning on the initial bucket size $K_j$ . Finally, for $j=n$ we also take into account the probability of the event $\{Y_{n,j}<b+1-K_j\}$ .

Let $\text{Be}(p)$ denote a Bernoulli-distributed random variable:

\[{\mathbb{P}}\{\text{Be}(p)=1\}=p,\qquad {\mathbb{P}}\{\text{Be}(p)=0\}=1-p.\]

Furthermore, let $W_N(w_0,b_0)$ denote the number of white balls at time N in a triangular urn model with balls of two colours and initial values $w_0>0$ and $b_0>0$ , whose balanced replacement matrix given by $\left(\begin{smallmatrix}1& \quad \alpha\\[3pt] 0& \quad 1+\alpha\\\end{smallmatrix}\right)$ .

We obtain the following result.