15
$\begingroup$

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 above the diagonal). For each path, I consider the first step crossing the line $y = x + h - 1$, if any. From the point above, all the way back to the origin, I change $\uparrow$ into $\rightarrow$ and vice versa (this is a reflection wrt the line $y=x+h$). It becomes apparent that the paths I want to count ($B_{nh}$) are in bijection with the monotonic paths from $(-h,h)$ to $(n-1,n-1)$ which avoid the boundaries $y=x+2h+1$ and $y=x-1$. (See figure.)

In the classic book Lattice Path Counting and Applications by Mohanty (1979, page 6) the formula $$ \sum_{k \in \mathbb{Z}} \left[\binom{m+n}{m-k(t+s)} - \binom{m+n}{n+k(t+s)+t}\right], $$ counts the number of monotonic paths in a lattice from $(0,0)$ to $(m,n)$, which avoid the boundaries $y = x - t$ and $y = x + s$, with $t > 0$ and $s > 0$. (This result was first established by Russian statisticians in the 50s.) Therefore, by considering a new origin at $(-h,h)$, we satisfy the conditions of the formula: $s=1$, $t=2h+1$ and the destination point (the upper right corner) is now $(n+h-1,n-h-1)$. Then $$ B_{nh} = \sum_{k \in \mathbb{Z}} \left[\binom{2n-2}{n+h-1-k(2h+2)} - \binom{2n-2}{n-h-1+k(2h+2) + 2h+1}\right]. $$ This can be simplified in $$ B_{n+1,h-1} = \sum_{k \in \mathbb{Z}} \left[\binom{2n}{n+1-(2k+1)h} - \binom{2n}{n-(2k+1)h}\right], $$ which, in turn, is equivalent to $$ B_{n+1,h-1} = \sum_{k \geqslant 0} \left[\binom{2n}{n+1-(2k+1)h} - 2\binom{2n}{n-(2k+1)h} + \binom{2n}{n-1-(2k+1)h}\right]. $$ The difference with the expected formula is that I sum over the odd numbers ($2k+1$), instead of all positive integers ($k$).

Any idea where the problem is?

$\endgroup$
  • $\begingroup$ You say you want to use only elementary things, yet you use a result from a book. How does Mohanty derive the identity you use? $\endgroup$ – Raphael Sep 29 '12 at 10:01
  • $\begingroup$ I define in the first sentence what I mean by "elementary": no generating functions, no complex analysis, no Fourier analysis. In his book, Mohanty uses elementary means to derive that formula, more precisely, the principles of reflection and inclusion-exclusion on lattice paths. (I use the former above.) If you insist, I will add his proof at the end of the question. $\endgroup$ – Christian Sep 29 '12 at 14:04
  • $\begingroup$ Not at all, just wanted to make sure you were not breaking your rule yourself. $\endgroup$ – Raphael Sep 29 '12 at 18:02
  • $\begingroup$ It's very weird to me to see 'generating functions' listed as a non-elementary technique when analytical combinatorics is apparently considered elementary. $\sqrt{\pi}$ seems like an almost inherently non-elementary value; do you have e.g. a comparable proof of the asymptotics of the central binomial coefficient to give a better sense of what you're looking for? I suspect the two are closely related... $\endgroup$ – Steven Stadnicki May 7 '14 at 19:26
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.