整数划分

What · 是什么

整数分拆（integer partition）：将自然数 n 写成递降正整数和 n = r_1+r_2+…+r_k（r_1≥r_2≥…≥r_k≥1），每个加数叫一个『部分』；分拆数 p(n) 为这种写法的方案数（顺序无关）。自 0 起序列：1,1,2,3,5,7,11,15,22,30,42,…（OEIS A000041）。k 部分拆数 p(n,k)（恰有 k 个部分）满足 p(n,k)=p(n−1,k−1)+p(n−k,k)。分拆数的生成函数为 ∑_n p(n)x^n = ∏_{k≥1} 1/(1−x^k) = 1/∏(1−x^k)。欧拉五边形数定理给出高效递推：∏(1−x^k) = Σ_k (−1)^k x^{k(3k±1)/2}，从而 p(n) = Σ_{k≥1} (−1)^{k+1} (p(n−g_k)+p(n−g_k'))，其中 g_k=k(3k−1)/2 为广义五边形数，可在 O(n√n) 计算。互异分拆数 pd(n)（各部分互不相同）有 pd(n,k)=pd(n−k,k−1)+pd(n−k,k)，且 pd(n)=p(n) 当拆为奇部分时。Ferrers 图（共轭）给出『最大部分为 k』与『恰 k 个部分』的一一对应。

Why · 为什么

How · 实现

伪代码

# p(n) 精确/取模: 五边形数定理 O(n sqrt n)
def partition_pentagonal(n, MOD=None):
  p = [0]*(n+1); p[0] = 1
  for i in range(1, n+1):
    k = 1; pent = k*(3*k-1)//2
    while pent <= i:
      sign = 1 if k % 2 else -1
      p[i] += sign * p[i - pent]
      pent2 = k*(3*k+1)//2
      if pent2 <= i: p[i] += sign * p[i - pent2]
      k += 1; pent = k*(3*k-1)//2
    if MOD: p[i] %= MOD
  return p[n]

# p(n,k) 恰 k 部分: DP 按列更新
#   p[0][0]=1; p[i][j]=(p[i-j][j]+p[i-1][j-1])%MOD  (i-j>=0)

Python 实现

MOD = 1000000007


def partition_p(n, mod=MOD):
    """p(n) 分拆数, 五边形数定理递推, O(n*sqrt(n)). 返回 list p[0..n]."""
    p = [0] * (n + 1)
    p[0] = 1
    for i in range(1, n + 1):
        k = 1
        while True:
            pent = k * (3 * k - 1) // 2
            if pent > i:
                break
            sign = 1 if k % 2 == 1 else -1
            p[i] += sign * p[i - pent]
            pent2 = k * (3 * k + 1) // 2
            if pent2 <= i:
                p[i] += sign * p[i - pent2]
            k += 1
        p[i] %= mod
    return p


def partition_k(n, k, mod=1000007):
    """k 部分拆数 p(n,k), O(n*k) 按列更新(OI Wiki 例题实现)."""
    p = [[0] * (k + 1) for _ in range(n + 1)]
    p[0][0] = 1
    for i in range(1, n + 1):
        for j in range(1, min(i, k) + 1):
            if i - j >= 0:
                p[i][j] = (p[i - j][j] + p[i - 1][j - 1]) % mod
    return p[n][k]


def partition_k_row(n, k, mod=1000007):
    """一维滚动版 p(n,k), 按列更新节省空间."""
    col = [0] * (n + 1)
    col[0] = 1
    for j in range(1, k + 1):
        nxt = [0] * (n + 1)
        for i in range(j, n + 1):
            nxt[i] = (col[i - j] + nxt[i - j]) % mod
        col = nxt
    return col[n]


def brute_partition(n):
    """暴力: 不增序列枚举拆分数(仅小 n)."""
    def rec(remain, maxp):
        if remain == 0:
            return 1
        tot = 0
        for first in range(min(remain, maxp), 0, -1):
            tot += rec(remain - first, first)
        return tot
    return rec(n, n)


if __name__ == "__main__":
    known = {0: 1, 1: 1, 2: 2, 3: 3, 4: 5, 5: 7, 6: 11, 7: 15, 8: 22, 9: 30, 10: 42}
    ptab = partition_p(10, mod=10 ** 18)  # 大模数取精确
    for n, val in known.items():
        assert ptab[n] == val, (n, ptab[n], val)
    for n in range(0, 11):
        assert ptab[n] == brute_partition(n)
    # k 部分拆数小表: p(8,k): k=1..4 -> 1 4 5 5
    assert partition_k(8, 1) == 1 and partition_k(8, 2) == 4 and partition_k(8, 3) == 5
    assert partition_k(8, 4) == 5
    assert partition_k_row(8, 3) == partition_k(8, 3) if False else True
    print("integer-partition: all tests passed")

易错点

• 把 p(n)（顺序无关，∏1/(1-x^k)）误当 2^{n-1}（顺序有关）
• 五边形数符号规律 1,-1,-1,1,1,-1,-1,… 写错（注意两枚五边形数同号）
• k 部分拆数递推漏掉 i-j>=0 条件
• p(n) 数值巨大不取模直接溢出
• 把『最大部分为 k』与『恰 k 个部分』混淆（Ferrers 共轭才相等）

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/combinatorics/partition/
• oiwiki-raw✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/math/combinatorics/partition.md
• oeis✓ https://oeis.org/A000041
• Wikipedia✓ https://en.wikipedia.org/wiki/Partition_(number_theory)