Knuth、De Bruijn、Rice（1972）による「植えられた飛行の木の平均高さ」について

Question

私は導き出そうとしています クラシックペーパー タイトルでは、初等手段のみ（生成関数、複雑な分析なし、フーリエ分析なし）では、はるかに精度が低くなります。要するに、私は「$ n $ nodes（つまり、ルートから葉までの最大ノードの数）が$ h_n sim sqrt {を満たしているツリーの平均高さ$ h_n $が$ n $ nodesのあるツリーの$ h_n $が「のみ」を証明したいと考えています。 pi n} $。

アウトラインは次のとおりです。 $ a_ {nh} $を$ h $以下の高さを持つ木の数とします（$ a_ {nh} = a_ {nn} $ forすべての$ h geqslant n $）および$ b_ { nh} $ $ h+1 $以上の高さの$ n $ノードのツリー数（つまり、$ b_ {nh} = a_ {nn} -a_ {nh} $）。次に、$ h_n = s_n/a_ {nn} $、$ s_n $は有限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}。 $$ $ a_ {nn} = frac {1} {n} binom {2n-2} {n-1-1} $、$ n $ nodesの一般的なツリーのセットについては、カタロニアの数字でカウントされる$ n-1 $ノードのバイナリツリーのセット。

したがって、最初のステップは、$ b_ {nh} $を見つけることであり、次に$ s_n $の漸近拡張の主要な用語です。

この時点で、著者は分析組み合わせ（3ページ）を使用して$$ 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]。 $$

私自身の試みは次のとおりです。 $ n $ nodesと平方グリッド上の単調パスを持つ木の間のバイジェリアは、$（0,0）$から$（n-1、n-1から$（n-1） times（n-1）$ $ he ）対角線を越えない$（そして、2種類の手順で作られています：$ uparrow $と$ rightArrow $）。これらのパスは時々呼ばれます dyckパス また 遠足. 。格子パスに関して$ b_ {nh} $を表現できます。長さ2（n-1）のdyckパスの数と$ h $以上の高さです。 （注：高さ$ h $の木は、高さ$ h-1 $のdyckパスを備えたbijectionにあります。）

一般性を失うことなく、私はそれらが$ uparrow $から始まると仮定します（したがって、対角線の上にとどまります）。各パスについて、最初のステップがライン$ y = x + h -1 $を通過すると考えます。上記のポイントから、すべての源泉から、$ uparrow $を$ rightArrow $に変更し、その逆（これは 反射 wrt line $ y = x+h $）。カウントしたいパス（$ b_ {nh} $）は、境界を避ける$（h、h）$（n-1、n-1）$から$（h、h）$から$（n-1、n-1）$から単調なパスを伴う隔離にあることが明らかになります。 $ y = x+2h+1 $および$ y = x-1 $。 （見る 形.)

古典的な本で 格子パスカウントとアプリケーション Mohanty（1979、Page 6）by formula $$ sum_ {k in mathbb {z}} left [ binom {m+n} {mk（t+s）} - binom {m+n} {n+k（t+s）+t} right]、$$は、$（0,0）$ $（m、n）$から格子内の単調パスの数を数えます。 = 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 {2n-2} {n+h-1-k（2h+2）} - binom {2n- 2} {NH-1+K（2H+2）+2H+1} 右]。 $$これは$$ 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} = sum_ {k に相当します。 geqslant 0} left [ binom {2n} {n+1-（2k+1）h} -2 binom {2n} {n-（2k+1）h}+ binom {2n} {n-1} {n-1} - （2k+1）h} right]。 $$予想される式との違いは、すべての正の整数（$ k $）ではなく、奇数（$ 2K+1 $）に合計することです。

問題がどこにあるのか考えていますか？

Answer 1

$（ - h、h）$から$（n -1、n -1）$から構築する単調なパスは、$ y = x+h $を越える前に境界$ y = x+2h+1 $を回避するだけです。初めて。したがって、使用する式は適用されません。