Sobre "La altura media de los plátanos plantados" por Knuth, de Bruijn y Rice (1972)

Estoy tratando de derivar el artículo clásico en el título solo por medios elementales (sin funciones generadoras, sin análisis complejo, sin análisis de Fourier) aunque con mucha menos precisión. En resumen, "solo" quiero demostrar que la altura promedio $h_n$ de un árbol con $n$ nodos (es decir, el número máximo de nodos desde la raíz hasta una hoja) satisface $h_n \sim \sqrt{\pi n}$ .

$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 \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}.$$ Es bien sabido que $A_{nn} = \frac{1}{n}\binom{2n-2}{n-1}$ , porque el conjunto de árboles generales con $n$ nodos está en biyección con el conjunto de árboles binarios con $n-1$ nodos, contados por los números catalanes.

Por lo tanto, el primer paso es encontrar $B_{nh}$ y luego el término principal en la expansión asintótica de $S_n$ .

En este punto, los autores utilizan la combinatoria analítica (tres páginas) para obtener

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

Mi propio intento es el siguiente. Considero la biyección entre árboles con $n$ nodos y caminos monotónicos en una cuadrícula cuadrada $(n-1) \times (n-1)$ de $(0,0)$ a $(n-1,n-1)$ que no cruzan la diagonal (y se componen de dos tipos de pasos: $\uparrow$ y $\rightarrow$ ). Estos caminos a veces se llaman caminos Dyck o excursiones . Ahora puedo expresar $B_{nh}$ en términos de rutas reticulares: es el número de rutas Dyck de longitud 2 (n-1) y altura mayor o igual que $h$ . (Nota: un árbol de altura $h$ está en biyección con una trayectoria Dyck de altura $h-1$ ).

Sin pérdida de generalidad, supongo que comienzan con (por lo tanto, permanecen por encima de la diagonal). Para cada ruta, considero el primer paso que cruza la línea , si corresponde. Desde el punto anterior, todo el camino de regreso al origen, cambio a y viceversa (esto es un reflejo wrt la línea ). Se hace evidente que los caminos que quiero contar ( ) están en biyección con los caminos monotónicos desde hasta que evitan los límites e . (Ver figura )y = x + h - 1 ↑ $\uparrow$$y = x + h - 1$$\uparrow$$\rightarrow$$y=x+h$$B_{nh}$$(-h,h)$$(n-1,n-1)$$y=x+2h+1$$y=x-1$

En el libro clásico Lattice Path Counting and Applications by Mohanty (1979, página 6) la fórmula cuenta el número de caminos monotónicos en una red de a , que evitan los límites y , con y . (Este resultado fue establecido por primera vez por los estadísticos rusos en los años 50). Por lo tanto, al considerar un nuevo origen en , satisfacemos las condiciones de la fórmula: ,

$$\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$y el punto de destino (la esquina superior derecha) es ahora . Entonces Esto se puede simplificar en que, a su vez, es equivalente a La diferencia con la fórmula esperada es que sumo sobre los números impares ( ), en lugar de todos los enteros positivos ( ).$(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],$$ $$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$

¿Alguna idea de dónde está el problema?

Las rutas monotónicas desde hasta que construye solo evitan el límite antes de que crucen por primera vez. Por lo tanto, la fórmula que utiliza no es aplicable.$(−h,h)$$(n−1,n−1)$$y=x+2h+1$$y=x+h$