O „Średniej wysokości posadzonych platanów” Knuth, de Bruijn i Rice (1972)

Staram się czerpać z klasycznej pracy tytułowej tylko elementarne środki (bez funkcji generujących, bez złożonej analizy, bez analizy Fouriera), choć ze znacznie mniejszą precyzją. Krótko mówiąc, „tylko” chcę udowodnić, że średnia wysokość drzewa z węzłami (to znaczy maksymalną liczbą węzłów od korzenia do liścia) spełnia .$h_n$$n$$h_n \sim \sqrt{\pi n}$

Zarys jest następujący. Niech będzie liczbą drzew o wysokości mniejszej lub równej (z konwencją dla wszystkich ) i B_ {nh} liczbą drzew n węzłów o wysokości większej lub równej h + 1 (to znaczy B_ {nh} = A_ {nn} - A_ {nh} ). Następnie h_n = S_n / A_ {nn} , gdzie S_n jest skończoną sumą 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}. Dobrze wiadomo, że A_ {nn} = \ frac {1} {n} \ binom {2n-2} {n-1} h A n h = A n n h ⩾ n 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 $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$A n 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}.$$ $A_{nn} = \frac{1}{n}\binom{2n-2}{n-1}$, ponieważ zbiór ogólnych drzew z węzłami $n$ jest wstrząsany zestawem drzew binarnych z węzłami $n-1$ , liczonymi przez liczby katalońskie.

Dlatego pierwszym krokiem jest znalezienie $B_{nh}$ a następnie głównego terminu w asymptotycznej ekspansji $S_n$ .

W tym momencie autorzy wykorzystują kombinatorykę analityczną (trzy strony) do uzyskania

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

Moja własna próba jest następująca. Rozważam bijection między drzewami z $n$ węzłami i ścieżkami monotonicznymi na kwadratowej siatce $(n-1) \times (n-1)$ od $(0,0)$ do $(n-1,n-1)$ które nie przecinają przekątnej (i składają się z dwóch rodzajów kroków: $\uparrow$ i $\rightarrow$ ). Ścieżki te są czasem nazywane ścieżkami Dyck lub wycieczkami . Mogę teraz wyrazić $B_{nh}$ w kategoriach ścieżek kratowych: jest to liczba ścieżek Dyck o długości 2 (n-1) i wysokości większej lub równej $h$ . (Uwaga: drzewo wysokości $h$ jest bijection ze ścieżką Dyck o wysokości $h-1$ .)

Bez utraty ogólności, zakładam, że zaczynają się od $\uparrow$ (stąd pozostają powyżej przekątnej). Dla każdej ścieżki rozważam pierwszy krok przekraczający linię $y = x + h - 1$ , jeśli istnieje. Z powyższego punktu, aż do początku, zmieniam $\uparrow$ na \ w prawo$\rightarrow$ i na odwrót (jest to odbicie w linii $y=x+h$ ). Staje się oczywiste, że ścieżki, które chcę policzyć ( $B_{nh}$ ) są bijection ze ścieżkami monotonicznymi od $(-h,h)$ do $(n-1,n-1)$ które omijają granice $y=x+2h+1$ , a $y=x-1$ . (Patrz rysunek .)

W klasycznej książce Lattice Path Counting and Applications autorstwa Mohanty'ego (1979, strona 6) formuła zlicza liczbę ścieżek monotonicznych w sieci od do , które omijają granice , a , o i . (Ten wynik został po raz pierwszy ustalony przez rosyjskich statystyk w latach 50.) Dlatego, rozważając nowe pochodzenie w , spełniamy warunki wzoru: ,

$$\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$a punkt docelowy (prawy górny róg) jest teraz . Następnie Można to uprościć w co z kolei odpowiada Różnica w stosunku do oczekiwanego wzoru polega na tym, że sumuję ponad liczby nieparzyste ( ) zamiast wszystkich liczb całkowitych dodatnich ( ).B n h = ∑ k ∈ Z [ ( 2 n - $(n+h-1,n-h-1)$Bn+1,h-1=∑k∈Z[ ( 2 $$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$

Masz pojęcie, gdzie jest problem?

Ścieżki monotoniczne od do , które budujesz, unikają tylko granicy zanim przekroczą po raz pierwszy. Dlatego stosowana formuła nie ma zastosowania.$(−h,h)$$(n−1,n−1)$$y=x+2h+1$$y=x+h$