The statistics and combinatorics of increasing trees and colored increasing trees

Southwood, Garrett; Wang, Hua

doi:10.61091/jcmcc123-34

Abstract

1. Introduction
2. Preliminaries
3. Increasing trees with restricted height
4. Colored binary trees and k-ary trees
5. Colored recursive tree
6. Conclusions

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 123
Pages: 475-487

Research article

The statistics and combinatorics of increasing trees and colored increasing trees

^¹, ^¹

¹Department of Mathematical Sciences, Georgia Southern University, Statesboro, GA 30460, USA

Received: 13/11/2024
Accepted: 05/12/2024
Published: 31/12/2024

Copyright Link
License

Abstract

We consider the generating function for increasingly labelled trees. By generalizing the proof through symbolic method, we are able to study various statistics regarding binary increasing trees with respect to height restrictions. We then apply our approach to special colorings of increasing trees in order to obtain their generating functions and, from there, derive the counting sequence for $(a k + a)$ -colored recursive trees. We also present some interesting bijections between colored and non-colored increasing trees.

Keywords: Increasing Trees, Generating Functions, Analytic Combinatorics

1. Introduction

The enumeration of trees has long been an interesting topic of study. It is a natural progression to assign some sort of labeling to the vertices of these trees, and from that, we have increasingly labeled trees. Formally speaking, an increasing tree is a tree which is labeled in a strictly increasing manner (where every vertex has a smaller label than any of its descendants) by ${1, \dots, n} .$ . One of the earliest results in increasing trees comes from Donaghey and his proof of a bijection between increasingly labeled binary trees and the alternating permutations [2].

This concept can also be expanded to trees with no restrictions on their down degrees (as opposed to the binary case, where all down degrees are 2 or 0), which are called recursive trees. Figure 1 shows an example. Recursive and random recursive trees have been extensively studied by Meir and Moon [5,6] and also by Szymański [10].

Interesting enumeration questions arise from these concepts. In the case of the recursive trees, it is well known that it is enumerated by $(n - 1)!$ . On the other hand, plane recursive trees are enumerated by $(2 n - 1)!!$ as seen in Prodinger’s paper [7]. A plane tree is a labeled tree in which the orderings between siblings matter, as illurstrated in Figure 2.

Figure 2 Two plane increasing trees on $7$ vertices which are distinct

Based on the work of Bergeron, Flajolet, and Salvy in their landmark paper [1], one may consider various enumeration problems of colored increasingly labeled trees whose vertices have a number of color options based on their down degrees (the number of children of a vertex). In preparation for this, we first introduce some basic definitions and previous work on combinatorial classes and their generating functions in Section 2.

These essential ideas allow us to use generating functions to study increasing trees with restricted heights and study various interesting statistics in Section 3.

From there, we move on to consider colored increasing binary trees. Some of their counting sequences appear to coincide with some previously known sequences, with connections to a number of interesting concepts, including: alternating permutations, Euler and Bernoulli polynomials, zigzag numbers, trigonometric functions, Fourier transform of a square wave, quantum algebras, integrals over and in n-dimensional hypercubes and over Green functions [4,9], and generalized tangent numbers [8]. The counting sequences are justified through both generating functions and combinatorial arguments, and generalized for $k$ -ary trees in Section 4.

We then shift our attention to colored recursive trees in Section 5, where similar analysis through generating functions is shown, followed by combinatorial arguments. In particular, the enumeration of $(k + 1)$ -colored plane recursive trees (to be defined later) leads to $(3 n - 4)!!!$ , closely related to the previous results of $(n - 1)!;$ for standard recursive trees and $(2 n - 1)!!$ for plane recursive trees. A generalization is also discussed here.

Lastly, in Section 2, we briefly discuss the counting sequences introduced from this work. Some of the data is shown in the appendix.

2. Preliminaries

The general definitions and techniques follow those developed in [1] and [3]. A combinatorial class is a finite set along with a size function where every object has a size that is a non-negative integer and the number of objects of any size is finite. The generating function of a combinatorial class $B$ would be denoted by $B (z)$ . And we say two combinatorial classes $A$ and $B$ are isomorphic (or have a class isomorphism) if we have that $A (z) = B (z)$ for their generating functions. The following definition is also crucial to our work that follows.

Definition 2.1. ([1]) The degree function of an increasing tree with

n

being the set of possible degrees for a vertex in the tree and

s

being the number of possible colors for said vertices of degree

n

are as follows:

Plane: $ϕ (u) = \sum_{n \geq 0} s_{n} u^{n} .$
Non-plane: $ϕ (u) = \sum_{n \geq 0} s_{n} \frac{u^{n}}{n!} .$

The following theorem was given in [1]. Here, we provide details of the proof using symbolic notations developed in [3]. This approach is generalized to present some of the observations shown in this paper. With the given degree functions, the increasing trees are described by the combinatorial class $I = Z^{} ⋆ ϕ (I)$ (where $Z$ is the root of such a tree) with generating function $I (z)$ .

Theorem 2.2. The generating function

I (z)

for increasing trees with degree function

ϕ (u)

satisfies

\int_{0}^{I (z)} \frac{1}{ϕ (u)} du = z .

Proof. It is defined by Flajolet and Sedgewick in [3] that $A = B ⋆ C$ is defined by $A_{n} = \sum_{n_{1} + n_{2}} (\binom{n}{n_{1}, n_{2}}) B_{n_{1}} C_{n_{2}} .$ It is then clear that by restricting our smallest element in to be in $B,$ denoted by $B^{},$ we obtain $A_{n} = \sum_{k = 1}^{n} (\binom{n - 1}{k - 1}) B_{k} C_{n - k} = \frac{1}{n} \sum_{k = 1}^{n} (\binom{n}{k}) k B_{k} C_{n - k} .$ So from the definition of an exponential generating function, $A (z) = \sum_{n \geq 0} \frac{z^{n}}{n!} \frac{1}{n} \sum_{k = 1}^{n} (\binom{n}{k}) k B_{k} C_{n - k} = \sum_{n \geq 0} \frac{z^{n}}{n} \sum_{k = 1}^{n} \frac{k}{k! (n - k)!} B_{k} C_{n - k} .$ We then take the derivative, $\begin{aligned} A^{'} (z) & = \sum_{n \geq 0} z^{n - 1} \sum_{k = 1}^{n} \frac{k}{k! (n - k)!} B_{k} C_{n - k} \\ = \sum_{n \geq 0} \sum_{k = 1}^{n} \frac{z^{k - 1} k}{k!} B_{k} \frac{z^{n - k}}{(n - k)!} C_{n - k} \\ = B_{1} C_{0} + B_{1} C_{1} z + B_{2} C_{0} z + B_{1} C_{2} \frac{z^{2}}{2!} + B_{2} C_{1} z^{2} + \frac{z^{2}}{2} B_{3} C_{0} + \dots \\ = (B_{1} + z B_{2} + \frac{z^{2}}{2} B_{3} + \dots) (C_{0} + z C_{1} + \frac{z^{2}}{2} C_{2} + \dots) \\ = \partial_{z} B (z) \cdot C (z) . \end{aligned}$

We now apply this to $I = Z^{} ⋆ ϕ (I),$ $I^{'} (z) = \partial_{z} z \cdot ϕ (I (z)) = ϕ (I (z)) .$ Therefore, $\begin{aligned} \frac{I^{'} (z)}{ϕ (I (z))} & = 1 \\ \int_{0}^{z} \frac{I^{'} (z)}{ϕ (I (z))} d z & = z \\ \int_{0}^{I (z)} \frac{1}{ϕ (u)} d u & = z, \end{aligned}$ where $u = I (z) .$

As an example, applying Theorem 2.2 to the degree function $ϕ (u) = \sum_{n = 0}^{\infty} \frac{u^{n}}{n!} = e^{u},$ we have $\int_{0}^{R (z)} e^{- u} d u = z,$ Therefore, we obtain $R (z) = \ln (\frac{1}{1 - z})$ and ${(n - 1)!}$ as the counting sequence for non-plane increasingly labeled recursive trees. This can also be seen through simple recursive combinatorial argument where the vertex with label $n$ can be a child to any of the vertices labeled 1 through $n - 1$ .

3. Increasing trees with restricted height

We may apply the developed approach to increasing trees with restricted heights. We will denote the class of all increasing trees with height less than or equla to $h$ by $I_{h}$ . Then, $I_{h} = Z^{} ⋆ ϕ (I_{h - 1})$ as the height of the subtree formed by the children of the root is one less than that of the original tree. Following similar arguments to the proof of Theorem 2.2, we have the following based on the fact that $I_{h}^{'} (z) = ϕ (I_{h - 1} (z))$ .

Proposition 3.1. The generating function for the class of increasing trees with restricted height is,

I_{h} (z) = \int_{0}^{z} ϕ (I_{h - 1} (t)) d t .

As an example, Proposition 3.1 can be used to calculate the generating function for plane binary increasing trees whose height is less than or equal to three.

$\begin{aligned} B_{3} (z) & = \int_{0}^{z} B_{2}^{2} (t) + 1 d t \\ = \int_{0}^{z} [1 + {(\int_{0}^{t} B_{1}^{2} (u) + 1 d u)}^{2}] d t \\ = \int_{0}^{z} [1 + {(\int_{0}^{t} 1 + {(\int_{0}^{u} B_{0}^{2} (x) + 1 d x)}^{2} d u)}^{2}] d t \\ = \int_{0}^{z} [1 + {(\int_{0}^{t} 1 + {(\int_{0}^{u} 2 d x)}^{2} d u)}^{2}] d t \\ = \int_{0}^{z} [1 + {(\int_{0}^{t} 1 + 4 u^{2} d u)}^{2}] d t \\ = \int_{0}^{z} [1 + {(t + \frac{4}{3} t^{3})}^{2}] d t \\ = \int_{0}^{z} [1 + t^{2} + \frac{8}{3} t^{4} + \frac{16}{9} t^{6}] d t \\ = \frac{16}{63} z^{7} + \frac{8}{15} z^{5} + \frac{1}{3} z^{3} + z . \end{aligned}$

In general, we may apply Proposition 3.1 to obtain various statistics related to binary increasing trees. In Figure 3, we plot the probability of trees of a given order has restricted height $\leq h$ . From left to right each curve corresponds to a particular bound from zero to eleven.

Figure 3 Probabilities of trees with restricted height

We may also use our data to identify three thresholds where the percentage of non-plane binary increasing trees of restricted height passes or achieves $25 %,$ $50 %,$ and $75 %$ of the total number of non-plane binary increasing trees. We give this information in Table 1.

Table 1 The order where each height exceeds or meets the threshold values
height	order	probability
$h \leq 6$	$17$	$28.3 %$
$h \leq 7$	$24$	$25.2 %$
$h \leq 8$	$32$	$27 %$
$h \leq 9$	$44$	$25 %$
$h \leq 10$	$58$	$26.3 %$
$h \leq 11$	$78$	$25.3 %$
$h \leq 6$	$14$	$52.1 %$
$h \leq 7$	$19$	$51.6 %$
$h \leq 8$	$25$	$53.7 %$
$h \leq 9$	$34$	$51.5 %$
$h \leq 10$	$45$	$51.6 %$
$h \leq 11$	$60$	$50.6 %$
$h \leq 6$	$11$	$79 %$
$h \leq 7$	$15$	$76.4 %$
$h \leq 8$	$20$	$75.6 %$
$h \leq 9$	$26$	$76.5 %$
$h \leq 10$	$34$	$76.6 %$
$h \leq 11$	$45$	$75.7 %$

Given the order of the increasing binary trees, we may also study the distribution of them according to different values. As examples, we consider trees of order 31, 61, and 121 respectively in Figure 4. Note that the final column represents trees with height $\geq 12$ .

Figure 4 Trees of order 31 (left), 61 (middle) and 121 (right)

Lastly, in Figure 5, we present the probability of a non-plane binary increasing tree of order $n$ having height exactly $h$ .

4. Colored binary trees and $k$ -ary trees

We move on to study general theories and specific combinatorial argument related to colored increasing trees.

First of all, We say an increasing binary tree is $(a; b)$ -colored if there exist $a$ colors for vertices of down degree $0$ and $b$ colors for nodes of down degree $2$ . We begin by presenting the generating functions for $(a; b)$ -colored increasing binary trees.

Proposition 4.1. Let

B_{p}

be the combinatorial class for the

(a; b)

-colored plane increasing binary tree. The generating function for the

(a; b)

-colored plane increasing binary tree is

$B_{p} (z) = \frac{\sqrt{a}}{\sqrt{b}} \tan (z \sqrt{a b}) .$

Proof. From Definition 2.1 we obtain the degree function $ϕ (u) = \sum_{n} s_{n} u^{n} .$ With $n = {0, 2}$ and $s_{0} = a, s_{2} = b$ , we have $ϕ (u) = \sum_{n} s_{n} u^{n} = a + b u^{2} .$

By Theorem 2.2, we have $\begin{aligned} \int_{0}^{B_{p} (z)} \frac{1}{a + b u^{2}} du & = z \\ \frac{1}{\sqrt{a b}} \arctan (\frac{\sqrt{b}}{\sqrt{a}} B_{p} (z)) & = z \\ \arctan (\frac{\sqrt{b}}{\sqrt{a}} B_{p} (z)) & = z \sqrt{a b} \\ \frac{\sqrt{b}}{\sqrt{a}} B_{p} (z) & = \tan (z \sqrt{a b}) \\ B_{p} (z) & = \frac{\sqrt{a}}{\sqrt{b}} \tan (z \sqrt{a b}) . \end{aligned}$

Similarly, for non-plane trees we have the following.

Proposition 4.2. Let

B_{n p}

be the class for the

(a; b)

-colored non-plane increasing binary tree. The generating function for

B_{n p}

is,

$B_{n p} (z) = \frac{\sqrt{2 a}}{\sqrt{b}} \tan (z \frac{\sqrt{a b}}{\sqrt{2}}) .$

Proof. We obtain the degree function in a similar way,

$ϕ (u) = \sum_{n} s_{n} \frac{u^{n}}{n!} = a + \frac{b}{2} u^{2} .$

The proof proceeds from Theorem 2.2 giving us,

$\begin{aligned} \int_{0}^{B_{p} (z)} \frac{1}{a + \frac{b}{2} u^{2}} du & = z \\ \frac{\sqrt{2}}{\sqrt{a b}} \arctan (\frac{\sqrt{b}}{\sqrt{2 a}} B_{n p} (z)) & = z \\ \arctan (\frac{\sqrt{b}}{\sqrt{2 a}} B_{n p} (z)) & = z \frac{\sqrt{a b}}{\sqrt{2}} \\ \frac{\sqrt{b}}{\sqrt{2 a}} B_{n p} (z) & = \tan (z \frac{\sqrt{a b}}{\sqrt{2}}) \\ B_{n p} (z) & = \frac{\sqrt{2 a}}{\sqrt{b}} \tan (z \frac{\sqrt{a b}}{\sqrt{2}}) . \end{aligned}$

From the above proofs, it is easy to see that the generating functions for $(a; 2 b)$ -colored non-plane increasing binary trees is $\frac{\sqrt{2 a}}{\sqrt{2 b}} \tan (z \frac{\sqrt{2 a b}}{\sqrt{2}}) = \frac{\sqrt{a}}{\sqrt{b}} \tan (z \sqrt{a b}),$ exactly that of the $(a; b)$ -colored plane increasing binary trees, leading us to the following result as an immediate consequence. We will provide a combinatorial proof for this connection.

Theorem 4.3. The

(a; b)

-colored plane binary tree is equinumerous with the

(a; 2 b)

-colored non-plane binary tree.

Proof. We start with the simple case of $a = b = 1$ . For any increasing binary tree, we know that we can determine the number of trees on $n$ vertices by the ways in which we can rearrange the labelings and the number of children for each vertex. If this tree is plane then we also must consider the number of ways in which we can rearrange the branches. This of course only applies to vertices with a down degree of $2$ , where each vertex has $2$ possible ways in which we can rearrange the branches. In a non-plane binary tree, we have no such consideration though. However, if we are to color the vertices of down degree $2$ with $2$ possible colors, then we now have the same consideration, except instead of rearranging the branches we must consider the ways in which we could color the vertex. This establishes the bijection between the plane increasing binary tree and the $(1; 2)$ -colored non-plane increasing binary tree.

Similarly, in the more general case: in the plane tree we have $b$ colors for each node with $2$ children (hence 2 ways to arrange them) and in the non-plane case $2 b$ colors. Once again though we can arrange the branches in the plane case in $2$ possible ways for each node of down degree $2$ this combined with the $b$ colors gives $2 b$ possible considerations for each node with children. While in the non-plane case, we have $2 b$ considerations from the coloring and no considerations due to arranging the branches, which gives us just $2 b$ total. Thus we have an equal number of trees.

Example 4.4. Since the binary tree is plane by rearranging branches we generate distinct trees by rearranging our branches as shown in Figure 6.

However, in the case of the non-plane binary tree we see that same can not be said which we illustrate in Figure 7.

If we instead color the non-plane binary tree though we see that they are no longer equivalent as in Figure 8.

Figure 8 Colored non-plane binary tree case

This allows us to map them like in Figure 9 and Figure 10.

Figure 9 Between non-plane and plane binary trees: Example 1

Figure 10 Between non-plane and plane binary trees: Example 2

We can take this a step further, while no generating functions can be explicitly shown for $k$ -ary trees with $k > 2$ , the above combinatorial arguments apply to show the following more general statement. The proof, which we omit, follows exactly the same logic but noting that there are $k!$ ways to arrange the pending branches of each nonleaf vertex.

Theorem 4.5. The

(a; b)

-colored plane increasing

k

-ary tree is equinumerous with the

(a; (k!) b)

-colored non-plane increasing

k

-ary tree.

5. Colored recursive tree

We now move on to consider general trees with all possible down degrees allowed. First, we define a $f (k)$ -colored recursive tree to be a recursive tree where each vertex of down degree $k$ has $f (k)$ possible colors. Throughout this section we’ll consider different type of trees from different $f (k)$ functions. Recall the following important result from [1].

Theorem 5.1 ([1]).

Let $R_{p}$ denote the class of plane recursive trees. Then,

$R_{p} (z) = 1 - \sqrt{1 - 2 z} .$

5.1. $k!$ -colored recursive trees

For $k!$ -colored non-plane recursive trees, we have the following.

Proposition 5.2.Let

N_{n p}

be the combinatorial class for the

k!

-colored non-plane recursive tree. Then,

$N_{n p} (z) = R_{p} (z) .$

Proof. It is clear that degree function given by the $k!$ -colored non-plane recursive tree is,

$ϕ (u) = \sum_{n \geq 0} n! \frac{u^{n}}{n!} = \sum_{n \geq 0} u^{n} .$

The rest follows from the fact that this is the same degree function as that of the (non-colored) plane recursive trees.

It is not difficult to apply combinatorial arguments similar to the last section to justify that the plane recursive trees and $k!$ -colored non-plane recursive trees are equinumerous. We make a more general statement as follows.

Theorem 5.3. Let

T_{p}

be the class for some plane increasing trees and

T_{n p}

its non-plane counterpart. The number of elements in

T_{p}

is equinumerous with the number of elements in the

k!

-colored

T_{n p}

Proof. Starting from the set of non-plane trees we can generate the plane trees by multiplying by the number of ways in which we can arrange the branches of each vertex. This is the same as multiplying by $k!$ , the number of ways to permute $k$ children, for each vertex of down degree $k$ .

On the other hand, this is the same to let each vertex in the non-plane tree with down degree $k$ to have $k!$ possible colors.

5.2. $(a k + a)$ -colored recursive trees

First we consider the case $a = 1$ , the degree function is given by $ϕ (u) = \sum_{n = 0}^{\infty} (n + 1) u^{n} = \frac{1}{(u - 1)^{2}} .$

Letting $R$ be the combinatorial class for the $(k + 1)$ -colored plane recursive trees. Then, $\begin{aligned} \int_{0}^{R (z)} (u - 1)^{2} du & = z, \\ \frac{R (z)^{3}}{3} - R (z)^{2} + R (z) & = z, \\ \frac{R (z)^{3}}{3} - R (z)^{2} + R (z) - z & = 0. \end{aligned}$ Solving for $R (z)$ , we have $R (z) = (3 z - 1)^{\frac{1}{3}} + 1.$

This generating function coincides with that of the sequence A008544 in the Online Encyclopedia of Integer Sequences, where simple application of the general binomial coefficients yields $(3 n - 4)!!! := (3 n - 4) \cdot (3 n - 7) \dots 5 \cdot 2,$ as the counting sequence, below we provide a combinatorial proof for this fact.

Theorem 5.4. The number of

(k + 1)

-colored plane recursive trees is

(3 n - 4)!!!

Proof. Let $A_{n}$ be the number of such trees on $n$ vertices. Let $T$ be such a tree with $n - 1$ vertices and let $v \in T$ be an arbitrary vertex with down degree $k$ . It follows from our definition that $v$ has $(k + 1)$ different colors. We now append a new vertex $w$ to this one $v$ will now have $k + 2$ different colors and we may also place $w$ in $(k + 1)$ positions to generate a distinct tree with $n$ vertices, this is because changing the position of $w$ rearranges the branch which $w$ forms. So far we have that appending $w$ to $v$ generates $(k + 1) (k + 2)$ new trees of size $n$ . Dividing by $(k + 1)$ , the original number of color choices for $v$ , this gives us $(k + 2)$ new trees generated by appending $w$ to $v$ .

In order to consider all possible cases, we must sum $(k + 2)$ over all $k_{i}$ corresponding to each $v_{i} \in T$ as we could append $w$ to any vertex in $T$ . Since there are only $(n - 1)$ vertices in $T$ this gives $\sum_{i = 1}^{n - 1} k_{i} + 2,$ and it follows that $\sum_{i = 1}^{n - 1} k_{i} + 2 = 2 n - 2 + \sum_{i = 1}^{n - 1} k_{i}$ . Note that the sum of down degrees is the same as the total number of children, $n - 2$ .

Thus, $2 n - 2 + \sum_{i = 1}^{n - 1} k_{i} = 2 n - 2 + n - 2 = 3 n - 4,$ new trees generated by appending $w$ to $T$ . Hence $A_{n} = (3 n - 4) A_{n - 1} = (3 n - 4)!!!$ .

The above argument is illustrated in Figure 11.

Should one apply similar generating functions and/or combinatorial arguments to $(a k + a)$ -colored plane recursive trees, we have the followings.

Proposition 5.5. Let

A

be the combinatorial class for the

(a k + a)

-colored plane recursive tree, where

a \in N

. Then,

A (z) = (3 a z - 1)^{\frac{1}{3}} + 1.

Let ${A_{n}}$ be the counting sequence corresponding to the $(a k + a)$ -colored plane recursive trees, then $A_{n} = (3 n - 4)!!! a^{n}$

Indeed, if the number of color choices for each vertex is multiplied by a fixed value $a$ , then the total number of possible trees is multiplied by $a^{n}$ as there are $n$ vertices.

6. Conclusions

Applying the symbolic approach, we studied the generating functions corresponding to various classes of colored increasingly labelled trees. This approach allows us to study various statistics related to such trees with restricted heights, as well as colored analogues. Both computational data and combinatorial observations are presented.

References:

F. Bergeron, P. Flajolet, and B. Salvy. Varieties of increasing trees. In CAAP ’92. Springer Berlin Heidelberg, 1992, pages 24–48. https://doi.org/10.1007/3-540-55251-0_2.
R. Donaghey. Alternating permutations and binary increasing trees. Journal of Combinatorial Theory, Series A, 18(2):141–148, Mar. 1975. https://doi.org/10.1016/0097-3165(75)90002-3.
P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, Jan. 2009. https://doi.org/10.1017/cbo9780511801655.
A. Hodges and C. Sukumar. Bernoulli, Euler, permutations and quantum algebras. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463(2086):2401–2414, July 2007. https://doi.org/10.1098/rspa.2007.0001.
A. Meir and J. W. Moon. On the altitude of nodes in random trees. Canadian Journal of Mathematics, 30(5):997–1015, Oct. 1978. https://doi.org/10.4153/cjm-1978-085-0.
A. Meir and J. W. Moon. Recursive trees with no nodes of out-degree one. Congressus Numerantium, 66:49–62, 1988.
H. Prodinger. A bijection between phylogenetic trees and plane oriented recursive trees. arXiv preprint arXiv:1709.05966, 2017.
N. J. A. Sloane. A Handbook of Integer Sequences. Academic Press, 2014.
C. Sukumar and A. Hodges. Quantum algebras and parity-dependent spectra. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463(2086):2415–2427, July 2007. https://doi.org/10.1098/rspa.2007.0003.
J. Szymański. On a nonuniform random recursive tree. In North-Holland Mathematics Studies, Volume 144, pages 297–306. Elsevier, 1987.

[1] F. Bergeron, P. Flajolet, and B. Salvy. Varieties of increasing trees. In CAAP ’92. Springer Berlin Heidelberg, 1992, pages 24–48. https://doi.org/10.1007/3-540-55251-0_2.

[2] R. Donaghey. Alternating permutations and binary increasing trees. Journal of Combinatorial Theory, Series A, 18(2):141–148, Mar. 1975. https://doi.org/10.1016/0097-3165(75)90002-3.

[3] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, Jan. 2009. https://doi.org/10.1017/cbo9780511801655.

[4] A. Hodges and C. Sukumar. Bernoulli, Euler, permutations and quantum algebras. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463(2086):2401–2414, July 2007. https://doi.org/10.1098/rspa.2007.0001.

[5] A. Meir and J. W. Moon. On the altitude of nodes in random trees. Canadian Journal of Mathematics, 30(5):997–1015, Oct. 1978. https://doi.org/10.4153/cjm-1978-085-0.

[6] A. Meir and J. W. Moon. Recursive trees with no nodes of out-degree one. Congressus Numerantium, 66:49–62, 1988.

[7] H. Prodinger. A bijection between phylogenetic trees and plane oriented recursive trees. arXiv preprint arXiv:1709.05966, 2017.

[8] N. J. A. Sloane. A Handbook of Integer Sequences. Academic Press, 2014.

[9] C. Sukumar and A. Hodges. Quantum algebras and parity-dependent spectra. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463(2086):2415–2427, July 2007. https://doi.org/10.1098/rspa.2007.0003.

[10] J. Szymański. On a nonuniform random recursive tree. In North-Holland Mathematics Studies, Volume 144, pages 297–306. Elsevier, 1987.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing