1
$\begingroup$

I am moving through a classic paper (On Average Height of Planted Plane Trees by Knuth, de Bruijn and Rice, 1972), and I would like to trade a weaker result for simpler mathematical tools, because my skills are not up for the task. I would simply like to prove that the average height $h_n$ of a tree with $n$ nodes (i.e. the maximum number of nodes from the root to a leaf) satisfies $h_n \sim \sqrt{\pi n}$.

The outline from the article is as follows and may be skipped.

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. Thus, 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]. $$

Then they say that $$ S_{n+1} = \sum_{k \geqslant 1}d(k) \cdot \left[\binom{2n}{n+1-k} - 2\binom{2n}{n-k} + \binom{2n}{n-1-k}\right], $$ where $d(k)$ is the number of positive divisors of $k$. (They go about it with an integral on the complex plane.)

If I am not mistaken, this boils down to prove $$ \sum_{k \geqslant 1}\sum_{h \geqslant 1}\binom{2n}{n+a-kh} = \sum_{k' \geqslant 1}d(k') \cdot \binom{2n}{n+a-k'}. $$ How would you approach this identity without using complex analysis?

EDIT: Terry Tao nailed it in a comment below: if we write all the binomial coefficients summed in the left-hand side, we can regroup them by multiples of $k$, that is, by divisors of $k'$. (What obscures this simple argument is to use $k$ on the right-hand side as well and think that it is the same as in the left-hand side.)

$\endgroup$
2
  • 2
    $\begingroup$ Crossposted to math.SE: math.stackexchange.com/q/264137/264 In the future, please wait some time before posting your question in multiple fora, and when you do, provide links to the other posts - as you can imagine, it would be frustrating for someone to put time into answering your question here, only to see hear from you that you'd already gotten the solution elsewhere. $\endgroup$ Dec 24, 2012 at 5:47
  • 5
    $\begingroup$ I think all that the authors are doing here is expanding $d(k) = \sum_{k = k' h} 1$, then interchanging summations, then relabeling $k'$ as $k$ (and also shifting $h$ by $1$). $\endgroup$
    – Terry Tao
    Dec 24, 2012 at 8:07

2 Answers 2

3
$\begingroup$

It isn't true. Choose $n,a,k$ such that $n+a-k>0$, $n+a-2k<0$ and $k>1$. The sum has only one nonzero term which is not equal to the right side.

$\endgroup$
1
  • $\begingroup$ Thanks. That was too strong a condition. I restated above. $\endgroup$ Dec 25, 2012 at 12:56
1
$\begingroup$

Terry Tao answered my question in a comment. See edit at the end of the main post.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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