Fig. 1. A planted plane tree with root label Abstract A note on plane trees with decreasing labels Tsun-Ming Cheung, Luc Devroye, and Marcel Goh School of Computer Science, McGill University Abstract. This note derives asymptotic upper and lower bounds for the number of planted plane trees on n nodes assigned labels from the set \{1,2,\ldots,k\} with the restriction that on any path from the root to a leaf, the labels must strictly decrease. We illustrate an application to calculating the largest eigenvalue of the adjacency matrix of a tree. Keywords. Planted plane trees, decreasing labels, eigenvalues of trees. Mathematics Subject Classification. 05C05, 05C30, 05C50. In this note, we count the number of planted plane trees (also sometimes called ordered trees ) on n nodes, each node is given a label from the set \{1,2,\ldots,k\} , and labels must strictly decrease on any path from the root to a leaf. Let G_{n,k} denote this count for given positive integers n and k . It is clear that G_{1,1}=1 and G_{n,1}=0 for all n\geq 2 . Then, letting C(n) denote the set of all compositions of n , we have the recurrence formula G_{n,k}=G_{n,k-1}+\sum_{S\in C(n-1)}\prod_{s\in S}G_{s,k-1} [formula] for k\geq 2 . The first term, k , corresponds to the number of labellings that do not use the label k . For the second term, the root label must be k , the children of the root have subtrees with a total of n-1 nodes, and each subtree must only use labels from \{1,2,\ldots,k-1\} . The sequence G_{n,k} has two parameters, which suggests the use of a bivariate generating function in its analysis (see, e.g., [12] for a detailed account of methods related to multivariate generating functions). However we found that the nature of our specific recurrence made it easiest to work with a sequence of single-variable generating functions instead. For k\geq 1 , let G_{k}(z) be the generating function G_{k}(z)=\sum_{n=0}^{\infty}G_{n,k}z^{n}. Immediately we see that G_{1}(z)=z , and from the recurrence ( 1 ), we have G_{k}(z)=G_{k-1}(z)+{z\over 1-G_{k-1}(z)} [formula] for k\geq 2 . For any fixed k , the coefficients G_{n,k} of G_{k}(z) are nonnegative integers, so by Pringsheim’s theorem [4], if the radius of convergence of G_{k}(z) is R_{k} , then R_{k} is a singularity of the function G_{k}(z) . From the formula ( 2 ), it is clear that any pole of G_{k-1}(z) as well as any solution z to G_{k-1}(z)=1 is a pole of G_{k}(z) . For convenience, we define S_{k}(z)=1-G_{k}(z) . The functions S_{k}(z) satisfy the recurrence S_{k}(z)=S_{k-1}(z)-{z\over S_{k-1}(z)}, [formula] with S_{1}(z)=1-z . We define z^{*}_{k} to be the smallest positive real root of S_{k}(z) ; hence we must have S_{k}(z)>0 for z\in[0,z^{*}_{k}] . Furthermore, the formula ( 3 ) implies that S_{k}(z)\leq S_{k-1}(z) for z\in[0,z^{*}_{k}] , so z^{*}_{k} is a nonincreasing sequence of positive numbers. We now give a lower bound for z^{*}_{k} and show that S_{k}(z) is small at a point close to this lower bound. Lemma 1 For every k\geq 1 , z^{*}_{k}\geq k-\sqrt{k^{2}-1} [formula] and S_{k}\biggl({1\over 2k}\biggr)\leq\biggl({1\over 4k}\biggr)^{1/4}. [formula] Proof. Squaring both sides of ( 3 ) yields S_{k}(z)^{2}-S_{k-1}(z)^{2}=-2z+{z^{2}\over S_{k-1}(z)^{2}}, [formula] and by telescoping, we have \eqalign{S_{k}(z)^{2}&=(1-z)^{2}+\sum^{k}_{j=2}\bigl(S_{j}(z)^{2}-S_{j-1}(z)\bigr)^{2}\cr&=(1-z)^{2}-2(k-1)z+\sum^{k}_{j=2}{z^{2}\over S_{j-1}(z)^{2}}\cr&=1-2kz+z^{2}+\sum^{k-1}_{j=1}{z^{2}\over S_{j}(z)^{2}}.} [formula] Thus the lower bound S_{k}(z)^{2}\geq 1-2kz+z^{2} is immediate, and since 1-2kz+z^{2} is positive for 0\leq z0, [formula] the above limit is finite. This means that z_{k-1}^{*} is a pole of order 1 of the function G_{k}(z) . Letting \alpha_{k}=1/z_{k-1}^{*} , by a standard result on the coefficient asymptotics of rational functions, we have G_{n,k}={c_{k}{\alpha_{k}}^{n}}\bigl(1+o(1)\bigr), [formula] where c_{k} is a constant depending on k only. The claimed bounds on \alpha_{k} follow from the two previous lemmas. We also note the following explicit upper bound. As G_{k}(z_{k}^{*})=1 , we immediately have G_{n,k}\leq\left({1\over z^{*}_{k}}\right)^{n}=\left(\alpha_{k+1}\right)^{n}. This is weaker than ( 17 ), but only slightly so, as \alpha_{k+1}/\alpha_{k}\to 1 as k\to\infty . The regular leaning tree of order k . Consider the sequence T_{0},T_{1},T_{2},\ldots of trees defined recursively as follows. Let T_{0} be a single root node with no children, and for k\geq 1 , we define T_{k} to be the tree with a root node having k children whose subtrees are T_{k-1},T_{k-2},\ldots,T_{0} . We shall call T_{k} the regular leaning tree of order k . For all k\geq 0 , the tree T_{k} has 2^{k} nodes. The following algorithm gives a mapping from the set of closed walks of length 2n starting at the root of T_{k} and n -node planted plane trees with root label k+1 and decreasing labels. Algorithm P ( Build planted plane tree ).  Given a closed walk \sigma=(u_{0},u_{1},\ldots,u_{2n}) of length 2n in T_{k} , this algorithm outputs a planted plane tree labelled with positive integers. P1. [Initialize.] Set i\mathchar 12832\relax 0 and initialize the tree P with a root node v and set \hbox{\tentt LABEL}(v)\mathchar 12832\relax k+1 . P2. [Child.] If u_{i+1} is the parent of u_{i} , go to step P3. Otherwise, suppose that u_{i+1} is the root of a subtree isomorphic to T_{j} for some j<\hbox{\tentt LABEL}(v) . Append a child with label j+1 to v and update v to point to this child. Go to step P4. P3. [Parent.] Set v\mathchar 12832\relax\hbox{\tentt PARENT}(v) . P4. [Loop.] Increment i by one. If i<2n , go to step P2; otherwise terminate the algorithm with the tree P as output. The root of the output planted plane tree has label k+1 , and every time we move downward in T_{k} along the path \sigma and encounter the root of T_{j} for some j\leq k , we append a node with label j+1 . This implies that the output of Algorithm P is a planted plane tree with decreasing labels and root label k+1 . We also know that this output tree has n+1 nodes, since we start with one root node, and in the walk \sigma , half of the 2n edges must go down in the tree and half must go up (to return to the root), and we add a node to P when (and only when) going down. The tree P is built up in depth-first preorder, so it is easy to write an algorithm that recovers the walk from a tree P output by Algorithm P. Algorithm W ( Build walk in T_{k} ).  Given a planted plane tree P with decreasing labels and root label k+1 , we build a walk \sigma starting at the root in T_{k} . Suppose we have a function \hbox{\tentt NEXT}(v) of getting the node that follows a given node v\in P in a depth-first traversal of P (in this traversal, nodes may be visited multiple times). W1. [Initialize.] Let u_{0} be the root of T_{k} . Set i\mathchar 12832\relax 0 and let v be the root of P . W2. [Child.] Let w\mathchar 12832\relax\hbox{\tentt NEXT}(v) . If w is the parent of v , go to step W3. Otherwise, let u_{i+1} be the child of u_{i} that is the root of the subtree isomorphic to T_{j} , where j=\hbox{\tentt LABEL}(w)-1 . Go to step W4. W3. [Parent.] Set u_{i+1}\mathchar 12832\relax\hbox{\tentt PARENT}(u) . W4. [Loop.] Set v\mathchar 12832\relax w and increment i by one. (An invariant we have maintained is that u_{i} is the root of a subtree isomorphic to T_{j} , where j=\hbox{\tentt LABEL}(v)-1 . This makes step W2 possible in the next iteration.) If i<2n , go to step W2; otherwise, terminate the algorithm with output \sigma=(u_{0},u_{1},\ldots,u_{2n}) . An example of a tree P and its corresponding walk in T_{k} is illustrated in Fig. 1. The parallel structures of Algorithms P and W make it clear that if Algorithm P terminates with output P upon being given input \sigma , then Algorithm W returns the walk \sigma upon the input P . We have thus furnished a bijective proof of the following theorem. Theorem 4 Let n and k be positive integers. The number W_{2n}(T_{k}) of closed paths in T_{k} of length 2n that begin and end at the root is equal to the number G_{n+1,k+1}-G_{n+1,k} of (n+1) -node planted plane trees with decreasing labels and root label equal to k+1 . The top eigenvalue of a regular leaning tree. Let \Gamma=(V,E) be a graph, let A=A(\Gamma) be its adjacency matrix, and let \lambda_{1}(A) denote the largest eigenvalue of A . By the trace method, we have \eqalign{\lambda_{1}(A)&=\lim_{n\to\infty}\Bigl(\mathop{\hbox{\tenrm tr}}\nolimits\bigl(A^{2n}\bigr)\Bigr)^{1/2n}\cr&=\lim_{n\to\infty}\Bigl(\max_{v\in V}W_{2n}(v,\Gamma)\Bigr)^{1/2n},\cr&=\lim_{n\to\infty}\Bigl(\min_{v\in V}W_{2n}(v,\Gamma)\Bigr)^{1/2n},\cr} [formula] where W_{2n}(v,\Gamma) denotes the number of closed walks of length 2n in \Gamma starting at the vertex v . It is well known that if \Gamma=T is a tree and A is its adjacency matrix, then the largest eigenvalue \lambda_{1}(A) of A satisfies \sqrt{\Delta}\leq\lambda_{1}(A)\leq 2\sqrt{\Delta-1}, [formula] where \Delta is the maximum vertex degree of T . (The lower bound is trivial and the upper bound is a result of D. Stevanović [13].) Theorems 3 and 4 together tell us that largest eigenvalue of the adjacency matrix of a leaning tree of order k (which has maximum vertex degree k+1 ) does not tend towards either of these bounds as k\to\infty . Lemma 5 Let k\geq 1 and let A_{k} denote the adjacency matrix of the regular leaning tree T_{k} . Then the largest eigenvalue \lambda_{1}(A_{k}) is \sqrt{2k+o(k)} . The Ulam–Harris number. We can extend the above result to arbitrary trees as follows. We give the root the label 1 , and for any node with label r and s children, we label the children r+1,r+2,\ldots,r+s . We define the Ulam–Harris number \mathop{\hbox{\ninerm UH}}\nolimits(T) of a planted plane tree T to be the maximum label in the tree. (There is a standard notion of the Ulam–Harris labelling of a tree (see, e.g., Section 6 of [5]), in which one assigns a vector of positive integers to each node. Our Ulam–Harris number is the maximum sum of coordinates, taken over all Ulam–Harris labels in the tree.) For an unordered tree T , we can let \mathop{\hbox{\ninerm UH}}\nolimits(T) be the minimum of \mathop{\hbox{\ninerm UH}}\nolimits(T^{\prime}) over all planted plane trees T^{\prime} obtained from T by choosing orderings for the children of each node. Fig. 2. A planted plane tree with Ulam–Harris number equal to 5 . Theorem 6 Let T be a rooted unordered tree, and let A be the adjacency matrix of T . Then \lambda_{1}(A)\leq\lambda_{1}\bigl(A_{\mathop{\hbox{\sevenrm UH}}\nolimits(T)-1}\bigr) , where A_{\mathop{\hbox{\sevenrm UH}}\nolimits(T)-1} is the adjacency matrix of the regular leaning tree of order \mathop{\hbox{\ninerm UH}}\nolimits(T)-1 . Proof. Consider T as a labelled planted plane tree, with maximum label \mathop{\hbox{\ninerm UH}}\nolimits(T) . Replace each label j with \mathop{\hbox{\ninerm UH}}\nolimits(T)-j+1 . Then the root has label \mathop{\hbox{\ninerm UH}}\nolimits(T) , all labels are positive and decreasing both as one descends in the tree, and as one goes from left to right among siblings. Furthermore, the new label of each node is strictly greater than the number of children it has, so we can embed T into the regular leaning tree T_{\mathop{\hbox{\sevenrm UH}}\nolimits(T)-1} , and the claim follows. Let T be a tree with maximum vertex degree \Delta and adjacency matrix A . Since a node and its children must all have different labels, we must have \mathop{\hbox{\ninerm UH}}\nolimits(T)\geq\Delta ; the regular leaning tree of order k attains this bound with equality. Lemma 5 and Theorem 6 together supply an upper bound of roughly \sqrt{2\mathop{\hbox{\ninerm UH}}\nolimits(T)-2} on \lambda_{1}(A) . In the scenario where \mathop{\hbox{\ninerm UH}}\nolimits(T)+1<2\Delta (as in Fig. 2, for instance), this improves upon Stevanović’s bound of 2\sqrt{\Delta-1} . Related work. In this paper we have considered trees with decreasing labels, but in the literature it has been somewhat more common to count trees with increasing labels (by reflecting the values of the nodes, there are exactly as many increasing trees with maximum label k as there are decreasing ones). There is a classical bijection between permutations of \{1,\ldots n\} and increasing binary trees on n nodes using each label from 1 through n exactly once. A 2020 paper of O. Bodini, A. Genitrini, B. Gittenberger, and S.Wagner [2] relaxed the stipulation that all the labels 1 through n must appear, requiring instead that for some 1\leq k\leq n , all the labels 1 through k must appear (labels must still strictly increase down the tree). A later paper of O. Bodini, A. Genitrini, M. Naima, and A. Singh describes a more general approach that applies to more families of trees [3]. In 1987, J. Blieberger counted the number of Motzkin trees with labels that increase, but not necessarily strictly [1]. R. Kemp showed in 1993 that the planted plane trees labelled similarly are in bijection with monotonically extended binary trees [7]. In 2011, S. Janson, M. Kuba, and A. Panholzer drew a link between generalized Stirling permutations and k -ary trees with (strictly) increasing labels [6]. A generalization of labelled trees, in which nodes can receive multiple labels, was introduced in 2016 by M. Kuba and A. Panholzer, and this generalization is shown to imply various hook-length formulas for trees [10]. Other authors have considered the average shape [8] and the degree distribution [9] of various tree families with increasing labels. The expectation and variance of the size of the ancestor tree as well as the Steiner distance of increasingly labelled trees were determined by K. Morris in 2004 [11]. Acknowledgements. We thank Ari Blondal, Gábor Lugosi, and Steve Melczer for stimulating discussions and helpful suggestions. The second and third authors are funded by the Natural Sciences and Engineering Research Council of Canada.