分拆數

分拆：將自然數 \(n\) 寫成遞降正整數和的表示。

\[ n=r_1+r_2+\ldots+r_k \quad r_1 \ge r_2 \ge \ldots \ge r_k \ge 1 \]

和式中每個正整數稱為一個部分。

分拆數：\(p_n\)。自然數 \(n\) 的分拆方法數。

自 \(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)\) 同時也是下面方程的解數：

\[ n-k=y_1+y_2+\ldots+y_k\quad y_1\ge y_2\ge\ldots\ge y_k\ge 0 \]

如果這個方程裏面恰有 \(j\) 個部分非 0，則恰有 \(p(n-k,j)\) 個解。因此有和式：

\[ p(n,k)=\sum_{j=0}^k p(n-k,j) \]

相鄰兩個和式作差，得：

\[ p(n,k)=p(n-1,k-1)+p(n-k,k) \]

如果列出表格，每個格里的數，等於左上方的數，加上該格向上方數，所在列數個格子中的數。

k	0	1	2	3	4	5	6	7	8
\(p(0,k)\)	1	0	0	0	0	0	0	0	0
\(p(1,k)\)	0	1	0	0	0	0	0	0	0
\(p(2,k)\)	0	1	1	0	0	0	0	0	0
\(p(3,k)\)	0	1	1	1	0	0	0	0	0
\(p(4,k)\)	0	1	2	1	1	0	0	0	0
\(p(5,k)\)	0	1	2	2	1	1	0	0	0
\(p(6,k)\)	0	1	3	3	2	1	1	0	0
\(p(7,k)\)	0	1	3	4	3	2	1	1	0
\(p(8,k)\)	0	1	4	5	5	3	2	1	1

例題

計算 k 部分拆數

計算 \(k\) 部分拆數 \(p(n,k)\)。多組輸入，其中 \(n\) 上界為 \(10000\)，\(k\) 上界為 \(1000\)，對 \(1000007\) 取模。

觀察表格與遞推式，按列更新對於存儲更有利。不難寫出程序：

#include <stdio.h>
#include <string.h>

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]);
  }
}

生成函數

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

\[ \frac{1}{1-x^k}=1+x^k+x^{2k}+x^{3k}+\ldots \]

\[ 1+p_1 x+p_2 x^2+p_3 x^3+\ldots=\frac{1}{1-x} \frac{1}{1-x^2} \frac{1}{1-x^3}… \]

對於 \(k\) 部分拆數，生成函數稍微複雜。具體寫出如下：

\[ \sum_{n,k=0}^\infty {p(n,k) x^n y^k }=\frac{1}{1-xy} \frac{1}{1-x^2 y} \frac{1}{1-x^3 y}… \]

Ferrers 圖

Ferrers 圖：將分拆的每個部分用點組成的行表示。每行點的個數為這個部分的大小。

根據分拆的定義，Ferrers 圖中不同的行按照遞減的次序排放。最長行在最上面。

例如：分拆 \(12=5+4+2+1\) 的 Ferrers 圖。

將一個 Ferrers 圖沿着對角線翻轉，得到的新 Ferrers 圖稱為原圖的共軛，新分拆稱為原分拆的共軛。顯然，共軛是對稱的關係。

例如上述分拆 \(12=5+4+2+1\) 的共軛是分拆 \(12=4+3+2+2+1\)。

最大 \(k\) 分拆數：自然數 \(n\) 的最大部分為 \(k\) 的分拆個數。

根據共軛的定義，有顯然結論：

最大 \(k\) 分拆數與 \(k\) 部分拆數相同，均為 \(p(n,k)\)。

互異分拆數

互異分拆數：\(pd_n\)。自然數 \(n\) 的各部分互不相同的分拆方法數。（Different）

n	0	1	2	3	4	5	6	7	8
\(pd_n\)	1	1	1	2	2	3	4	5	6

同樣地，定義互異 \(k\) 部分拆數 \(pd(n,k)\)，表示最大拆出 \(k\) 個部分的互異分拆，是這個方程的解數：

\[ n=r_1+r_2+\ldots+r_k\quad r_1>r_2>\ldots>r_k\ge 1 \]

完全同上，也是這個方程的解數：

\[ n-k=y_1+y_2+\ldots+y_k\quad y_1>y_2>\ldots>y_k\ge 0 \]

這裏與上面不同的是，由於互異，新方程中至多隻有一個部分為零。有不變的結論：恰有 \(j\) 個部分非 \(0\)，則恰有 \(pd(n-k,j)\) 個解，這裏 \(j\) 只取 \(k\) 或 \(k-1\)。因此直接得到遞推：

\[ pd(n,k)=pd(n-k,k-1)+pd(n-k,k) \]

同樣像組合數一樣列出表格，每個格里的數，等於該格前一列上數，所在列數個格子中的數，加上該格向上方數，所在列數個格子中的數。

k	0	1	2	3
\(pd(0,k)\)	1	0	0	0
\(pd(1,k)\)	0	1	0	0
\(pd(2,k)\)	0	1	0	0
\(pd(3,k)\)	0	1	1	0
\(pd(4,k)\)	0	1	1	0
\(pd(5,k)\)	0	1	2	0
\(pd(6,k)\)	0	1	2	1
\(pd(7,k)\)	0	1	3	1
\(pd(8,k)\)	0	1	3	2

例題

計算互異分拆數

計算互異分拆數 \(pd_n\)。多組輸入，其中 \(n\) 上界為 \(50000\)，對 \(1000007\) 取模。

觀察表格與遞推式，按列更新對於存儲更有利。代碼中將後一位縮減了空間，僅保留相鄰兩項。

#include <stdio.h>
#include <string.h>

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);
  }
}

奇分拆數

奇分拆數：\(po_n\)。自然數 \(n\) 的各部分都是奇數的分拆方法數。（Odd）

有一個顯然的等式：

\[ \prod_{i=1}^\infty (1+x^i ) =\frac{\prod_{i=1}^\infty (1-x^{2i} ) }{\prod_{i=1}^\infty (1-x^i ) }=\prod_{i=1}^\infty \frac{1}{1-x^{2i-1} } \]

最左邊是互異分拆數的生成函數，最右邊是奇分拆數的生成函數。兩者對應係數相同，因此，奇分拆數和互異分拆數相同：

\[ po_n=pd_n \]

但顯然 \(k\) 部奇分拆數和互異 \(k\) 部分拆數不是一個概念，這裏就不列出了。

再引入兩個概念：

互異偶分拆數：\(pde_n\)。自然數 \(n\) 的部分數為偶數的互異分拆方法數。（Even）

互異奇分拆數：\(pdo_n\)。自然數 \(n\) 的部分數為奇數的互異分拆方法數。（Odd）

因此有：

\[ pd_n=pde_n+pdo_n \]

同樣也有相應的 \(k\) 部概念。由於過於複雜，不再列出。

五邊形數定理

單獨觀察分拆數的生成函數的分母部分：

\[ \prod_{i=1}^\infty (1-x^i ) \]

將這部分展開，可以想到互異分拆，與互異分拆拆出的部分數奇偶性有關。

具體地，互異偶部分拆在展開式中被正向計數，互異奇部分拆在展開式中被負向計數。因此展開式中各項係數為兩方法數之差。即：

\[ \sum_{i=0}^\infty ({pde}_n-{pdo}_n ) x^n =\prod_{i=1}^\infty (1-x^i ) \]

接下來説明，多數情況下，上述兩方法數相等，在展開式中係數為 \(0\)；僅在少數位置，兩方法數相差 \(1\) 或 \(-1\)。

這裏可以藉助構造對應的辦法。

畫出每個互異分拆的 Ferrers 圖。最後一行稱為這個圖的底，底上點的個數記為 \(b\)（Bottom）；連接最上面一行的最後一個點與圖中某點的最長 \(45\) 度角線段，稱為這個圖的坡，坡上點的個數記為 \(s\)（Slide）。

要想在互異偶部分拆與互異奇部分拆之間構造對應，就要定義變換，在保證互異條件不變的前提下，使得行數改變 \(1\)：

變換 A：當 \(b\) 小於等於 \(s\) 的時候，就將底移到右邊，成為一個新坡。

變換 B：當 \(b\) 大於 \(s\) 的時候，就將坡移到下邊，成為一個新底。

這兩個變換，對於多數時候的 \(n\)，恰有一個變換可以進行，就在互異偶部分拆與互異奇部分拆之間構造了一個一一對應。已經構造了一一對應的兩部分分拆個數相等，因此這時展開式中第 \(n\) 項係數為 \(0\)。

變換 A 不能進行的條件：底與坡有一個公共點，且 \(b=s\)。這種情形只發生於：

\[ n=b+(b+1)+\ldots+(b+b-1)=\frac{b(3b-1)}{2} \]

這時，展開式中第 \(n\) 項為：

\[ \prod_{i=0}^{b-1} (-x)^{b+i} =(-1)^b \prod_{i=0}^{b-1} x^{b+i} =(-1)^b x^n \]

變換 B 不能進行的條件：底與坡有一個公共點，且 \(b=s+1\)。這種情形只發生於：

\[ n=(s+1)+(s+2)+\ldots+(s+s)=\frac{s(3s-1)}{2} \]

這時，展開式中第 \(n\) 項為：

\[ \prod_{i=1}^s (-x)^{s+i} =(-1)^s \prod_{i=1}^s x^{s+i} =(-1)^s x^n \]

至此，我們就證明了：

\[ (1-x)(1-x^2 )(1-x^3 )…=\ldots+x^{26}-x^{15}+x^7-x^2+1-x+x^5-x^{12}+x^{22}-…=\sum_{k=-\infty}^{+\infty} (-1)^k x^{\frac{k(3k-1)}{2}} \]

將這個式子整理，對比兩邊各項係數，就得到遞推式。

\[ (1+p_1 x+p_2 x^2+p_3 x^3+\ldots)(1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}-…)=1 \]

\[ p_n=p_{n-1}+p_{n-2}-p_{n-5}-p_{n-7}+\ldots \]

這個遞推式有無限項，但是如果規定負數的分拆數是 \(0\)（\(0\) 的分拆數已經定義為 \(1\)），那麼就簡化為了有限項。

例題

計算分拆數

計算分拆數 \(p_n\)。多組輸入，其中 \(n\) 上界為 \(50000\)，對 \(1000007\) 取模。

採用五邊形數定理的方法。有代碼：

#include <stdio.h>

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]);
  }
}

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用