Dada uma constante k, encontre a maior árvore enraizada possível, se para cada caminho de raiz a folha, a soma da aridade de seus nós for igual a k?

Como exemplo, aqui estão todas as árvores possíveis para o caso $k=3$: Em cada nó gravado está sua aridade (= o número de filhos).

Embora isso deva ser solucionado pela programação dinâmica, acho que houve um resultado combinatório nisso (limite superior exato ou bastante refinado). Alguém sabe disso?

Editar:

O tamanho da árvore é o número de nós que possui; portanto, a maior árvore seria aquela com o número máximo de nós.

Deixei $B(n)$ ser o tamanho da maior árvore, onde as áreas de cada caminho, da raiz às folhas, somam $n$.

Se a raiz de uma árvore tiver aridade $k$, os caminhos para cada um dos $k$ subárvores devem somar até $n-k$. Como as subárvores devem ser ótimas, a árvore tem tamanho$1+k\cdot B(n-k)$.

Uma fórmula para $B(n)$ apenas maximiza essa expressão sobre $k$, usando os valores anteriores $B(n-1), B(n-2),\dots$.

Tentei fazer isso manualmente e encontrei (com a ajuda do @Sudix, obrigado) $1,2,3,5,7,11,16,23,34,\dots$. Parece ser A239288 na Enciclopédia Online Sloanes de Sequências Inteiras. A recursão dada lá é semelhante, mas não exatamente a mesma.

A explicação da sequência é: "Soma máxima de x0 + x0 * x1 + ... + x0 * x1 * ... * xk em todas as composições x0 + ... + xk = n". Essa é realmente a mesma sequência: se a sequência de aridades ao longo do caminho a partir da raiz for x0, x1, ..., xk, elas devem somar n, e o número de nós de fato é a fórmula fornecida.

Outra observação em Sloane é interessante: "Para n> = 8, a solução se torna cíclica: a (3n + k) = 3 + 3a (3n - 3 + k)". Isso parece sugerir que, para valores maiores que 24, a raiz da árvore sempre tenha três filhos.