树中每个节点有 k 个总和小于 n 且大于父节点总和的正整数的节点数

Question

我正在研究这个挑战：

给定

n

和

k

，想象一棵具有以下特征的有根树：

• 树中的每个节点都有

  k

  正整数值，其总和小于或等于

  n

• 节点值的总和大于其父节点值的总和（当它有父节点时）。
• 不存在具有相同顺序的相同整数值的两个节点。

对于给定的

n

和

k

，这样的树最多可以有多少个节点？

我画了几张这样的树的图表。这里有两棵满足规则的树：

这是一个不满足规则的节点，因为它有重复的节点（以橙色突出显示）：

但即使有了这些例子，我也找不到最大节点数的数学表达式。

如何找到

n

和

k

的最大节点数是多少？有没有一种数据结构可以帮助我解决这个问题？

Answer 1

首先，请注意，对于给定的 𝑛 和 𝑘，您可以形成的树不是唯一的。例如，在为重复节点着色的图像中，您有多种选择来删除哪些节点以使其余节点唯一。这意味着给定的 𝑛 和 𝑘 通常有几种可能的树。

但是，所有这些可能的树（对于给定的 𝑛 和 𝑘）中不变的是树的每个层上的节点数。

树的给定级别的节点数对应于从一组大小𝑘，重复中选择𝑖元素的方式数量，其中𝑖是级别的索引（从0开始为根）水平）。

对于 𝑘=3、𝑛=5 的示例，树的级别具有以下数量的节点：

• 第一级：((3多选0)) = 1
• 第二级：((3多选1)) = 3
• 第三级：((3多选2))=6

...总共给出 10 个节点。

一般公式为：

      _𝑖=0Σ^𝑛−𝑘 ((𝑘多选𝑖))

...其中 multichoose 运算符可以替换为二项式系数：

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