将n个相同的球分配到若干组中，使得每组至少有k个球的方法数是多少？

Question

我正在尝试使用递归和记忆化来完成此操作，我已经确定了以下基本情况。

I）当n == k时，只有一个组具有所有球。

II）当k > n时，没有组可以至少有k个球，因此为零。

我无法从这里继续下去。如何完成这个操作？

例如，当n = 6，k = 2时， （2,2,2） （4,2） （3,3） （6）

可以形成4个不同的分组。

- A. Sam

---

尝试提出一个能够将可能性进行分区的语句，例如“每个有效的解决方案都由一个___后跟一个___组成”。如果第一个___是一个“简单”的对象，那么这将是最容易的。这个想法是，我们可以通过计算每个第一个___选择的解决方案数量，然后将它们全部加起来来计算总解决方案数。这也意味着不可能对任何一种解决方案进行两次计数（即，在第一个___的两个不同选择下）。 - j_random_hacker

如果问题是计算n个项目的列表的排序方式数量，我们可以说：“n个项目的每个排序都由其中一个项目组成，后跟其余n-1个项目的排序。” 这具有避免重复计数的重要属性：它将排序分成n个桶，根据它们的第一个项目进行划分，并且由于任何特定的排序都恰好有一个第一个项目，因此它将被准确地计算一次。 然后很容易计算n-1个项目的排序方式 - 可以使用我们刚刚编写的函数来计算n个项目的排序方式！ :) - j_random_hacker

在这个特定的问题中，如何划分解决方案就不那么明显了，因为分组的顺序并不重要——也就是说，(4,2)和(2,4)是“相同的”，所以只应该计算一次。(顺便说一下，在你的问题中应该明确说明这一点。)你能不能通过某种方式修改这个问题，来避免这种情况呢？提示：对于大多数解决方案，组列表可以用许多不同的顺序来编写；如果有一个简单的方法从这个集合中选择一个特定的顺序，你可以简单地计算解决方案的这样的排序的数量…… - j_random_hacker

Answer 1

这可以用下面描述的二维递归公式来表示：

T(0, k) = 1
T(n, k) = 0   n < k, n != 0
T(n, k) = T(n-k, k)                 +           T(n, k + 1)
             ^                                       ^
    There is a box with k balls,        No box with k balls, advance to next k
            put them 

在上述情况中，T(n,k)是指分配n个球的方案数，使得每个盒子至少得到k个球。
关键在于将k看作最少的球数，并将问题分为两种情况：是否有一个盒子恰好有k个球（如果有，则放置这些球并递归处理剩余的n-k个球），或者没有（然后以最小值k+1和相同数量的球递归处理）。

例如，计算您的示例：T(6,2)（6个球，每个盒子至少2个）：

T(6,2) = T(4,2) + T(6,3) 
T(4,2) = T(2,2) + T(4,3) = T(0,2) + T(2,3) + T(1,3) + T(4,4) =
       = T(0,2) + T(2,3) + T(1,3) + T(0,4) + T(4,5) = 
       =  1     +  0     +  0     +  1     +    0 
       = 2
T(6,3) = T(3,3) + T(6,4) = T(0,3) + T(3,4) + T(2,4) + T(6,5)
       = T(0,3) + T(3,4) + T(2,4) + T(1,5) + T(6,6) = 
       = T(0,3) + T(3,4) + T(2,4) + T(1,5) + T(0,6) + T(6,7) =
       =   1    +   0    +   0    +   0    + 1      + 0 
       = 2
T(6,2) = T(4,2) + T(6,3) = 2 + 2 = 4

使用动态规划，可以在O(n^2)时间内计算。

- amit

---

请原谅我的无知，我有些难以理解这个问题，为什么T（0，k）=1，我可以理解T（0，0）=1，因为我们满足了组中至少有k个元素的条件。 但是为什么对于T（0，1）、T（0，2）等来说它也是1呢？其次，您能否就“将k视为最小可能数量的球”在实际方面进行阐述？在第一部分中，这是否意味着有一个当前为空的盒子，我们在其中放置k个球？ - A. Sam

你能更详细或实际地解释一下 T(n-k, k) 和 T(n, k + 1) 这两种情况吗？我无法理解。 - A. Sam

@Sam T(0,k)=1，因为无论k的值如何，如果你没有球了——你可以以一种方式将它们放在盒子里。什么也不放，任何地方都不放。 - amit

@Sam 关于这两个术语：你首先要问自己，“是否有恰好有 k 个球的盒子？”如果是这样，你就把 k 个球放在一个盒子里，然后继续 - 还剩下 n-k 个球，并将刚刚填满的盒子放在一边。否则，你将 k 增加一，因为没有比 k 更少的球的盒子（问题要求），而且现在我们知道没有恰好有 k 个球的盒子，所以你可以确信所有的盒子都有 k+1 个球或更多。 - amit

Answer 2

这个问题可以很简单地解决：

桶的数量

最大桶数b可以按以下方式确定：

b = roundDown(n / k)

每个有效的分配最多可以使用b个桶。

具有x个桶的分配数量

对于给定的桶数，可以很容易地找到分配的数量：
将k个球分配到每个桶中。找到将剩余的球（r = n - k * x）分配到x个桶中的方法数量：

total_distributions(x) = bincoefficient(x , n - k * x)

编辑：这只适用于顺序很重要的情况。由于对于问题来说不那么重要，我们可以在这里使用一些技巧：

每个分布都可以映射到一个数字序列。例如：d = {d1 , d2 , ... , dx}。 我们可以轻松地生成所有以“第一个”序列{r，0，...，0}开始的这些序列，然后从左向右移动 1 。因此，下一个序列看起来像这样：{r - 1，1，...，0}。如果只生成与d1>=d2>=...>=dx匹配的序列，则不会产生重复。这个约束条件可以轻松用于优化这个搜索：我们只能在给定da-1>=db+1的情况下（其中a=b-1）将1从da移动到db ，否则就会违反数组排序的约束。要移动的1始终是最右边可移动的1。另一种思考方法是将r视为一元数，然后将该字符串简单地分成组，使得每个组至少与它的后继一样长。

 countSequences(x)
     sequence[]
     sequence[0] = r

     sequenceCount = 1

     while true
         int i = findRightmostMoveable(sequence)

         if i == -1
             return sequenceCount

         sequence[i] -= 1
         sequence[i + 1] -= 1
         sequenceCount

findRightmostMoveable(sequence)
    for i in [length(sequence) - 1 , 0)
       if sequence[i - 1] > sequence[i] + 1
           return i - 1

return -1

实际上，如果我们查看序列的结构转换（更准确地说是序列两个元素之间的差异），findRightmostMoveable可以进行一些优化。但老实说，我懒得再进一步优化了。

将所有部分组合在一起

range(1 , roundDown(n / k)).map(b -> countSequences(b)).sum()

- user4668606

---

据我理解，该解决方案假设“组”是不同的。但事实并非如此。(2,4) == (4,2)。 - amit

@amit 没有考虑到那一点。我会编辑答案。 - user4668606