查找总和为给定数字'n'的'p'数字的排列数

Question

我正在尝试解决动态编程问题,部分问题涉及查找一组'p'数字的排列数,这些数字将总和为数字'n'.p数集中的每个数字应该在0到n之间(包括0和n).

例如,如果n = 4且p = 3,则我有以下12个排列

{4,0,0},{0,4,0},{0,0,4}
{2,2,0},{2,0,2},{0,2,2}
{1,3,0},{1,0,3},{0,1,3}
{1,1,2},{1,2,1},{2,1,1}

我开始使用这种DP方法.

n(i,j) represents number of ways of representing n using i,j in p positions 

我的基本情况是

n(i,0) = n(0,i) = p   

(例如,p = 3处的n(4,0)为3,即{4,0,0},{0,4,0},0,0,4}

递归案例

n(i,j) = n(i,j-1)*n(i-1,j)

(例如:n(1,2)= n(1,1)*n(0,2)递归到n(1,0)*n(0,1)*2)

我不确定我是否正朝着正确的方向前进,因为上述方法并没有让我得到正确答案.请指导我正确的方向.

Answer 1

与我的评论相反,如果我们同时计算集合的数量和这些集合的排列,这个问题实际上更容易解决.

如果我们只需要计算而不是实际生成每个集合,我们可以直接使用一些简单的组合.让我们来解决p = 3, n = 5我们的例子并想象我们有n = 5球:

o o o o o

现在问题相当于,我们可以通过多少种方式将球分成每组3可以拥有[0, 5]球的组？想象一下,如果我们有p - 1 = 2棒可以单独放置在任何地方:在所有五个球之前,在所有五个球之后,以及在任意两个球之间.例如:

| o o | o o o => (0, 2, 3)
o | | o o o o => (1, 0, 4)
o o o o | | o => (4, 0, 1)

注意问题是如何相同的？无论如何我们可以把那些棍子,我们也可以将我们的n球分成几p组.请注意,我们只需要p - 1棍棒来生成p数字(第一个棍子之前的所有球是第一组,最后一个棍子之后的所有球是最后一组,两个棍子之间的任何球是其他组).

所以现在我们的问题是我可以通过多少方式安排n球和p - 1棍棒？你可以把它想象成有n + (p - 1)插槽而你只是在挑选n球的位置......剩下的就是木棒的位置.通过这种方式思考,我们可以应用组合学的基本公式(它已经证明了使用公理和产品规则的公理规则......不确定我是否曾经见过证据):

(n + (p - 1)) Choose n = (n + (p - 1))! / n! / (p - 1)!

所以在我们的例子中,它是7! / 5! / 2! = 21.你可以在你的例子中看到它6! / 4! / 2! = 15.你错过了一些排列(例如{0, 3, 1}).

您也可以通过简单的递归方程式解决这个问题.基本上

`f(n, p) = Sum over i = 0 to n, f(n - i, p - 1)`

并记住一些价值观f.我们的想法是,您为集合的第一个成员选择值S,然后下一个递归调用选择下一个成员,S依此类推.该基地的情况很可能会像f(0, p) = 1和f(n, 0) = 0否则你可以用递归的情况.如果您实际上并不需要这些集合,那么封闭形式显然会更高效.