Sur «La hauteur moyenne des platanes plantés» de Knuth, de Bruijn et Rice (1972)

15

J'essaie de dériver l' article classique dans le titre uniquement par des moyens élémentaires (pas de fonctions génératrices, pas d'analyse complexe, pas d'analyse de Fourier) bien qu'avec beaucoup moins de précision. Bref, je veux "seulement" prouver que la hauteur moyenne hn d'un arbre à n nœuds (c'est-à-dire le nombre maximum de nœuds de la racine à une feuille) satisfait hnπn .

AnhhAnh=AnnhnBnhnh+1Bnh=AnnAnhhn=Sn/AnnSn

Sn=h1h(AnhAn,h1)=h1h(Bn,h1Bnh)=h0Bnh.
Il est bien connu que Ann=1n(2n2n1) , car l'ensemble des arbres généraux à n nœuds est en bijection avec l'ensemble des arbres binaires avec n1 nœuds, comptés par les nombres catalans.

Par conséquent, la première étape consiste à trouver Bnh puis le terme principal dans l'expansion asymptotique de Sn .

À ce stade, les auteurs utilisent la combinatoire analytique (trois pages) pour dériver

Bn+1,h1=k1[(2nn+1kh)2(2nnkh)+(2nn1kh)].

Ma propre tentative est la suivante. Je considère la bijection entre des arbres à n nœuds et des chemins monotones sur une grille carrée (n1)×(n1) de (0,0) à (n1,n1) qui ne traversent pas la diagonale (et sont constitués de deux types d'étapes: et ). Ces chemins sont parfois appelés sentiers Dyck ou excursions . Je peux maintenant exprimer Bnh en termes de chemins de réseau: c'est le nombre de chemins de Dyck de longueur 2 (n-1) et de hauteur supérieure ou égale à h . (Remarque: un arbre de hauteur h est en bijection avec un chemin Dyck de hauteur h1 .)

Sans perte de généralité, je suppose qu'ils commencent par (donc restent au-dessus de la diagonale). Pour chaque chemin, je considère la première étape franchissant la ligne y=x+h1 , le cas échéant. Du point ci-dessus, tout en remontant à l'origine, je change en et vice versa (c'est une réflexion sur la ligne y=x+h ). Il devient évident que les chemins que je veux compter ( Bnh ) sont en bijection avec les chemins monotones de (h,h) à (n1,n1) qui évitent les frontières y=x+2h+1 et y=x1 . (Voir figure .)

Dans le livre classique Lattice Path Counting and Applications de Mohanty (1979, page 6), la formule compte le nombre de chemins monotones dans un réseau de à , ce qui évite les frontières et , avec et . (Ce résultat a été établi pour la première fois par des statisticiens russes dans les années 50.) Par conséquent, en considérant une nouvelle origine à , nous satisfaisons aux conditions de la formule: ,

kZ[(m+nmk(t+s))(m+nn+k(t+s)+t)],
(0,0)(m,n)y=xty=x+st>0s>0(h,h)s=1t=2h+1et le point de destination (le coin supérieur droit) est maintenant . Alors Cela peut être simplifié dans qui, à son tour, équivaut à La différence avec la formule attendue est que je additionne les nombres impairs ( ), au lieu de tous les entiers positifs ( ).(n+h1,nh1)
Bnh=kZ[(2n2n+h1k(2h+2))(2n2nh1+k(2h+2)+2h+1)].
Bn+1,h1=kZ[(2nn+1(2k+1)h)(2nn(2k+1)h)],
Bn+1,h1=k0[(2nn+1(2k+1)h)2(2nn(2k+1)h)+(2nn1(2k+1)h)].
2k+1k

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

Christian
la source
Vous dites que vous ne voulez utiliser que des choses élémentaires, mais vous utilisez un résultat d'un livre. Comment Mohanty dérive-t-elle l'identité que vous utilisez?
Raphael
Je définis dans la première phrase ce que j'entends par «élémentaire»: pas de fonctions génératrices, pas d'analyse complexe, pas d'analyse de Fourier. Dans son livre, Mohanty utilise des moyens élémentaires pour dériver cette formule, plus précisément, les principes de réflexion et d'inclusion-exclusion sur les chemins de réseau. (J'utilise l'ancien ci-dessus.) Si vous insistez, j'ajouterai sa preuve à la fin de la question.
Christian
Pas du tout, je voulais juste m'assurer que vous ne violiez pas votre règle vous-même.
Raphael
C'est très bizarre pour moi de voir les «fonctions génératrices» répertoriées comme une technique non élémentaire lorsque la combinatoire analytique est apparemment considérée comme élémentaire. π semble être une valeur non élémentaire presque intrinsèquement; avez-vous par exemple une preuve comparable de l'asymptotique du coefficient binomial central pour donner une meilleure idée de ce que vous recherchez? Je soupçonne que les deux sont étroitement liés ...
Steven Stadnicki

Réponses:

2

Les chemins monotones de (h,h) à que vous construisez n'évitent que la frontière avant de traverser pour la première fois. La formule que vous utilisez n'est donc pas applicable.(n1,n1)y=x+2h+1y=x+h

FrankW
la source