En “La altura media de los árboles plantados Plano” por Knuth, de Bruijn y Rice (1972)

Question

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

El esquema es el siguiente. Deje $ A_ {NH} $ es el número de árboles con altura menor o igual a $ h $ (con la convención $ A_ {NH} = A_ {nn} $ para todos $ h \ geqslant n $) y $ B_ { nh} $ el número de árboles de $ n $ nodos con mayor altura que o igual a $ h + 1 $ (es decir, $ B_ {nh} = A_ {nn} - A_ {nh} $). Entonces $ h_n = S_n / A_ {nn} $, donde $ $ S_n es la suma finita $$ 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} $, para 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 catalana.

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 combinatoria analíticos (tres 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]. $$

Mi propio intento es el siguiente. Considero que la biyección entre los árboles con $ n $ nodos y caminos monotónicas en una rejilla cuadrada $ (n-1) \ times (n-1) $ de $ (0,0) $ hasta $ (n-1, n-1) $ que no cruzan la diagonal (y son hecho de dos tipos de medidas: $ \ uparrow $ y $ \ rightarrow $). Estos caminos a veces se llaman caminos Dyck o excursiones . Puedo expresar ahora B_ {nh} $ $ en términos de caminos de celosía: es el número de trayectorias Dyck de longitud 2 (n-1) y una mayor altura que o igual a $ h $. (Nota:. Un árbol de altura h $ $ está en biyección con un camino Dyck de altura $ h-1 $)

Sin pérdida de generalidad, que supongo que comienzan con $ \ uparrow $ (por lo tanto mantenerse por encima de la diagonal). Para cada ruta, considero que el primer paso de cruzar la línea $ y = x + h - 1 $, si los hay. Desde el punto anterior, toda la parte posterior paso al origen, cambio $ \ uparrow $ en $ \ rightarrow $ y viceversa (esto es un reflexión WRT la línea $ y = x + h $) . Se hace evidente que los caminos que desea contar ($ B_ {NH} $) están en biyección con las trayectorias monótonas de $ (- H, H) $ a $ (n-1, n-1) $ que eviten los límites $ y = x + 2h + 1 $ y $ y = x-1 $. (Ver figura .)

En el libro clásico Entramado Conteo Path y Aplicaciones por Mohanty (1979, página 6) la fórmula $$ \ Sum_ {k \ in \ mathbb {Z}} \ left [\ Binom {m + n} {mk (t + s)} - \ Binom {m + n} {n + k (t + s) + t} \derecho], $$ cuenta el número de trayectorias monótonas en una red de $ (0,0) $ hasta $ (m, n) $, que evitan los límites $ y = x - t $ y $ y = x + s $, con $ t> 0 $ y $ s> 0 $. (Este resultado se estableció por primera vez por los estadísticos rusos en los años 50). Por tanto, considerando un nuevo origen en $ (- h, h) $, que satisfacen las condiciones de la fórmula: $ s = 1 $, $ t = 2h + 1 $ y el punto de destino (la esquina superior derecha) es ahora $ (n + h-1, NH-1) $. Luego $$ B_ {nh} = \ sum_ {k \ in \ mathbb {Z}} \ left [\ Binom {2n-2} {n + h-1-k (2h + 2)} - \ Binom {2n-2} { nh-1 + k (2h + 2) + 2h + 1} \ right]. $$ Esto se puede simplificar en $$ 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], $$ que, a su vez, es equivalente a $$ 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]. $$ La diferencia con la fórmula esperada es que suma sobre los números impares ($ 2k + 1 $), en lugar de todos los enteros positivos ($ k $).

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

Answer 1

Las trayectorias monótonas de $ (- h, h) $ hasta $ (n-1, n-1) $ que se construye sólo evitan el límite $ y = x + 2h + 1 $ antes de que crucen $ y = x + h $ por primera vez. Así, la fórmula que utiliza no es aplicable.