A note on plane trees with decreasing labels

Imagine you are an architect designing a very specific kind of family tree, but with a twist: everyone must be shorter than their parents.

That's the core idea of this paper. The authors (Cheung, Devroye, and Goh) are counting how many ways you can build these "downward-growing" trees under strict rules. Here is a breakdown of their work using simple analogies.

1. The Rules of the Game

Think of a Planted Plane Tree as a family tree where:

The Root: The top ancestor.
The Children: The branches coming off a node.
The Order: It matters which child is on the left and which is on the right (like a line of people waiting for a bus).
The Labels: Every person gets a number (like a height or an ID).
The Golden Rule: If you walk from the top (root) down to any leaf (the end of a branch), the numbers must get smaller at every step. You can't have a child with a bigger number than their parent.

The authors wanted to answer a simple question: If we have a tree with $n$ people and we can only use numbers from 1 to $k$ , how many different valid trees can we build?

2. The Mathematical "Recipe"

To solve this, the authors didn't just count trees one by one (which would take forever). Instead, they used a mathematical tool called a Generating Function.

Think of a generating function as a magic vending machine.

You put in a number $n$ (the size of the tree).
The machine spits out the exact count of valid trees for that size.
The authors found a recursive "recipe" (a formula) that tells the machine how to calculate the count for label $k$ based on the count for label $k-1$ .

They discovered that as the trees get huge (as $n$ goes to infinity), the number of possible trees grows at a predictable speed. They calculated exactly how fast this speed is, giving us a "growth rate" formula.

3. The "Leaning Tree" Analogy

To understand the deeper meaning, the authors invented a special character: The Regular Leaning Tree.

Imagine a tree that is perfectly symmetrical but leans heavily to one side.

Order 0: Just a single root.
Order 1: A root with one child (which is an Order 0 tree).
Order 2: A root with two children: one is an Order 1 tree, the other is an Order 0 tree.
Order $k$ : A root with $k$ children, which are the trees of Order $k-1$ , $k-2$ , all the way down to Order 0.

This structure is like a Russian nesting doll where each layer contains a slightly smaller version of itself, plus a tiny one.

4. The Magic Walk (The Bijection)

The most clever part of the paper is a "bridge" they built between two seemingly unrelated things:

Walking on the Leaning Tree: Imagine a robot walking on this special Leaning Tree. It starts at the root, takes $2n$ steps, and must return to the root.
Building the Labelled Tree: Imagine building a standard family tree with the "decreasing number" rule.

The authors wrote an algorithm (a set of instructions) that acts like a translator.

If you give the translator a walk on the Leaning Tree, it builds a unique labelled family tree.
If you give it a labelled family tree, it traces the exact walk on the Leaning Tree.

This proves that counting these specific walks is exactly the same as counting these specific trees. It's like proving that the number of ways to arrange a deck of cards is the same as the number of ways to shuffle them, just by showing you can turn one into the other without losing any information.

5. Why Does This Matter? (The "Vibe Check" of a Tree)

The paper ends with a cool application: Eigenvalues.

In math and physics, every network (like a tree) has a "largest eigenvalue." You can think of this as the tree's "vibe" or "energy level."

A tree with a high "vibe" is very connected and active.
A tree with a low "vibe" is more isolated.

Usually, mathematicians guess a tree's energy level based on how many branches the busiest node has (its degree). But the authors found that for these specific "Leaning Trees," the energy level is actually lower than the standard guesses would suggest.

They showed that the energy level is roughly the square root of twice the number of branches ( $\sqrt{2k}$ ). This is a more precise way to measure how "active" a complex tree structure really is.

Summary

The Problem: Counting trees where numbers get smaller as you go down.
The Method: Using a "magic vending machine" (generating functions) and a special "Leaning Tree" structure.
The Breakthrough: Proving that walking on a Leaning Tree is mathematically identical to building a decreasing-labeled tree.
The Result: A precise formula for how fast these trees grow and a better way to measure the "energy" (eigenvalue) of complex tree networks.

In short, they took a complicated puzzle about tree shapes and numbers, solved it by finding a hidden symmetry with a "leaning" tree, and used that to measure the fundamental energy of tree networks.

1. Problem Statement

The authors investigate the combinatorial enumeration of planted plane trees (also known as ordered trees) with specific labeling constraints.

Structure: A planted plane tree on $n$ nodes.
Labeling: Each node is assigned a label from the set $\{1, 2, \dots, k\}$ .
Constraint: Labels must strictly decrease along any path from the root to a leaf.
Objective: Determine the asymptotic behavior of $G_{n,k}$ , the number of such trees for fixed $k$ as $n \to \infty$ .
Secondary Objective: Apply these counting results to estimate the largest eigenvalue ( $\lambda_1$ ) of the adjacency matrix of specific tree structures, specifically "regular leaning trees."

2. Methodology

The paper employs a combination of generating functions, complex analysis, and bijective combinatorics.

A. Generating Functions and Recurrence Relations

The authors define $G_{n,k}$ as the count of valid trees. They derive a recurrence relation based on the root label:
$G_{n,k} = G_{n,k-1} + \sum_{S \in C(n-1)} \prod_{s \in S} G_{s, k-1}$
where $C(n-1)$ is the set of compositions of $n-1$ .

Translation to Generating Functions: They introduce the bivariate generating function approach but simplify it to a sequence of single-variable generating functions $G_k(z) = \sum_{n=0}^\infty G_{n,k} z^n$ .
Recurrence: The functions satisfy:
$G_k(z) = G_{k-1}(z) + \frac{z}{1 - G_{k-1}(z)}$
with $G_1(z) = z$ .
Singularity Analysis: To find the asymptotic growth of coefficients $G_{n,k}$ , the authors analyze the radius of convergence $R_k$ of $G_k(z)$ . By Pringsheim's theorem, the dominant singularity is a positive real pole. They define $S_k(z) = 1 - G_k(z)$ and study the smallest positive root $z^*_k$ of $S_k(z) = 0$ . The growth rate is determined by $\alpha_k = 1/z^*_k$ .

B. Asymptotic Bounds via Lemmas

The authors establish bounds for $z^*_k$ to determine the asymptotic base $\alpha_k$ :

Lemma 1 (Lower Bound): Proves $z^*_k \ge k - \sqrt{k^2-1}$ and provides an upper bound for $S_k(1/2k)$ .
Lemma 2 (Upper Bound): Uses the concavity of $S_k(z)$ to prove $z^*_k \le \frac{1}{2k}(1 - (4k)^{-1/4})$ .
Result: These lemmas allow the derivation of the asymptotic growth rate $\alpha_k \approx 2k$ for large $k$ .

C. Bijective Proof (Algorithm P and W)

To connect the tree counting problem to graph theory (specifically closed walks), the authors define a regular leaning tree $T_k$ :

$T_0$ is a single root.
$T_k$ has a root with $k$ children, whose subtrees are $T_{k-1}, T_{k-2}, \dots, T_0$ .
The Bijection: They construct two algorithms, P (Tree from Walk) and W (Walk from Tree), establishing a bijection between:
1. Closed walks of length $2n$ starting at the root of $T_k$ .
2. Planted plane trees with $n+1$ nodes, decreasing labels, and root label $k+1$ .
This bijection proves that the number of such walks $W_{2n}(T_k)$ equals $G_{n+1, k+1} - G_{n+1, k}$ .

3. Key Results

A. Asymptotic Enumeration (Theorem 3)

For fixed $k$ , the number of planted plane trees with decreasing labels $G_{n,k}$ grows asymptotically as:
$G_{n,k} = c_k \alpha_k^n (1 + o(1))$
where $c_k$ is a constant and $\alpha_k$ is the reciprocal of the singularity $z^*_{k-1}$ .
The paper provides tight bounds for $\alpha_k$ :
$2(k-1)\left(1 - \frac{1}{\sqrt{2}(k-1)^{1/4}}\right) \le \alpha_k \le \frac{1}{k-1 - \sqrt{(k-1)^2-1}}$
Crucially, as $k \to \infty$ , $\alpha_k = 2k + o(k)$ .

B. Eigenvalue of Regular Leaning Trees (Lemma 5)

Using the trace method, the largest eigenvalue $\lambda_1(A_k)$ of the adjacency matrix of the regular leaning tree $T_k$ is derived from the growth rate of closed walks:
$\lambda_1(A_k) = \lim_{n \to \infty} (W_{2n}(T_k))^{1/2n} = \sqrt{\alpha_k}$
Substituting the asymptotic result for $\alpha_k$ :
$\lambda_1(A_k) = \sqrt{2k} + o(k)$
This result is significant because standard bounds for trees with maximum degree $\Delta = k+1$ are $\sqrt{\Delta} \le \lambda_1 \le 2\sqrt{\Delta-1}$ . The authors show that for regular leaning trees, $\lambda_1 \approx \sqrt{2k}$ , which is strictly larger than the lower bound $\sqrt{k+1}$ and strictly smaller than the upper bound $2\sqrt{k}$ . Thus, these trees do not approach the extreme bounds as $k \to \infty$ .

C. General Trees and Ulam–Harris Number (Theorem 6)

The authors introduce the Ulam–Harris number $UH(T)$, defined as the maximum label in a tree where the root is 1, and children of a node with label $r$ are labeled $r+1, \dots, r+s$ (where $s$ is the number of children).

They prove that for any rooted unordered tree $T$ , $\lambda_1(A) \le \lambda_1(A_{UH(T)-1})$ .
Since $\lambda_1(A_{UH(T)-1}) \approx \sqrt{2(UH(T)-1)}$ , this provides a new upper bound for the spectral radius of arbitrary trees.
If $UH(T) + 1 < 2\Delta$ , this bound improves upon the known Stevanovi´c bound of $2\sqrt{\Delta-1}$ .

4. Significance and Contributions

Combinatorial Enumeration: The paper provides a rigorous asymptotic analysis of a specific class of labeled plane trees, resolving the growth rate behavior for fixed label sets $k$ as the tree size $n$ grows.
Spectral Graph Theory Application: It bridges combinatorial enumeration with spectral graph theory. By linking the count of decreasing label trees to closed walks on "regular leaning trees," the authors derive precise asymptotics for the largest eigenvalue of these specific tree structures.
Refinement of Eigenvalue Bounds: The work challenges the intuition that trees with high degree must have eigenvalues near the theoretical upper bound ( $2\sqrt{\Delta}$ ). It demonstrates that structural constraints (like the "leaning" structure) result in eigenvalues scaling as $\sqrt{2\Delta}$ , offering a more nuanced understanding of tree spectra.
New Upper Bound for General Trees: The introduction of the Ulam–Harris number as a parameter to bound the spectral radius offers a potentially tighter constraint than degree-based bounds for certain classes of trees.

5. Conclusion

The paper successfully utilizes generating functions and bijective mappings to solve a non-trivial counting problem. The primary contribution is the derivation of the asymptotic growth rate $\alpha_k \sim 2k$ for decreasing label trees, which directly translates to the spectral radius of regular leaning trees being $\sim \sqrt{2k}$ . This finding refines the understanding of how tree topology influences the largest eigenvalue of the adjacency matrix, providing a counter-example to the extremal behavior suggested by simple degree bounds.