patternMinor
On "The Average Height of Planted Plane Trees" by Knuth, de Bruijn and Rice (1972)
Viewed 0 times
theheightplantedaverageplanetrees1972knuthandbruijn
Problem
I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" want to prove that the average height $h_n$ of a tree with $n$ nodes (that is, the maximum number of nodes from the root to a leaf) satisfies $h_n \sim \sqrt{\pi n}$.
The outline is as follows. Let $A_{nh}$ be the number of trees with height less than or equal to $h$ (with the convention $A_{nh} = A_{nn}$ for all $h \geqslant n$) and $B_{nh}$ the number of trees of $n$ nodes with height greater than or equal to $h+1$ (that is, $B_{nh} = A_{nn} - A_{nh}$). Then $h_n = S_n/A_{nn}$, where $S_n$ is the finite sum
$$
S_n = \sum_{h \geqslant 1} h(A_{nh} - A_{n,h-1}) = \sum_{h \geqslant 1} h(B_{n,h-1} - B_{nh}) = \sum_{h \geqslant 0} B_{nh}.
$$
It is well known that $A_{nn} = \frac{1}{n}\binom{2n-2}{n-1}$, for the set of general trees with $n$ nodes is in bijection with the set of binary trees with $n-1$ nodes, counted by the Catalan numbers.
Therefore, the first step is to find $B_{nh}$ and then the main term in the asymptotic expansion of $S_n$.
At this point the authors use analytical combinatorics (three pages) to derive
$$
B_{n+1,h-1} = \sum_{k \geqslant 1} \left[\binom{2n}{n+1-kh} - 2\binom{2n}{n-kh} + \binom{2n}{n-1-kh}\right].
$$
My own attempt is as follows. I consider the bijection between trees with $n$ nodes
and monotonic paths on a square grid $(n-1) \times (n-1)$ from $(0,0)$ to $(n-1,n-1)$ which do not cross the diagonal (and are made of two kinds of steps: $\uparrow$ and $\rightarrow$). These paths are sometimes called Dyck paths or excursions. I can express now $B_{nh}$ in terms of lattice paths: it is the number of Dyck paths of length 2(n-1) and height greater than or equal to $h$. (Note: a tree of height $h$ is in bijection with a Dyck path of height $h-1$.)
Without loss of generality, I assume that they start with $\uparrow$ (hence stay abov
The outline is as follows. Let $A_{nh}$ be the number of trees with height less than or equal to $h$ (with the convention $A_{nh} = A_{nn}$ for all $h \geqslant n$) and $B_{nh}$ the number of trees of $n$ nodes with height greater than or equal to $h+1$ (that is, $B_{nh} = A_{nn} - A_{nh}$). Then $h_n = S_n/A_{nn}$, where $S_n$ is the finite sum
$$
S_n = \sum_{h \geqslant 1} h(A_{nh} - A_{n,h-1}) = \sum_{h \geqslant 1} h(B_{n,h-1} - B_{nh}) = \sum_{h \geqslant 0} B_{nh}.
$$
It is well known that $A_{nn} = \frac{1}{n}\binom{2n-2}{n-1}$, for the set of general trees with $n$ nodes is in bijection with the set of binary trees with $n-1$ nodes, counted by the Catalan numbers.
Therefore, the first step is to find $B_{nh}$ and then the main term in the asymptotic expansion of $S_n$.
At this point the authors use analytical combinatorics (three pages) to derive
$$
B_{n+1,h-1} = \sum_{k \geqslant 1} \left[\binom{2n}{n+1-kh} - 2\binom{2n}{n-kh} + \binom{2n}{n-1-kh}\right].
$$
My own attempt is as follows. I consider the bijection between trees with $n$ nodes
and monotonic paths on a square grid $(n-1) \times (n-1)$ from $(0,0)$ to $(n-1,n-1)$ which do not cross the diagonal (and are made of two kinds of steps: $\uparrow$ and $\rightarrow$). These paths are sometimes called Dyck paths or excursions. I can express now $B_{nh}$ in terms of lattice paths: it is the number of Dyck paths of length 2(n-1) and height greater than or equal to $h$. (Note: a tree of height $h$ is in bijection with a Dyck path of height $h-1$.)
Without loss of generality, I assume that they start with $\uparrow$ (hence stay abov
Solution
The monotonic paths from $(−h,h)$ to $(n−1,n−1)$ that you construct only avoid the boundary $y=x+2h+1$ before they cross $y=x+h$ for the first time. Thus the formula you use is not applicable.
Context
StackExchange Computer Science Q#4777, answer score: 2
Revisions (0)
No revisions yet.