Partition Numbers

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

Each positive integer in the sum is called a part.

Partition number: \(p_n\). The number of ways to partition the natural number \(n\).

Partition numbers starting from \(0\):

n	0	1	2	3	4	5	6	7	8
\(p_n\)	1	1	2	3	5	7	11	15	22

k-partition number

A partition of \(n\) into exactly \(k\) parts is called a k-partition, and its count is denoted as \(p(n,k)\).

Clearly, the k-partition number \(p(n,k)\) is also the number of solutions to the following equation:

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

If exactly \(j\) parts in this equation are non-zero, then there are exactly \(p(n-k,j)\) solutions. Therefore, we have the summation:

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

Taking the difference between two adjacent summations yields:

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

If we list the table, the number in each cell equals the number in the cell to its upper-left, plus the number in the cell located \(k\) rows above it in the same column.

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

Example

Compute k-partition number

Compute the k-partition number \(p(n,k)\). Multiple inputs, where the upper bound for \(n\) is \(10000\), the upper bound for \(k\) is \(1000\), modulo \(1000007\).

Observing the table and the recurrence relation, updating by column is more advantageous for storage. It's straightforward to write the program:

#include <cstdio>
#include <cstring>

int p[10005][1005]; /*Number of ways to partition natural number n into k parts*/

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] all parts > 1*/
        {
          p[i][j] = (p[i - j][j] + p[i - 1][j - 1]) %
                    1000007; /*p[i-1][j-1] at least one part is 1.*/
        }
      }
    }
    printf("%d\n", p[n][k]);
  }
}

Generating Function

From the geometric series summation formula, we have:

\[ \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}\ldots \]

For the k-partition number, the generating function is slightly more complex. Specifically:

\[ \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}\ldots \]

Ferrers Diagram

Ferrers Diagram: Represent each part of a partition by a row of dots. The number of dots in each row equals the size of that part.

According to the definition of a partition, different rows in a Ferrers diagram are arranged in decreasing order. The longest row is at the top.

For example: Ferrers diagram for the partition \(12=5+4+2+1\).

Reflecting a Ferrers diagram along its diagonal yields a new Ferrers diagram called the conjugate of the original, and the new partition is called the conjugate of the original partition. Clearly, conjugation is a symmetric relation.

For example, the conjugate of the partition \(12=5+4+2+1\) is \(12=4+3+2+2+1\).

Maximum k-partition number: The number of partitions of a natural number \(n\) with largest part equal to \(k\).

From the definition of conjugation, an obvious conclusion follows:

The maximum k-partition number is the same as the k-partition number, both are \(p(n,k)\).

Distinct Partition Number

Distinct partition number: \(pd_n\). The number of ways to partition the natural number \(n\) into distinct parts.

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

Similarly, define the distinct k-partition number \(pd(n,k)\), representing the number of distinct partitions with exactly \(k\) parts, which is the number of solutions to this equation:

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

Exactly as before, it is also the number of solutions to this equation:

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

The difference here, due to distinctness, is that at most one part in the new equation can be zero. An unchanged conclusion: if exactly \(j\) parts are non-zero, then there are exactly \(pd(n-k,j)\) solutions, where \(j\) is either \(k\) or \(k-1\). Therefore, we directly obtain the recurrence:

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

Similarly, list a table like the binomial coefficients. The number in each cell equals the number in the cell one column to the left, \(k\) cells above it, plus the number in the cell \(k\) cells above it in the same column.

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

Example

Compute Distinct Partition Number

Compute the distinct partition number \(pd_n\). Multiple inputs, where the upper bound for \(n\) is \(50000\), modulo \(1000007\).

Observing the table and the recurrence relation, updating by column is more advantageous for storage. In the code, space is reduced by keeping only two adjacent columns.

#include <cstdio>
#include <cstring>

int pd[50005][2]; /*Number of ways to partition natural number n into k distinct parts*/

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] only depends on pd[][j] and pd[][j-1]*/
      }
      for (i = 0; i <= n; ++i) {
        if (i - j >= 0) /*pd[i-j][j] all parts > 1*/
        {
          pd[i][j & 1] = (pd[i - j][j & 1] + pd[i - j][(j - 1) & 1]) %
                         1000007; /*pd[i-j][j-1] at least one part is 1.*/
        }
      }
      ans = (ans + pd[n][j & 1]) % 1000007;
    }
    printf("%d\n", ans);
  }
}

Odd Partition Number

Odd partition number: \(po_n\). The number of ways to partition the natural number \(n\) into odd parts.

There is an obvious identity:

\[ \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} } \]

The leftmost side is the generating function for distinct partitions, the rightmost side is the generating function for odd partitions. Their corresponding coefficients are the same, therefore, the odd partition number equals the distinct partition number:

\[ po_n=pd_n \]

But clearly, the k-part odd partition number and the distinct k-part partition number are different concepts, and are not listed here.

Introduce two more concepts:

Even distinct partition number: \(pde_n\). The number of distinct partitions of natural number \(n\) with an even number of parts.

Odd distinct partition number: \(pdo_n\). The number of distinct partitions of natural number \(n\) with an odd number of parts.

Therefore:

\[ pd_n=pde_n+pdo_n \]

There are also corresponding k-part concepts. They are too complex and are not listed.

Pentagonal Number Theorem

Consider the denominator part of the generating function for partition numbers separately:

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

Expanding this part, one can think of distinct partitions and the parity of the number of parts in a distinct partition.

Specifically, even distinct partitions are counted positively in the expansion, while odd distinct partitions are counted negatively. Therefore, the coefficients in the expansion are the difference between these two counts. That is:

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

Next, we explain that in most cases, these two counts are equal, resulting in a coefficient of \(0\) in the expansion; only in a few positions do the counts differ by \(1\) or \(-1\).

We can use a constructive correspondence here.

Draw the Ferrers diagram for each distinct partition. The last row is called the bottom of the diagram, and the number of dots in the bottom is denoted by \(b\) (Bottom); the longest 45-degree line segment connecting the last dot of the top row to some dot in the diagram is called the slide of the diagram, and the number of dots on the slide is denoted by \(s\) (Slide).

To construct a correspondence between even distinct partitions and odd distinct partitions, we need to define transformations that change the number of rows by \(1\) while preserving the distinctness condition:

Transformation A: When \(b\) is less than or equal to \(s\), move the bottom to the right to become a new slide.

Transformation B: When \(b\) is greater than \(s\), move the slide down to become a new bottom.

For most distinct partitions of most \(n\), exactly one of these transformations can be applied, establishing a one-to-one correspondence between even distinct partitions and odd distinct partitions. Since the two parts in correspondence have equal counts, the coefficient of the \(n\)-th term in the expansion is \(0\).

However, for certain \(n\), there exists exactly one distinct partition for which neither transformation can be applied.

Case 1: When \(b=s\) and the bottom and slide share a common point, Transformation A cannot be applied. Then

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

The \(n\)-th term in the expansion relates to the parity of the number of parts, and is \((-1)^s x^n\).

Case 2: When \(b=s+1\) and the bottom and slide share a common point, Transformation B cannot be applied. Then

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

The \(n\)-th term in the expansion is \((-1)^s x^n\).

Replacing \(s\) with \(-s\) in the above formula gives \(n=\frac{s(3s-1)}{2}\), where \(s\) is a negative integer, and the \(n\)-th term in the expansion is still \((-1)^s x^n\).

Since the two cases cannot occur for the same \(n\) simultaneously, we can combine the conditions to get the condition that \(n\) must satisfy:

\[ \exists k\in\mathbb{Z},n=\frac{k(3k-1)}{2} \]

Thus, we have proved:

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

Recall: This expression is the reciprocal of the generating function for partition numbers, so multiplying it with the generating function for partition numbers yields \(1\). Comparing coefficients on both sides after rearrangement gives the recurrence relation for the partition number sequence.

\[ (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}-\ldots)=1 \]

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

This recurrence has infinitely many terms, but if we define the partition number for negative numbers as \(0\) (the partition number for \(0\) is already defined as \(1\)), it simplifies to a finite recurrence.

Example

Compute Partition Number

Compute the partition number \(p_n\). Multiple inputs, where the upper bound for \(n\) is \(50000\), modulo \(1000007\).

Use the Pentagonal Number Theorem method. Code:

#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++) /*Recurrence coefficients: 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; /*Pentagonal numbers: 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++) /*Could be negative, add 1000007 in the expression*/
    {
      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 协议之条款下提供，附加条款亦可能应用