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

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 $h_n$ d'un arbre à $n$ nœuds (c'est-à-dire le nombre maximum de nœuds de la racine à une feuille) satisfait $h_n \sim \sqrt{\pi n}$ .

$A_{nh}$$h$$A_{nh} = A_{nn}$$h \geqslant n$$B_{nh}$$n$$h+1$$B_{nh} = A_{nn} - A_{nh}$$h_n = S_n/A_{nn}$$S_n$

$$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}$ , car l'ensemble des arbres généraux à $n$ nœuds est en bijection avec l'ensemble des arbres binaires avec $n-1$ nœuds, comptés par les nombres catalans.

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

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

$$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 est la suivante. Je considère la bijection entre des arbres à $n$ nœuds et des chemins monotones sur une grille carrée $(n-1) \times (n-1)$ de $(0,0)$ à $(n-1,n-1)$ qui ne traversent pas la diagonale (et sont constitués de deux types d'étapes: $\uparrow$ et $\rightarrow$ ). Ces chemins sont parfois appelés sentiers Dyck ou excursions . Je peux maintenant exprimer $B_{nh}$ 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 $h-1$ .)

Sans perte de généralité, je suppose qu'ils commencent par $\uparrow$ (donc restent au-dessus de la diagonale). Pour chaque chemin, je considère la première étape franchissant la ligne $y = x + h - 1$ , le cas échéant. Du point ci-dessus, tout en remontant à l'origine, je change $\uparrow$ en $\rightarrow$ et vice versa (c'est une réflexion sur 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 frontières $y=x+2h+1$ et $y=x-1$ . (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: ,

$$\sum_{k \in \mathbb{Z}} \left[\binom{m+n}{m-k(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$$(-h,h)$$s=1$$t=2h+1$et 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+h-1,n-h-1)$ $$B_{nh} = \sum_{k \in \mathbb{Z}} \left[\binom{2n-2}{n+h-1-k(2h+2)} - \binom{2n-2}{n-h-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} = \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].$$ $2k+1$$k$

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

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.$(n−1,n−1)$$y=x+2h+1$$y=x+h$