Cuenta cuántos árboles binarios hay con n nodos.
El conteo de árboles binarios es un problema fundamental en la combinatoria enumerativa que pregunta por el número de árboles binarios distintos que puedes construir usando $n$ nodos sin etiquetas. En un árbol binario, cada nodo tiene a lo mucho dos hijos, que distingues como el hijo izquierdo y el hijo derecho. Algo muy importante es que el orden de los hijos importa; un árbol que solo tiene un hijo izquierdo es diferente a uno que solo tiene un hijo derecho. Esta distinción estructural diferencia a los árboles binarios de los árboles planos con raíz generales, aunque hay bijecciones entre variaciones específicas de estas estructuras.
Este concepto es central para el estudio de los números de Catalan, ya que el número de árboles binarios con $n$ nodos te lo da el $n$-ésimo número de Catalan, $C_n$. Te vas a encontrar este problema seguido en el análisis de algoritmos de computación (por ejemplo, para contar cuántos árboles binarios de búsqueda estructuralmente únicos existen) y aparece mucho en competencias como el AIME y la USAMO. Sirve como un puente entre interpretaciones geométricas (como caminos en una cuadrícula) y estructuras algebraicas (como el uso de paréntesis).
La idea clave para contar árboles binarios está en una descomposición recursiva. Un árbol binario que no está vacío consiste en un nodo raíz, un subárbol izquierdo y un subárbol derecho. Si el número total de nodos es $n$, y el subárbol izquierdo tiene $k$