# 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.

• Define biggest. – idoby Jan 27 '19 at 9:47
• You probably mean "every path from the root to a leaf", as otherwise the 1-vertex tree is the only solution. (Also it would be better to explicitly say that you're talking about a rooted tree -- unrooted trees are also possible.) – j_random_hacker Jan 27 '19 at 16:38
• @j_random_hacker Yes, you're completely right. I'll correct the question. – Sudix Jan 28 '19 at 12:53

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 + x0*x1 + ... + x0*x1*...*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.

• So, to put it into one formula, the recursion to solve/estimate is: $B(n) = 1+\max_{1\le k\le n}k\cdot B(n-k)\\ B(0) = 1\\$ – Sudix Jan 28 '19 at 13:20
• I think in your sequence you've missed a step, I've got: '1, 2, 3, 5, 7, 11, 16, 23, 34, 49, 70, 103, 148, 211, 310, 445, 634, 931, 1336, 1903, 2794, 4009, 5710, 8383, 12028, 17131'; If I didn't misscalculate, there's an [OEIS][1] entry for the series-1. [1]: oeis.org/… – Sudix Jan 28 '19 at 13:32