跳转至

# 分拆数

分拆：将自然数 𝑛 n 写成递降正整数和的表示．

𝑛=𝑟 1+𝑟 2+…+𝑟 𝑘 𝑟 1≥𝑟 2≥…≥𝑟 𝑘≥1 n=r 1+r 2+…+r k r 1≥r 2≥…≥r k≥1

和式中每个正整数称为一个部分．

分拆数：𝑝 𝑛 p n．自然数 𝑛 n 的分拆方法数．

自 0 0 开始的分拆数：

n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
--- | --- | --- | --- | --- | --- | --- | --- | --- | ---
𝑝 𝑛 p n | 1 | 1 | 2 | 3 | 5 | 7 | 11 | 15 | 22

## k 部分拆数

将 𝑛 n 分成恰有 𝑘 k 个部分的分拆，称为 𝑘 k 部分拆数，记作 𝑝(𝑛,𝑘)p(n,k)．

显然，𝑘 k 部分拆数 𝑝(𝑛,𝑘)p(n,k) 同时也是下面方程的解数：

𝑛−𝑘=𝑦 1+𝑦 2+…+𝑦 𝑘 𝑦 1≥𝑦 2≥…≥𝑦 𝑘≥0 n−k=y 1+y 2+…+y k y 1≥y 2≥…≥y k≥0

如果这个方程里面恰有 𝑗 j 个部分非 0，则恰有 𝑝(𝑛 −𝑘,𝑗)p(n−k,j) 个解．因此有和式：

𝑝(𝑛,𝑘)=𝑘∑𝑗=0 𝑝(𝑛−𝑘,𝑗)p(n,k)=∑j=0 k p(n−k,j)

相邻两个和式作差，得：

𝑝(𝑛,𝑘)=𝑝(𝑛−1,𝑘−1)+𝑝(𝑛−𝑘,𝑘)p(n,k)=p(n−1,k−1)+p(n−k,k)

如果列出表格，每个格里的数，等于左上方的数，加上该格向上方数，所在列数个格子中的数．

k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
--- | --- | --- | --- | --- | --- | --- | --- | --- | ---
𝑝(0,𝑘)p(0,k) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
𝑝(1,𝑘)p(1,k) | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0
𝑝(2,𝑘)p(2,k) | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0
𝑝(3,𝑘)p(3,k) | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0
𝑝(4,𝑘)p(4,k) | 0 | 1 | 2 | 1 | 1 | 0 | 0 | 0 | 0
𝑝(5,𝑘)p(5,k) | 0 | 1 | 2 | 2 | 1 | 1 | 0 | 0 | 0
𝑝(6,𝑘)p(6,k) | 0 | 1 | 3 | 3 | 2 | 1 | 1 | 0 | 0
𝑝(7,𝑘)p(7,k) | 0 | 1 | 3 | 4 | 3 | 2 | 1 | 1 | 0
𝑝(8,𝑘)p(8,k) | 0 | 1 | 4 | 5 | 5 | 3 | 2 | 1 | 1

### 例题

计算 k 部分拆数

计算 𝑘 k 部分拆数 𝑝(𝑛,𝑘)p(n,k)．多组输入，其中 𝑛 n 上界为 1 0 0 0 0 10000，𝑘 k 上界为 1 0 0 0 1000，对 1 0 0 0 0 0 7 1000007 取模．

观察表格与递推式，按列更新对于存储更有利．不难写出程序：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    #include <cstdio>
    #include <cstring>

    int p[10005][1005]; /*将自然数n分拆为k个部分的方法数*/

    int main() {
      int n, k;
      while (~scanf("%d%d", &n, &k)) {
        memset(p, 0, sizeof(p));
        p[0][0] = 1;
        int i;
        for (i = 1; i <= n; ++i) {
          int j;
          for (j = 1; j <= k; ++j) {
            if (i - j >= 0) /*p[i-j][j]所有部分大于1*/
            {
              p[i][j] = (p[i - j][j] + p[i - 1][j - 1]) %
                        1000007; /*p[i-1][j-1]至少有一个部分为1．*/
            }
          }
        }
        printf("%d\n", p[n][k]);
      }
    }

### 生成函数

由等比数列求和公式，有：

1 1−𝑥 𝑘=1+𝑥 𝑘+𝑥 2 𝑘+𝑥 3 𝑘+…1 1−x k=1+x k+x 2 k+x 3 k+…1+𝑝 1 𝑥+𝑝 2 𝑥 2+𝑝 3 𝑥 3+…=1 1−𝑥 1 1−𝑥 2 1 1−𝑥 3…1+p 1 x+p 2 x 2+p 3 x 3+…=1 1−x 1 1−x 2 1 1−x 3…

对于 𝑘 k 部分拆数，生成函数稍微复杂．具体写出如下：

∞∑𝑛,𝑘=0 𝑝(𝑛,𝑘)𝑥 𝑛 𝑦 𝑘=1 1−𝑥 𝑦 1 1−𝑥 2 𝑦 1 1−𝑥 3 𝑦…∑n,k=0∞p(n,k)x n y k=1 1−x y 1 1−x 2 y 1 1−x 3 y…

### Ferrers 图

Ferrers 图：将分拆的每个部分用点组成的行表示．每行点的个数为这个部分的大小．

根据分拆的定义，Ferrers 图中不同的行按照递减的次序排放．最长行在最上面．

例如：分拆 1 2 =5 +4 +2 +1 12=5+4+2+1 的 Ferrers 图．

将一个 Ferrers 图沿着对角线翻转，得到的新 Ferrers 图称为原图的共轭，新分拆称为原分拆的共轭．显然，共轭是对称的关系．

例如上述分拆 1 2 =5 +4 +2 +1 12=5+4+2+1 的共轭是分拆 1 2 =4 +3 +2 +2 +1 12=4+3+2+2+1．

最大 𝑘 k 分拆数：自然数 𝑛 n 的最大部分为 𝑘 k 的分拆个数．

根据共轭的定义，有显然结论：

最大 𝑘 k 分拆数与 𝑘 k 部分拆数相同，均为 𝑝(𝑛,𝑘)p(n,k)．

## 互异分拆数

互异分拆数：𝑝 𝑑 𝑛 p d n．自然数 𝑛 n 的各部分互不相同的分拆方法数．（Different）

n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
--- | --- | --- | --- | --- | --- | --- | --- | --- | ---
𝑝 𝑑 𝑛 p d n | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 6

同样地，定义互异 𝑘 k 部分拆数 𝑝 𝑑(𝑛,𝑘)p d(n,k)，表示最大拆出 𝑘 k 个部分的互异分拆，是这个方程的解数：

𝑛=𝑟 1+𝑟 2+…+𝑟 𝑘 𝑟 1>𝑟 2>…>𝑟 𝑘≥1 n=r 1+r 2+…+r k r 1>r 2>…>r k≥1

完全同上，也是这个方程的解数：

𝑛−𝑘=𝑦 1+𝑦 2+…+𝑦 𝑘 𝑦 1>𝑦 2>…>𝑦 𝑘≥0 n−k=y 1+y 2+…+y k y 1>y 2>…>y k≥0

这里与上面不同的是，由于互异，新方程中至多只有一个部分为零．有不变的结论：恰有 𝑗 j 个部分非 0 0，则恰有 𝑝 𝑑(𝑛 −𝑘,𝑗)p d(n−k,j) 个解，这里 𝑗 j 只取 𝑘 k 或 𝑘 −1 k−1．因此直接得到递推：

𝑝 𝑑(𝑛,𝑘)=𝑝 𝑑(𝑛−𝑘,𝑘−1)+𝑝 𝑑(𝑛−𝑘,𝑘)p d(n,k)=p d(n−k,k−1)+p d(n−k,k)

同样像组合数一样列出表格，每个格里的数，等于该格前一列上数，所在列数个格子中的数，加上该格向上方数，所在列数个格子中的数．

k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
--- | --- | --- | --- | --- | --- | --- | --- | --- | ---
𝑝 𝑑(0,𝑘)p d(0,k) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
𝑝 𝑑(1,𝑘)p d(1,k) | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0
𝑝 𝑑(2,𝑘)p d(2,k) | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0
𝑝 𝑑(3,𝑘)p d(3,k) | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0
𝑝 𝑑(4,𝑘)p d(4,k) | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0
𝑝 𝑑(5,𝑘)p d(5,k) | 0 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0
𝑝 𝑑(6,𝑘)p d(6,k) | 0 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0
𝑝 𝑑(7,𝑘)p d(7,k) | 0 | 1 | 3 | 1 | 0 | 0 | 0 | 0 | 0
𝑝 𝑑(8,𝑘)p d(8,k) | 0 | 1 | 3 | 2 | 0 | 0 | 0 | 0 | 0

### 例题

计算互异分拆数

计算互异分拆数 𝑝 𝑑 𝑛 p d n．多组输入，其中 𝑛 n 上界为 5 0 0 0 0 50000，对 1 0 0 0 0 0 7 1000007 取模．

观察表格与递推式，按列更新对于存储更有利．代码中将后一位缩减了空间，仅保留相邻两项．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    #include <cstdio>
    #include <cstring>

    int pd[50005][2]; /*将自然数n分拆为k个部分的互异方法数*/

    int main() {
      int n;
      while (~scanf("%d", &n)) {
        memset(pd, 0, sizeof(pd));
        pd[0][0] = 1;
        int ans = 0;
        int j;
        for (j = 1; j < 350; ++j) {
          int i;
          for (i = 0; i < 350; ++i) {
            pd[i][j & 1] = 0; /*pd[i][j]只与pd[][j]和pd[][j-1]有关*/
          }
          for (i = 0; i <= n; ++i) {
            if (i - j >= 0) /*pd[i-j][j]所有部分大于1*/
            {
              pd[i][j & 1] = (pd[i - j][j & 1] + pd[i - j][(j - 1) & 1]) %
                             1000007; /*pd[i-j][j-1]至少有一个部分为1．*/
            }
          }
          ans = (ans + pd[n][j & 1]) % 1000007;
        }
        printf("%d\n", ans);
      }
    }

### 奇分拆数

奇分拆数：𝑝 𝑜 𝑛 p o n．自然数 𝑛 n 的各部分都是奇数的分拆方法数．（Odd）

有一个显然的等式：

∞∏𝑖=1(1+𝑥 𝑖)=∏∞𝑖=1(1−𝑥 2 𝑖)∏∞𝑖=1(1−𝑥 𝑖)=∞∏𝑖=1 1 1−𝑥 2 𝑖−1∏i=1∞(1+x i)=∏i=1∞(1−x 2 i)∏i=1∞(1−x i)=∏i=1∞1 1−x 2 i−1

最左边是互异分拆数的生成函数，最右边是奇分拆数的生成函数．两者对应系数相同，因此，奇分拆数和互异分拆数相同：

𝑝 𝑜 𝑛=𝑝 𝑑 𝑛 p o n=p d n

但显然 𝑘 k 部奇分拆数和互异 𝑘 k 部分拆数不是一个概念，这里就不列出了．

再引入两个概念：

互异偶分拆数：𝑝 𝑑 𝑒 𝑛 p d e n．自然数 𝑛 n 的部分数为偶数的互异分拆方法数．（Even）

互异奇分拆数：𝑝 𝑑 𝑜 𝑛 p d o n．自然数 𝑛 n 的部分数为奇数的互异分拆方法数．（Odd）

因此有：

𝑝 𝑑 𝑛=𝑝 𝑑 𝑒 𝑛+𝑝 𝑑 𝑜 𝑛 p d n=p d e n+p d o n

同样也有相应的 𝑘 k 部概念．由于过于复杂，不再列出．

## 五边形数定理

单独观察分拆数的生成函数的分母部分：

∞∏𝑖=1(1−𝑥 𝑖)∏i=1∞(1−x i)

将这部分展开，可以想到互异分拆，与互异分拆拆出的部分数奇偶性有关．

具体地，互异偶部分拆在展开式中被正向计数，互异奇部分拆在展开式中被负向计数．因此展开式中各项系数为两方法数之差．即：

∞∑𝑖=0(𝑝 𝑑 𝑒 𝑛−𝑝 𝑑 𝑜 𝑛)𝑥 𝑛=∞∏𝑖=1(1−𝑥 𝑖)∑i=0∞(p d e n−p d o n)x n=∏i=1∞(1−x i)

接下来说明，多数情况下，上述两方法数相等，在展开式中系数为 0 0；仅在少数位置，两方法数相差 1 1 或 −1−1．

这里可以借助构造对应的办法．

画出每个互异分拆的 Ferrers 图．最后一行称为这个图的底，底上点的个数记为 𝑏 b（Bottom）；连接最上面一行的最后一个点与图中某点的最长 4 5 45 度角线段，称为这个图的坡，坡上点的个数记为 𝑠 s（Slide）．

要想在互异偶部分拆与互异奇部分拆之间构造对应，就要定义变换，在保证互异条件不变的前提下，使得行数改变 1 1：

变换 A：当 𝑏 b 小于等于 𝑠 s 的时候，就将底移到右边，成为一个新坡．

变换 B：当 𝑏 b 大于 𝑠 s 的时候，就将坡移到下边，成为一个新底．

这两个变换对于大多数 𝑛 n 的任意互异分拆，恰有一个变换可以进行，就在互异偶部分拆与互异奇部分拆之间构造了一个一一对应．已经构造了一一对应的两部分分拆个数相等，因此这时展开式中第 𝑛 n 项系数为 0 0．

但是对于某些 𝑛 n，其存在恰一个互异分拆无法进行上述变换．

- 情况一：𝑏 =𝑠 b=s 且底与坡有一个公共点时，变换 A 不能进行．此时

𝑛=𝑠+(𝑠+1)+…+(𝑠+𝑠−1)=𝑠(3 𝑠−1)2 n=s+(s+1)+…+(s+s−1)=s(3 s−1)2

展开式的第 𝑛 n 项与分拆部分数的奇偶性有关，为 ( −1)𝑠 𝑥 𝑛(−1)s x n．

- 情况二：𝑏 =𝑠 +1 b=s+1 且底与坡有一个公共点时，变换 B 不能进行．此时

𝑛=(𝑠+1)+(𝑠+2)+…+(𝑠+𝑠)=𝑠(3 𝑠+1)2 n=(s+1)+(s+2)+…+(s+s)=s(3 s+1)2

展开式的第 𝑛 n 项为 ( −1)𝑠 𝑥 𝑛(−1)s x n．

用 −𝑠−s 替换上式的 𝑠 s，得到 𝑛 =𝑠(3 𝑠−1)2 n=s(3 s−1)2，其中 𝑠 s 为负整数，展开式的第 𝑛 n 项仍为 ( −1)𝑠 𝑥 𝑛(−1)s x n．．

由于两种情况不会在同一个 𝑛 n 同时出现，我们可以把两个条件合起来，得到 𝑛 n 需要满足的条件是

∃𝑘∈ℤ,𝑛=𝑘(3 𝑘−1)2∃k∈Z,n=k(3 k−1)2

至此，我们就证明了：

(1−𝑥)(1−𝑥 2)(1−𝑥 3)…=+∞∑𝑘=−∞(−1)𝑘 𝑥 𝑘(3 𝑘−1)2=…+𝑥 2 6−𝑥 1 5+𝑥 7−𝑥 2+1−𝑥+𝑥 5−𝑥 1 2+𝑥 2 2−…(1−x)(1−x 2)(1−x 3)…=∑k=−∞+∞(−1)k x k(3 k−1)2=…+x 26−x 15+x 7−x 2+1−x+x 5−x 12+x 22−…

回忆一下：这个式子是分拆数的生成函数的倒数，因此其与分拆数的生成函数相乘的结果是 1 1．整理并对比两边各项系数，就得到分拆数数列的递推式．

(1+𝑝 1 𝑥+𝑝 2 𝑥 2+𝑝 3 𝑥 3+…)(1−𝑥−𝑥 2+𝑥 5+𝑥 7−𝑥 1 2−𝑥 1 5+𝑥 2 2+𝑥 2 6−…)=1(1+p 1 x+p 2 x 2+p 3 x 3+…)(1−x−x 2+x 5+x 7−x 12−x 15+x 22+x 26−…)=1 𝑝 𝑛=𝑝 𝑛−1+𝑝 𝑛−2−𝑝 𝑛−5−𝑝 𝑛−7+…p n=p n−1+p n−2−p n−5−p n−7+…

这个递推式有无限项，但是如果规定负数的分拆数是 0 0（0 0 的分拆数已经定义为 1 1），那么就简化为了有限项．

### 例题

计算分拆数

计算分拆数 𝑝 𝑛 p n．多组输入，其中 𝑛 n 上界为 5 0 0 0 0 50000，对 1 0 0 0 0 0 7 1000007 取模．

采用五边形数定理的方法．有代码：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    #include <cstdio>

    long long a[100010];
    long long p[50005];

    int main() {
      p[0] = 1;
      p[1] = 1;
      p[2] = 2;
      int i;
      for (i = 1; i < 50005;
           i++) /*递推式系数1,2,5,7,12,15,22,26...i*(3*i-1)/2,i*(3*i+1)/2*/
      {
        a[2 * i] = i * (i * 3 - 1) / 2; /*五边形数为1,5,12,22...i*(3*i-1)/2*/
        a[2 * i + 1] = i * (i * 3 + 1) / 2;
      }
      for (
          i = 3; i < 50005;
          i++) /*p[n]=p[n-1]+p[n-2]-p[n-5]-p[n-7]+p[12]+p[15]-...+p[n-i*[3i-1]/2]+p[n-i*[3i+1]/2]*/
      {
        p[i] = 0;
        int j;
        for (j = 2; a[j] <= i; j++) /*有可能为负数,式中加1000007*/
        {
          if (j & 2) {
            p[i] = (p[i] + p[i - a[j]] + 1000007) % 1000007;
          } else {
            p[i] = (p[i] - p[i - a[j]] + 1000007) % 1000007;
          }
        }
      }
      int n;
      while (~scanf("%d", &n)) {
        printf("%lld\n", p[n]);
      }
    }

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Tiphereth-A, Ir1d, 2008verser, Early0v0, Enter-tainer, Great-designer, ksyx, myeeye, Xeonacid, YOYO-UIAT
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用