7
$\begingroup$

As an example, here are all possible trees for the case $k=3$: enter image description here 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.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Define biggest. $\endgroup$
    – idoby
    Commented Jan 27, 2019 at 9:47
  • $\begingroup$ 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.) $\endgroup$
    – j_random_hacker
    Commented Jan 27, 2019 at 16:38
  • $\begingroup$ @j_random_hacker Yes, you're completely right. I'll correct the question. $\endgroup$
    – Sudix
    Commented Jan 28, 2019 at 12:53

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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\\$ $\endgroup$
    – Sudix
    Commented Jan 28, 2019 at 13:20
  • 2
    $\begingroup$ 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/… $\endgroup$
    – Sudix
    Commented Jan 28, 2019 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.