如何估计给定树结构中的节点数量？

Question

我正在解决一个算法问题，我必须估计在没有重复情况的情况下，

complete search

算法将调用多少次递归。

我发现它类似于树形数据结构，有一定的规则，所以我画了几张图。

但是即使我画了它，我也找不到数学表达式，所以我很沮丧。

树结构的规则如下：

1. 目标是估计树结构中存在多少个节点。
2. 给出了变量

   k

   和

   n

   。
3. 树中的每个节点中，存在

   k

   个子元素，且所有元素之和小于或等于

   n

   。
4. 节点中的所有元素均为正整数。
5. 父节点中所有元素的总和总是小于子节点的总和。 6. 树形结构中，不允许有重复的节点。

例如下图所示是满足规则的树形结构。

• 子元素数量为

  3

• (a sum of elements in node) <= 5

• 所有元素均为正整数

• 每个父节点中的元素总和小于其子节点

  (

  [root 1 1 1 -> 3] < [1 1 2 -> 4], ...

  )

下面显示了不正确的树结构。 （存在重复节点）

所以，我很好奇的是：

1. 如何在数学中表示多个节点？
2. 是否存在类似的数据结构？

Answer 1

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

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

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

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

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

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

一般公式为：

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

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

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