Sur « La moyenne Hauteur de Plantée Platanes » par Knuth, de Bruijn et Rice (1972)

Question

Je suis en train de tirer le papier classique dans le titre que par élémentaires (pas de fonctions génératrices , aucune analyse complexe, aucune analyse de Fourier) mais avec beaucoup moins de précision. En bref, je « seulement » veux prouver que la hauteur moyenne $ h_n $ d'un arbre avec $ n nœuds $ (ce qui est, le nombre maximum de nœuds de la racine à une feuille) satisfait $ h_n \ sim \ sqrt {\ pi n} $.

Le contour est suit comme. Soit $ A_ {nh} $ le nombre d'arbres avec une hauteur inférieure ou égale à $ h $ (avec la convention $ A_ {nh} = A_ {nn} $ pour tous $ h \ geqslant n $) et B_ $ { nh} $ le nombre d'arbres de $ n $ noeuds avec une plus grande hauteur supérieure ou égale à $ h + $ 1 (qui est, B_ {$ de nh} = A_ {nn} - A_ {nh} $). Alors $ h_n = S_n / A_ {nn} $, où $ S_n $ est la somme finie $$ 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}. $$ Il est bien connu que $ A_ {nn} = \ frac {1} {n} \ binom {2n-2} {n-1} $, pour l'ensemble des arbres généraux avec des nœuds $ n $ est en bijection avec l'ensemble des arbres binaires avec n-1 $ nœuds de $, comptés par les chiffres catalans.

Par conséquent, la première étape est de trouver $ B_ {nh} $ et le terme principal dans l'expansion asymptotique de $ S_n $.

À ce stade, les auteurs utilisent analytiques (trois combinatoires pages) à 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]. $$

  

Ma propre tentative suit comme. Je considère que la bijection entre les arbres avec $ n nœuds de $   et les chemins monotones sur une grille carrée $ (n-1) \ Temps (n-1) à partir de $ $ (0,0) $ à (n-1, n-1) $ qui ne traversent pas la diagonale (et sont en deux types de mesures: $ \ uparrow $ et $ \ rightarrow $). Ces chemins sont parfois appelés chemins de Dyck ou excursions . Je peux maintenant exprimer B_ $ {nh} $ en termes de chemins treillis: il est le nombre de Dyck chemins de longueur 2 (n-1) et une plus grande hauteur supérieure ou égale à $ h $. (Note:. Un arbre de hauteur $ h $ est en bijection avec un chemin de Dyck h-1 $ la hauteur $)

     

Sans perte de généralité, je suppose qu'ils commencent par $ \ uparrow $ (séjour là-dessus de la diagonale). Pour chaque chemin, je considère que la première étape de franchir la ligne $ y = x + h - 1 $, le cas échéant. Du point ci-dessus, tout l'arrière de façon à l'origine, je change $ \ uparrow $ en $ \ rightarrow $ et vice versa (ce qui est une réflexion wrt la ligne $ y = x + h $) . Il devient évident que les chemins que je veux compter ($ B_ {nh} $) sont en bijection avec les chemins monotones de $ (- h, h) $ à $ (n-1, n-1) $ qui évitent les limites $ y = x + 2h + 1 $ et $ y = x-1 $. (Voir figure .)

Dans le livre classique Lattice Chemin de comptage et applications par Mohanty (1979, page 6) la formule $$ \ Sum_ {k \ in \ mathbb {Z}} \ left [\ binom {m + n} {mk (t + s)} - \ binom {m + n} {n + k (t + s) + t} \droite], $$ compte le nombre de chemins monotones dans un réseau de $ (0,0) $ à $ (m, n) $, ce qui évite les limites $ y = x - t $ et $ y = x + s $, avec $ t> 0 $ et> de $ 0 $. (Ce résultat a été établi par les statisticiens russes dans les années 50). Par conséquent, en considérant une nouvelle origine à $ (- h, h) $, nous satisfaisons les conditions de la formule: $ s = 1 $, $ t = 2h + 1 $ et le point de destination (le coin supérieur droit) est maintenant $ (n + h-1, nh-1) $. alors $$ 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} \ right]. $$ Cela peut être simplifié $$ 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], $$ qui, à son tour, est équivalent à $$ 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]. $$ La différence avec la formule I attendu est que somme sur les nombres impairs ($ 2k + 1 $), au lieu de tous les entiers positifs ($ k $).

Toute idée où le problème est?

Answer 1

Les chemins monotones de $ (- h, h) $ à $ (n-1, n-1) $ que vous construisez seulement d'éviter la limite $ y = x + 2h + 1 $ avant de traverser $ y = x + h $ pour la première fois. Ainsi, la formule que vous utilisez est pas applicable.