给定总数、部分数量和最大加数，寻找整数划分的数量

Question

给定总数、部分数量和最大加数，寻找整数划分的数量

integercombinatoricsnumber-theory

3

我正在寻找一个整数分割的数量，总和为N，部分数量为S，最大部分恰好为X，而不需要枚举所有分割。

例如：100的所有分割中，有10个部分，最大部分为42。

我没有找到任何定理或分区身份证明来解决这个问题，并且我怀疑这是一个非平凡的问题，不能轻易地从已知的定理（例如Nijenhuis和Wilf 1978、Andrews等人2004、Bona 2006）中推导出来。

例如：具有S个部分的N的分区数等于具有S作为最大部分的N的分区数。

这个问题与我的研究相关，但它远离了纯数学。

更新：下面回答了这个问题，但我想发布我用来实现它的Python脚本。我可能会通过Cython将其加速。

n = 100 # the total
s = 10  # number of parts
x = 20  # largest part
print Partitions(n,length=s,max_part=x).cardinality() # Sage is very slow at this

def parts_nsx(n,s,x):
    if n==0 and s==0:return 1
    if n<=0 or s<=0 or x<=0:return 0
    if n>0 and s>0 and x>0:
        _sum = 0
        for i in range(0,s+1):
            _sum += parts_nsx(n-i*x, s-i, x-1)
        return _sum    
print parts_nsx(n,s,x)

- klocey

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ante · Accepted Answer

对于这个分区数量的递归P(n,s,x)成立：

P(n,s,x) = sum P(n-i*x, s-i, x-1), for i=0,...,s 
P(0,0,x) = 1
P(n,s,x) = 0, if n <= 0 or s <= 0 or x <= 0

计算效率不高，也许在你的例子中足够快。

最好使用记忆化实现。

编辑：

带有记忆化的Python实现：

D = {}
def P(n,s,x):
  if n > s*x or x <= 0: return 0
  if n == s*x: return 1
  if (n,s,x) not in D:
    D[(n,s,x)] = sum(P(n-i*x, s-i, x-1) for i in xrange(s))
  return D[(n,s,x)]

P(100, 10, 42)
2685871

更新：

满足参数 n，s，x 的分区可以有最大尺寸为 x 的 i 个分区。通过删除这些具有尺寸 x 的 i 部分，我们得到具有参数 n-i*x，s-i，x-1 的相同问题。例如，具有10个部分和42作为最大部分的100的分区，可以具有0、1或2个大小为42的部分。

P(0,0,x) = 1 表示我们在之前的迭代中已经有了分区。

P(n,s,x) = 0，如果 n>s*x 表示我们不能使用所有最大尺寸的分区对 n 进行分区，因此不可能组合参数。边界条件为