Number of nodes in tree where each node has k positive integers whose sum is less than n, and greater than parent's sum

I am looking into this challenge:

Given n and k, imagine a rooted tree with the following characteristics:

Each node in the tree has k positive integer values whose sum is less or equal to n

The sum of a node's values is greater than the sum of its parent's values (when it has a parent).

There are no two nodes that have the same integer values in the same order.

What is the maximum number of nodes such a tree can have for given n and k?

I drew a couple of diagrams of such trees. Here are two trees that satisfy the rules:

Here is one that does not satisfy the rules, because it has duplicate nodes (highlighted in orange):

But even with these examples I couldn't find a mathematical expression for the maximum number of nodes.

How can I find what the maximum number of nodes is in terms of n and k? Is there a data structure that can help me with this?

Solution

First of all, note that for a given 𝑛 and 𝑘, the tree that you can form is not unique. For instance, in the image where you colored duplicate nodes, you have several choices concerning which nodes to remove in order to make the remaining ones unique. This means there are usually several possible trees for a given 𝑛 and 𝑘.

However, what is invariant in all these possible trees (for a given 𝑛 and 𝑘) is the number of nodes on each level of the tree.

The number of nodes at a given level of the tree corresponds to the number of ways you can select 𝑖 elements from a set of size 𝑘, with repetition, where 𝑖 is the index of the level (starting at 0 for the root level).

For your example with 𝑘=3, 𝑛=5, the levels of the tree have these number of nodes:

first level: ((3 multichoose 0)) = 1
second level: ((3 multichoose 1)) = 3
third level: ((3 multichoose 2)) = 6

...giving a total of 10 nodes.

The general formula is:

_𝑖=0∑^𝑛−𝑘 ((𝑘 multichoose 𝑖))

...where the multichoose operator can be replaced with a binomial coefficient:

_𝑖=0∑^𝑛−𝑘 _{𝑘+𝑖−1}𝐶_𝑖