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 liczbą drzew węzłów o wysokości większej lub równej (to znaczy ). Następnie , gdzie jest skończoną sumą Dobrze wiadomo, że $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 ⩾ 1} h ({ZA}_{n h} - {ZA}_{n, h - 1}) = \sum_{h ⩾ 1} h (b_{n, h - 1} - b_{n h}) = \sum_{h ⩾ 0} b_{n h} .

$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_{n n} = \frac{1}{n} (\binom{2 n - 2}{n - 1})

$A_{nn} = \frac{1}{n}\binom{2n-2}{n-1}$ , ponieważ zbiór ogólnych drzew z węzłami

n

$n$ jest wstrząsany zestawem drzew binarnych z węzłami

n - 1

$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 ⩾ 1} [(\binom{2 n}{n + 1 - k h}) - 2 (\binom{2 n}{n - k h}) + (\binom{2 n}{n - 1 - k h})] .

$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 $\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 Z} [(\binom{m + n}{m - k (t + s)}) - (\binom{m + n}{n + k (t + s) + t})],

$\sum_{k \in \mathbb{Z}} \left[\binom{m+n}{m-k(t+s)} - \binom{m+n}{n+k(t+s)+t}\right],$

(0, 0)

$(0,0)$

(m, n)

$(m,n)$

y = x - t

$y = x - t$

y = x + s

$y = x + s$

t > 0

$t > 0$

s > 0

$s > 0$

(- h, h)

$(-h,h)$

s = 1

$s=1$

t = 2 h + 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 ( ).

(n + h - 1, n - h - 1)

$(n+h-1,n-h-1)$

B_{n h} = \sum_{k \in Z} [(\binom{2 n - 2}{n + h - 1 - k (2 h + 2)}) - (\binom{2 n - 2}{n - h - 1 + k (2 h + 2) + 2 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 Z} [(\binom{2 n}{n + 1 - (2 k + 1) h}) - (\binom{2 n}{n - (2 k + 1) h})],

$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 ⩾ 0} [(\binom{2 n}{n + 1 - (2 k + 1) h}) - 2 (\binom{2 n}{n - (2 k + 1) h}) + (\binom{2 n}{n - 1 - (2 k + 1) h})] .

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

2 k + 1

$2k+1$

k

$k$

Masz pojęcie, gdzie jest problem?

— chrześcijanin
źródło

Mówisz, że chcesz używać tylko elementarnych rzeczy, ale używasz wyniku z książki. Jak Mohanty czerpie tożsamość, której używasz?

— Raphael

W pierwszym zdaniu definiuję, co rozumiem przez „elementarny”: brak funkcji generujących, brak złożonej analizy, brak analizy Fouriera. W swojej książce Mohanty używa elementarnych środków, aby wyprowadzić tę formułę, a dokładniej zasady refleksji i włączenia-wykluczenia na ścieżkach sieci. (Korzystam z powyższego.) Jeśli nalegasz, dodam jego dowód na końcu pytania.

— Christian

Wcale nie, chciałem tylko upewnić się, że sam nie łamiesz swojej reguły.

— Raphael

To dziwne, że „funkcje generujące” są wymienione jako technika nie elementarna, kiedy kombinatoryka analityczna jest najwyraźniej uważana za elementarną. wydaje się niemal z natury nie elementarną wartością; czy masz np. porównywalny dowód na asymptotykę centralnego dwumianowego współczynnika, aby lepiej zrozumieć, czego szukasz? Podejrzewam, że są ze sobą blisko spokrewnieni ...

\sqrt{π}

$\sqrt{\pi}$

— Steven Stadnicki

Ś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$

— FrankW
źródło