Pada “Tinggi Rata-Rata Pohon Pesawat yang Ditanam” oleh Knuth, de Bruijn dan Rice (1972)

Saya mencoba untuk mendapatkan makalah klasik dalam judul hanya dengan cara dasar (tidak ada fungsi menghasilkan, tidak ada analisis kompleks, tidak ada analisis Fourier) walaupun dengan presisi jauh lebih sedikit. Singkatnya, saya "hanya" ingin membuktikan bahwa tinggi rata-rata $h_n$ dari sebuah pohon dengan $n$ simpul (yaitu, jumlah maksimum simpul dari akar ke daun) memuaskan $h_n \sim \sqrt{\pi n}$ .

Garis besarnya adalah sebagai berikut. Misalkan adalah jumlah pohon dengan tinggi kurang dari atau sama dengan h (dengan konvensi A n h = A n n untuk semua h ⩾ n ) dan B n h jumlah pohon n node dengan tinggi lebih besar dari atau sama dengan h + 1 (yaitu, B n h = A n n - A n h ). Kemudian h n = S $A_{nh}$$h$$A_{nh} = A_{nn}$$h \geqslant n$$B_{nh}$$n$$h+1$$B_{nh} = A_{nn} - A_{nh}$ , di mana S n adalah jumlah terbatas S n = ∑ h ⩾ 1 h ( A n h - A n , h - 1 ) = ∑ h ⩾ 1 h ( B n , h - 1 - B n h ) = ∑ h ⩾ 0 B n h . Diketahui bahwa A $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}.$$ , untuk himpunan pohon - pohon umum dengannnode berada dalam penimbunan dengan himpunan pohon biner dengann-1node, dihitung dengan angka Catalan.$A_{nn} = \frac{1}{n}\binom{2n-2}{n-1}$$n$$n-1$

Oleh karena itu, langkah pertama adalah menemukan dan kemudian istilah utama dalam ekspansi asimptotik S n .$B_{nh}$$S_n$

Pada titik ini penulis menggunakan kombinatorik analitik (tiga halaman) untuk mendapatkan

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

Upaya saya sendiri adalah sebagai berikut. Saya menganggap bijih antara pohon dengan node dan jalur monoton pada kotak persegi ( n - 1 ) × ( n - 1 ) dari ( 0 , 0 ) hingga ( n - 1 , n - 1 ) yang tidak melintasi diagonal ( dan terbuat dari dua jenis langkah: ↑ dan → ). Jalur ini kadang-kadang disebut jalur Dyck atau kunjungan . Saya dapat mengekspresikan sekarang B $n$$(n-1) \times (n-1)$$(0,0)$$(n-1,n-1)$$\uparrow$$\rightarrow$ dalam hal lattice paths: itu adalah jumlah lintasan Dyck dengan panjang 2 (n-1) dan tingginya lebih dari atau sama denganh. (Catatan: sebatang pohon dengan ketinggianhberada di bijection dengan lintasan Dyck dengan ketinggianh-1.)$B_{nh}$$h$$h$$h-1$

Tanpa kehilangan keumuman, saya berasumsi bahwa mereka mulai dengan (karenanya tetap di atas diagonal). Untuk setiap jalur, saya menganggap langkah pertama melintasi garis y = x + h - 1 , jika ada. Dari titik di atas, sepanjang perjalanan kembali ke titik asal, saya mengubah ↑ menjadi → dan sebaliknya (ini adalah cerminan dari garis y = x + h ). Menjadi jelas bahwa jalur yang ingin saya hitung ( B n h ) berada dalam penyatuan dengan jalur monoton dari ( - h , h ) hingga$\uparrow$$y = x + h - 1$$\uparrow$$\rightarrow$$y=x+h$$B_{nh}$$(-h,h)$ yang menghindari batas y = x + 2 jam + 1 dan y = x - 1 . (Lihatgambar.)$(n-1,n-1)$$y=x+2h+1$$y=x-1$

Dalam buku klasik Lattice Path Counting and Applications oleh Mohanty (1979, halaman 6) rumus menghitung jumlah jalur monoton dalam kisi dari(0,0)hingga(m,n), yang menghindari batasy=x-tdany=x+s, dengant>0dans>0. (Hasil ini pertama kali didirikan oleh ahli statistik Rusia pada 50-an.) Oleh karena itu, dengan mempertimbangkan asal baru di

$$\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$ , kami memenuhi ketentuan rumus: s = 1 , t = 2 h + 1 dan titik tujuan (sudut kanan atas) sekarang ( n + h - 1 , n - h - 1 ) . Kemudian B n h = ∑ k ∈ Z [ ( 2 n - $(-h,h)$$s=1$$t=2h+1$$(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],$$ which, in turn, is equivalent to $$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].$$ The difference with the expected formula is that I sum over the odd numbers ($2k+1$), instead of all positive integers ($k$).

Any idea where the problem is?

Jalur monotonik dari $(−h,h)$ untuk $(n−1,n−1)$ Anda membangun hanya menghindari batas $y=x+2h+1$ sebelum mereka menyeberang $y=x+h$untuk pertama kalinya. Dengan demikian rumus yang Anda gunakan tidak berlaku.