Sobre "A altura média das árvores planas plantadas", de Knuth, de Bruijn e Rice (1972)

Estou tentando derivar o artigo clássico no título apenas por meios elementares (sem funções geradoras, sem análise complexa, sem análise de Fourier), embora com muito menos precisão. Em resumo, "apenas" quero provar que a altura média $h_n$ de uma árvore com $n$ nós (ou seja, o número máximo de nós da raiz até uma folha) satisfaz .$h_n \sim \sqrt{\pi n}$

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}$, pois o conjunto de árvores gerais com $n$ nós está em bijeção com o conjunto de árvores binárias com $n-1$ nós, contados pelos números catalães.

Portanto, o primeiro passo é encontrar $B_{nh}$ e, em seguida, o termo principal na expansão assintótica de $S_n$ .

Neste ponto, os autores usam combinatória analítica (três páginas) para derivar

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

Minha própria tentativa é a seguinte. Considero a bijeção entre árvores com $n$ nós e caminhos monotônicos em uma grade quadrada $(n-1) \times (n-1)$ de $(0,0)$ a $(n-1,n-1)$ que não cruzam a diagonal (e são feitos de dois tipos de etapas: $\uparrow$ e $\rightarrow$ ). Esses caminhos são chamados de caminhos Dyck ou excursões . Posso expressar agora $B_{nh}$ em termos de caminhos de treliça: é o número de caminhos Dyck de comprimento 2 (n-1) e altura maior ou igual a $h$ . (Nota: uma árvore de altura $h$ está em bijeção com um caminho Dyck de altura $h-1$ .)

Sem perda de generalidade, presumo que eles começam com $\uparrow$ (portanto permaneçam acima da diagonal). Para cada caminho, considero o primeiro passo que cruza a linha $y = x + h - 1$ , se houver. Do ponto acima, todo o caminho de volta à origem, mudo $\uparrow$ para $\rightarrow$ e vice-versa (este é um reflexo na linha $y=x+h$ ). Torna-se aparente que os caminhos que eu quero contar ( $B_{nh}$ ) estão em bijeção com os caminhos monotônicos de $(-h,h)$ a $(n-1,n-1)$ que evitam os limites $y=x+2h+1$ e $y=x-1$ . (Veja a figura .)

No livro clássico Lattice Path Counting and Applications de Mohanty (1979, página 6), a fórmula conta o número de caminhos monotônicos em uma rede de a , o que evita os limites e , com e . (Este resultado foi estabelecido pela primeira vez por estatísticos russos nos anos 50.) Portanto, considerando uma nova origem em , satisfazemos as condições da fórmula: ,(0,0)(m,n)y=x-ty=x+st>0s>0(-h,h)s=

$$\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$e o ponto de destino (canto superior direito) é agora . Então Isso pode ser simplificado em que, por sua vez, é equivalente a A diferença com a fórmula esperada é que somamos os números ímpares ( ), em vez de todos os números inteiros positivos ( ).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$

Alguma idéia de onde está o problema?

Os caminhos monotônicos de a que você constrói apenas evitam o limite antes que eles cruzem$(−h,h)$$(n−1,n−1)$$y=x+2h+1$ pela primeira vez. Portanto, a fórmula que você usa não é aplicável.$y=x+h$