在给定总数、部分数和最大被加数的情况下查找整数分区的数量

我正在寻找总共 N 个整数分区的数量，其中多个部分为 S，最大部分恰好为 X，而无需枚举所有分区。

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

我没有找到解决这个问题的定理或分区恒等式，我怀疑这是一个不平凡的问题，不容易从已知定理中推导出来（例如 Nijenhuis 和 Wilf 1978、Andrews 等人 2004、Bona 2006）：

例如：N 中恰好有 S 个部分的分区数量等于 N 中恰好有 S 部分为最大部分的分区数量。

这个问题与我的研究有关，这远远超出了纯数学的范围。

Update：这个问题在下面得到了回答，但我想发布我用来实现它的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) 

对于这个数量的分区递归P(n,s,x) holds:

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

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

最好使用记忆法来实现。

Edit:

具有记忆功能的 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

Update:

满足参数的分区n,s,x可以有i最大尺寸的分区x。 通过删除这些i有尺寸的零件x我们在参数方面遇到了同样的问题n-i*x, s-i, x-1。 例如。 100 的分区有 10 个部分，42 作为最大部分，可以有 0、1 或 2 个大小为 42 的部分。

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

P(n,s,x) = 0, if n>s*x意味着我们不能用最大大小的所有分区对 n 进行分区，因此参数的组合是不可能的。 边界条件是