Given a constant k, find the biggest possible rooted tree, if for every path from root to leaf, the sum of the arity of its nodes equals k?

As an example, here are all possible trees for the case $k=3$:

On each node written is its arity (= the number of children).

While this should be solvable by dynamic programming, I think there was a combinatoric result on this (either exact or a rather fine grained upper bound). Does anybody know it?

Edit:

The size of the tree is the number of nodes it has, so the biggest tree would be the one with the maximum number of nodes.

Let $B(n)$ be the size of the largest tree, where the arities of each path from root to leaf add up to $n$.

If the root of such a tree has arity $k$, then the paths for each of the $k$ subtrees must add up to $n-k$. As the subtrees must be optimal, the tree has size $1+k\cdot B(n-k)$.

A formula for $B(n)$ just maximizes that expression over $k$, using the previous values $B(n-1), B(n-2),\dots$.

I tried to do this by hand, and found (with the help of @Sudix, thanks) $1,2,3,5,7,11,16,23,34,\dots$. This seems to be A239288 in Sloanes Online Encyclopedia of Integer Sequences. The recursion given there is similar, but not exactly the same.

The explanation of the sequence there is: "Maximal sum of x0 + x0x1 + ... + x0x1...xk over all compositions x0 + ... + xk = n". That indeed is the same sequence: if the sequence of arities along the path from the root is x0, x1,..., xk these should sum to n, and the number of nodes indeed is the given formula.

Another remark at Sloane is interesting: "For n >= 8 the solution becomes cyclic: a(3n + k) = 3 + 3a(3n - 3 + k)". This seems to suggest that for values larger than 24 the root of the tree always has three children.

StackExchange Computer Science Q#103453, answer score: 4