Dado un entero $h$
¿Qué es $N(h)$ el número de árboles binarios de altura de menos de $h$?
Por ejemplo, $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(Como se señalaba en TravisJ en su respuesta parcial) no puedo encontrar cualquier expresión de $N(h)$ ni un razonable límite superior.
Editar En un árbol binario (a veces llamada correcto árbol binario) cada nodo distinto de las hojas tiene dos hijos.
Aquí está mi aportación a este interesante debate. Introducir $T_{\le n}(z)$ la OGF de lleno árboles binarios de altura en la mayoría de las $n$ por el número de nodos. Ahora un árbol de altura en la mayoría de las $n$ tiene de altura en la mayoría de las $n-1$ o altura exactamente $n.$ El último árbol tiene una rama de la altura de la $n-1$ a la izquierda o a la derecha del nodo raíz o la raíz tiene dos hijos de altura $n-1.$ Esto da $$T_{\le n} = T_{\le n-1} + 2z (T_{\le n-1}-T_{\le n-2})T_{\le n-2} + z(T_{\le n-1}-T_{\le n-2})^2$$ donde $T_{\le 0} = 1$ $T_{\le 1} = z+1.$ Observar que $$T_{=n} = T_{\le n} - T_{\le n-1}.$$ Algunos de álgebra produce la forma simplificada $$T_{\le n} = T_{\le n-1} + z T_{\le n-1}^2 - z T_{\le n-2}^2.$$ Esto produce, por ejemplo, la siguiente generación de la función de los árboles de altura a más de cuatro por el número de nodos: $${z}^{15}+8\,{z}^{14}+28\,{z}^{13}+60\,{z}^{12}+94\,{z}^{11} +116\,{z}^{10}\\+114\,{z}^{9}+94\,{z}^{8}+69\,{z}^{7} +44\,{z}^{6}+26\,{z}^{5}+14\,{z}^{4}+5\,{z}^{3}+2\,{z}^{2}+z+1.$$ Para el recuento de calcular la secuencia de $T_{\le n}(1)$ que los rendimientos de $$1, 2, 5, 26, 677, 458330, 210066388901, 44127887745906175987802,\\ 1947270476915296449559703445493848930452791205,\ldots$$ Este es OEIS A003095 y tiene la forma cerrada de la recurrencia de la $$t_n = t_{n-1} + t_{n-1}^2-t_{n-2}^2$$ con $t_0=1$ $t_1=2.$ El número de árboles de altura exactamente $n$ está dado por $$t_n-t_{n-1}$$ que da la secuencia $$1, 3, 21, 651, 457653, 210065930571, 44127887745696109598901,\\ 1947270476915296449559659317606103024276803403,\ldots$$ que es OEIS A001699.
(Respuesta Parcial) En Primer Lugar, $N(3)=21$. Segundo, y probablemente más útil, se pueden construir todos los árboles de la altura de la $h$ mediante la adición de dos niños a todos los no-vacío subconjunto de los más bajos de los vértices de un árbol de altura $h-1$. Por lo tanto, si a la altura de la $h-1$ tiene árboles $T_{1},...,T_{n}$ y el árbol de $T_{i}$ $v_{i}$ vértices en el nivel más bajo, entonces el número de árboles en el nivel $h$ es
$$\sum_{i=1}^{n} (2^{v_{i}}-1).$$
Por desgracia, parece ser que no está claro cómo contar cuántas hojas están en el nivel más bajo en el recién construido árboles. Esto proporciona un algoritmo para la construcción de todos esos arboles.
Puede definir $T(h,b)$ como el número de árboles de altura $h$ $b$ hojas en la parte inferior. Su $N(h)$ es entonces la suma de más de $b$ $T(h,b)$ Para obtener un árbol de altura $h+1$ $b$ hojas en la parte inferior, tienes que elegir un árbol de altura $h$ y al menos el $b/2$ hojas en la parte inferior, a continuación, elija $b/2$ deja colgar las hojas nuevas. Esto le da una recurrencia $$T(h+1,b)=\sum_{k=b/2}^{2^h}T(h,k){k \choose b/2}$$ Tenemos $T(3,2)=8, T(3,4)=8, T(3,6)=4, T(3,8)=1$, dando el total de $21$ citado por TravisJ. A continuación,$T(4,2)=8 \cdot 2 + 8 \cdot 4 + 4 \cdot 6 + 1 \cdot 8=80, T(4,4)=8\cdot 1+8\cdot 6 + 4 \cdot 15+1\cdot 28=144, T(4,6)=8\cdot 4+4 \cdot 20+1\cdot 56=168,T(4,8)=8\cdot 1+4\cdot 15+1\cdot 70=138,T(4,10)=4\cdot 6+1\cdot 56=80,T(4,12)=4\cdot 1+1\cdot 28=32,T(4,14)=8,T(4,16)=1$, para un total de $N(4)=651$ La secuencia se da en OEIS A001699 donde se dice que el enfoque de $1.5028368...^{(2^n)}$ y algunas referencias.
Vamos a considerar todas las posibles maneras de construir un completo árbol binario de altura en la mayoría de las $h \geq 1$. La raíz ha $0$ o $2$ de los niños, por lo que una posibilidad es que el árbol es un solo nodo. Por otro lado, el número de árboles binarios tales que la raíz tiene dos hijos, es igual al cuadrado del número de árboles binarios de altura en la mayoría de las $h - 1$. Por lo tanto, obtenemos la recurrencia
\begin{align} N(0) & = 1 \\ N(h) & = N(h - 1)^2 + 1 \text{ if } h \geq 1 \end{align}
De ello se desprende que $2^{2^{h-1}}$ es un límite inferior. Por otro lado, $2^{2^{2 h}}$ es un límite superior por lo que la complejidad es doblemente exponencial. Sospecho que hay una forma cerrada así.
Tenga en cuenta que $N(3) = 26$ aquí no está en desacuerdo con las otras respuestas ya que consideran árboles de altura exactamente $h$.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
