Zu „Die durchschnittliche Höhe gepflanzter Platanen“ von Knuth, de Bruijn und Rice (1972)

Ich versuche, das klassische Papier im Titel nur mit elementaren Mitteln (keine Erzeugungsfunktionen, keine komplexe Analyse, keine Fourier-Analyse) abzuleiten , wenn auch mit viel geringerer Genauigkeit. Kurz gesagt, ich möchte "nur" beweisen, dass die durchschnittliche Höhe $h_n$ eines Baums mit $n$ Knoten (dh die maximale Anzahl von Knoten von der Wurzel bis zu einem Blatt) h n ∼ √ erfüllt$h_n \sim \sqrt{\pi n}$ .

$A_{nh}$$h$$A_{nh} = A_{nn}$B n h n h + 1 B n h = A n n - A n h h n = S n / A n n S n S n = Σ h ⩾ 1 h ( A n h - A n , h - 1 ) = Σ h ⩾ 1 h ( B $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}.$$ Es ist allgemein bekannt, dass für die Menge der allgemeinen Bäume mit Knoten mit der Menge der binären Bäume mit in Bijektion steht n-1 Knoten, gezählt nach den katalanischen Zahlen. nn-$A_{nn} = \frac{1}{n}\binom{2n-2}{n-1}$$n$$n-1$

Daher besteht der erste Schritt darin, $B_{nh}$ und dann den Hauptterm in der asymptotischen Expansion von $S_n$ .

Zu diesem Zeitpunkt verwenden die Autoren die analytische Kombinatorik (drei Seiten), um B_ {n + 1, h-1} = \ sum_ {k \ geqslant 1} \ left [\ binom {2n} {n + 1-kh} - 2 abzuleiten

$$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].$$

Mein eigener Versuch ist wie folgt. Ich betrachte die Bijektion zwischen Bäumen mit $n$ Knoten und monotonen Pfaden auf einem quadratischen Gitter $(n-1) \times (n-1)$ von $(0,0)$ bis $(n-1,n-1)$ die die Diagonale nicht kreuzen (und bestehen aus zwei Arten von Schritten: $\uparrow$ und $\rightarrow$ ). Diese Wege werden manchmal als Dyck-Wege oder Exkursionen bezeichnet . Ich kann jetzt $B_{nh}$ in Gitterpfaden ausdrücken : Es ist die Anzahl der Dyck-Pfade der Länge 2 (n-1) und der Höhe größer oder gleich $h$ . (Hinweis: Ein Baum der Höhe $h$ befindet sich in Bijektion mit einem Dyck-Pfad der Höhe $h-1$ .)

Ohne Verlust der Allgemeinheit gehe ich davon aus, dass sie mit \ uparrow beginnen$\uparrow$ (also über der Diagonale bleiben). Für jeden Pfad betrachte ich den ersten Schritt, der die Linie y = x + h - 1 kreuzt $y = x + h - 1$, falls vorhanden. Von oben bis zum Ursprung ändere ich $\uparrow$ in $\rightarrow$ und umgekehrt (dies ist eine Reflexion auf der Linie $y=x+h$ ). Es wird deutlich, dass die Pfade, die ich zählen möchte ( $B_{nh}$ ), im Widerspruch zu den monotonen Pfaden von $(-h,h)$ bis $(n-1,n-1)$ wobei die Grenzen $y=x+2h+1$ und $y=x-1$ . (Siehe Abbildung .)

In dem klassischen Buch Lattice Path Counting and Applications von Mohanty (1979, Seite 6) lautet die Formel zählt die Anzahl der monotonen Pfade in einem Gitter von bis , die die Grenzen umgehen und , mit und . (Dieses Ergebnis wurde erstmals in den 50er Jahren von russischen Statistikern ermittelt.) Wenn wir einen neuen Ursprung bei , erfüllen wir daher die Bedingungen der Formel: ,

$$\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$und der Zielpunkt (die obere rechte Ecke) ist jetzt . Dann ist Dies kann vereinfacht werden in was wiederum äquivalent zu Der Unterschied zur erwarteten Formel besteht darin, dass ich statt aller positiven ganzen Zahlen ( ) über die ungeraden Zahlen ( ) summiere .$(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$

Irgendeine Idee, wo das Problem liegt?

Die monotonen Pfade von nach , die Sie konstruieren, umgehen nur die Grenze bevor sie zum ersten Mal kreuzen . Daher ist die von Ihnen verwendete Formel nicht anwendbar.$(−h,h)$$(n−1,n−1)$$y=x+2h+1$$y=x+h$