关于Knuth，De Bruijn和Rice（1972）的“种植架树的平均高度”

Question

我试图得出 经典纸 在标题中仅通过基本均值（没有生成功能，没有复杂的分析，没有傅立叶分析），尽管精度要少得多。简而言之，我“唯一”想证明，带有$ n $节点的树的平均高度$ h_n $（即，从根到叶子的最大节点数量）满足$ h_n sim sqrt { sqrt { sqrt { sqrt { sqrt pi n} $。

大纲如下。 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} $高度大于或等于$ h+1 $的$ n $节点的树的数量（即，$ b_ {nh} = a_ {nn} - a_ a_ {nh} $）。然后$ h_n = s_n/a_ {nn} $，其中$ s_n $是有限sum $$ $$ s_n = sum_ {h geqslant 1} sum_ {h geqslant 1} h（b_ {n，h -1} - b_ {nh}）= sum_ {h geqslant 0} b_ {nh}。 $$众所周知，$ a_ {nn} = frac {1} {n} binom {2n-2} {n-1} $，对于带有$ n $ nodes的一组通用树，与$ n $ nodes一起进行双向射击加泰罗尼亚数字计算的一组带有$ n-1 $节点的二进制树。

因此，第一步是找到$ b_ {nh} $，然后是$ s_n $的渐近扩展中的主要术语。

此时，作者使用分析组合（三页）来得出$$ 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]。 $$

我自己的尝试如下。我认为从$（0,0）$到$（N-1，N-1，N-1 ）$不穿越对角线（并且由两种步骤制成：$ uparrow $和$ rightarrow $）。这些路径有时被称为 戴克路径 或者 游览. 。我现在可以按晶格路径表示$ b_ {nh} $：它是长度2（n-1）的戴克路径的数量，高度大于或等于$ h $。 （注意：一棵高度$ h $的树在培训中，带有高度$ h-1 $的戴克路径。）

我认为，我认为它们以$ uparrow $（因此保持在对角线上方）。对于每条路径，我考虑越过线路的第一步$ y = x + h -1 $（如果有）。从上面的角度，我一直回到原点，我将$ uparrow $更改为$ rightarrow $，反之亦然（这是一个 反射 wrt行$ y = x+h $）。很明显，我要计算的路径（$ b_ {nh} $）与$（-h，h）$到$（n-1，n-1）$的单调路径进行培养，从而避免了边界$ y = x+2h+1 $和$ y = x-1 $。 （看 数字.)

在经典书中 晶格路径计数和应用 由Mohanty（1979，第6页）由公式$$ sum_ {k in mathbb {z}}} left [ binom { binom {m+n} {mk（t+s）} - binom {m+n} {n+k（t+s）+t} right]，$$从$（0,0）$到$（m，n）$计数晶格中单调路径的数量，避免了边界$ y = x -t $和$ y = x + s $，带有$ t> 0 $和$ s> 0 $。 （该结果首先是俄罗斯统计学家在50年代建立的。）因此，通过考虑$（-h，h）$的新来源，我们满足公式的条件：$ s = 1 $，$ t = 2h+ 1 $，目的点（右上角）现在为$（N+H-1，NH-1）$。然后$$ b_ {nh} = sum_ {k in mathbb {z}}} left [ binom { binom {2n-2} {n+h-1-k（2H+2）} - binom {2n-- 2} {NH-1+K（2H+2）+2H+1} right]。 $$可以在$$ 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]，$$，$$又等同于$$ b_ {n+1，h-1，h-1} = sum_ {k {k geqslant 0} left [ binom {2n} {n+1-（2k+1）h} -2 binom {2n} {n-（2k+1）h}+ binom {2n} {2n} {n-1 - （2K+1）H} 右]。 $$与预期公式的区别在于，我汇总了奇数（$ 2K+1 $），而不是所有正整数（$ k $）。

知道问题在哪里吗？

Answer 1

您构造的单调路径从$（ - h，h）$到$（n -1，n -1）$，仅避免边界$ y = x+2h+1 $，然后它们交叉$ y = x+h $首次。因此，您使用的公式不适用。