Auf „die durchschnittliche Höhe der gepflanzten Flugzeugbäume“ von Knuth, de Bruijn und Rice (1972)

Question

Ich versuche das abzuleiten Klassisches Papier im Titel nur mit elementaren Mitteln (keine generierenden Funktionen, keine komplexe Analyse, keine Fourier -Analyse), obwohl mit viel weniger Präzision. Kurz gesagt, ich möchte beweisen, dass die durchschnittliche Höhe $ h_n $ eines Baumes mit $ n $ Knoten (dh die maximale Anzahl von Knoten vom Wurzel zu einem Blatt) erfüllt $ H_N SIM SQRT { pi n} $.

Der Umriss ist wie folgt. Sei $ a_ {nh} $ die Anzahl der Bäume mit einer Höhe von weniger als oder gleich $ h $ (mit der Konvent nh} $ Die Anzahl der Bäume von $ n $ Knoten mit Höhe größer oder gleich $ H+1 $ (dh $ b_ {nh} = a_ {nn} - a_ {nh} $). Dann $ h_n = s_n/a_ {nn} $, wobei $ s_n $ die endliche Summe $$ S_N = sum_ {h geqslant 1} h (a_ {nh} - a_ {n, h -1}) = ist sum_ {h geqslant 1} H (B_ {n, h -1} - b_ {nh}) = sum_ {h geqslant 0} b_ {nh}. $$ Es ist bekannt Der Satz Binärbäume mit N-1 $ -Knoten, gezählt von den katalanischen Zahlen.

Der erste Schritt besteht daher darin, $ B_ {NH} $ und dann der Hauptbegriff in der asymptotischen Erweiterung von $ s_n $ zu finden.

Zu diesem Zeitpunkt verwenden die Autoren die analytische Kombinatorik (drei Seiten), um $$ b_ {n+1, h-1} = sum_ {k geqslant 1} links [ binom {2n} {n+1-kh} abzuleiten -2 binom {2n} {n-kh} + binom {2n} {n-1-kh} rechts]. $$

Mein eigener Versuch ist wie folgt. Ich betrachte die Bijection zwischen Bäumen mit $ n $ Knoten und monotonischen Pfaden auf einem quadratischen Netz $ (N-1) Times (N-1) $ von $ (0,0) $ bis $ (N-1, N-1) ) $, die die Diagonale nicht überqueren (und aus zwei Arten von Schritten bestehen: $ Uparrow $ und $ rightarrow $). Diese Wege werden manchmal genannt Dyck -Pfade oder Exkursionen. Ich kann jetzt $ b_ {nh} $ in Bezug auf Gitterpfade ausdrücken: Es ist die Anzahl der Dyck-Pfade von Länge 2 (N-1) und Höhe größer oder gleich $ H $. (Hinweis: Ein Baum mit Höhe $ H $ ist in Bijection mit einem Dyck-Pfad der Höhe $ h-1 $.)

Ohne Verlust der Allgemeinheit gehe ich davon aus, dass sie mit $ uparrow $ beginnen (daher bleiben Sie über der Diagonale). Für jeden Weg betrachte ich den ersten Schritt, der die Linie $ y = x + h - 1 $ überquert, falls vorhanden. Von dem obigen Punkt, bis zum Ursprung, ändere ich $ uparrow $ $ rightarrow $ und umgekehrt (dies ist ein Betrachtung wrt die Linie $ y = x+h $). Es wird offensichtlich, dass die Pfade, die ich zählen möchte ($ b_ {nh} $) $ y = x+2h+1 $ und $ y = x-1 $. (Sehen Zahl.)

Im klassischen Buch Gitterpfadzählung und Anwendungen von Mohanty (1979, Seite 6) Die Formel $$ sum_ {k in mathbb {z}} links [ binom {m+n} {mk (t+s)} - binom {m+n} oder = x - t $ und $ y = x + s $, mit $ t> 0 $ und $ s> 0 $. (Dieses Ergebnis wurde erstmals von russischen Statistikern in den 50er Jahren festgelegt.) Daher erfüllen wir die Bedingungen der Formel: $ s = 1 $, $ t = 2H+ 1 $ und der Zielpunkt (die obere rechte Ecke) ist jetzt $ (N+H-1, NH-1) $. Dann $$ b_ {nh} = sum_ {k in mathbb {z}} links [ binom {2n-2} {n+h-1-k (2H+2)}- binom {2n- 2} {NH-1+k (2H+2)+2H+1} rechts]. $$ Dies kann in $$ b_ {n+1, h-1} = sum_ {k in mathbb {z}} links [ binom {2n} {n+1- (2k+1) vereinfacht werden. H}- binom {2n} {n- (2k+1) H} rechts], $$, was wiederum $ $$ b_ {n+1, h-1} = sum_ {k entspricht Geqslant 0} links [ binom {2n} {n+1- (2k+1) H}-2 binom {2n} {n- (2k+1) H}+ binom {2n} {n-1 -(2k+1) H} rechts]. $$ Die Differenz mit der erwarteten Formel besteht darin, dass ich über die ungeraden Zahlen ($ 2k+1 $) anstelle aller positiven Ganzzahlen ($ K $) summe.

Irgendeine Idee, wo das Problem ist?

Answer 1

Die monotonischen Pfade von $ ( - h, h) $ bis $ (n - 1, n - 1) $, dass Sie nur die Grenze $ y = x+2h+1 $ vermeiden, bevor sie $ y = x+H $ überqueren zum ersten Mal. Somit ist die von Ihnen verwendete Formel nicht zutreffend.