Dada una constante k, encuentre el árbol enraizado más grande posible, si para cada camino de raíz a hoja, la suma de la aridad de sus nodos es igual a k?

Como ejemplo, aquí están todos los árboles posibles para el caso : en cada nodo escrito está su aridad (= el número de hijos).$k=3$

Si bien esto debería resolverse mediante programación dinámica, creo que hubo un resultado combinatorio en esto (ya sea exacto o un límite superior de grano fino). ¿Alguien lo sabe?

Editar:

El tamaño del árbol es la cantidad de nodos que tiene, por lo que el árbol más grande sería el que tenga la cantidad máxima de nodos.

Dejar $B(n)$ ser del tamaño del árbol más grande, donde las aridades de cada camino desde la raíz hasta la hoja se suman a $n$.

Si la raíz de tal árbol tiene aridad $k$, luego los caminos para cada una de las $k$ los subárboles deben sumar hasta $n-k$. Como los subárboles deben ser óptimos, el árbol tiene tamaño$1+k\cdot B(n-k)$.

Una fórmula para $B(n)$ simplemente maximiza esa expresión sobre $k$, utilizando los valores anteriores $B(n-1), B(n-2),\dots$.

Traté de hacer esto a mano y encontré (con la ayuda de @Sudix, gracias) $1,2,3,5,7,11,16,23,34,\dots$. Esto parece ser A239288 en Sloanes Online Encyclopedia of Integer Sequences. La recursividad dada allí es similar, pero no exactamente la misma.

La explicación de la secuencia allí es: "Suma máxima de x0 + x0 * x1 + ... + x0 * x1 * ... * xk sobre todas las composiciones x0 + ... + xk = n". De hecho, esa es la misma secuencia: si la secuencia de aridades a lo largo del camino desde la raíz es x0, x1, ..., xk, estas deberían sumar n, y el número de nodos es la fórmula dada.

Otro comentario en Sloane es interesante: "Para n> = 8 la solución se vuelve cíclica: a (3n + k) = 3 + 3a (3n - 3 + k)". Esto parece sugerir que para valores mayores de 24 la raíz del árbol siempre tiene tres hijos.