AIOJ

Partitions: a representation of a natural number $n$ as a sum of positive integers in non-increasing order.

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 numbers: $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

Partitions into k Parts

A partition of $n$ into exactly $k$ parts is called a partition into $k$ parts, denoted by $p(n,k)$ .

Clearly, the number of partitions into $k$ parts, $p(n,k)$ , is also the number of solutions of 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 nonzero, then there are exactly $p(n-k,j)$ solutions. Therefore,

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

Subtracting two adjacent sums gives

p(n,k)=p(n-1,k-1)+p(n-k,k)

If we lay out a table, the number in each cell equals the number in the upper-left cell plus the numbers in the column-number-many cells above that cell.

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

Computing the Number of Partitions into k Parts

Compute the number of partitions into $k$ parts, $p(n,k)$ . There are multiple test cases; $n$ is at most $10000$ , $k$ is at most $1000$ , and all answers are taken modulo $1000007$ .

Looking at the table and recurrence, updating by column is more favorable for storage. The program is straightforward:

#include <cstdio>
#include <cstring>

int p[10005][1005]; /*Number of ways to partition the 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) /*All parts of p[i-j][j] are greater than 1*/
        {
          p[i][j] = (p[i - j][j] + p[i - 1][j - 1]) %
                    1000007; /*p[i-1][j-1] has at least one part equal to 1.*/
        }
      }
    }
    printf("%d\n", p[n][k]);
  }
}

Generating Function

By the formula for the sum of a geometric progression,

\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 partitions into $k$ parts, the generating function is slightly more complicated. Explicitly,

\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

A Ferrers diagram represents each part of a partition as a row of dots. The number of dots in each row is the size of that part.

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

For example, the Ferrers diagram of the partition $12=5+4+2+1$ is as follows.

$Figure: ferrers$

Flipping a Ferrers diagram along its diagonal produces a new Ferrers diagram called the conjugate of the original diagram, 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$ above is the partition $12=4+3+2+2+1$ .

The number of partitions with largest part $k$ is the number of partitions of the natural number $n$ whose largest part is $k$ .

By the definition of conjugation, we immediately obtain:

The number of partitions with largest part $k$ is equal to the number of partitions into $k$ parts; both are $p(n,k)$ .

Partitions into Distinct Parts

The number of partitions into distinct parts: $pd_n$ , the number of ways to partition the natural number $n$ so that all parts are distinct. (Different)

n	0	1	2	3	4	5	6	7	8
$pd_n$	1	1	1	2	2	3	4	5	6

Similarly, define the number of partitions into $k$ distinct parts, $pd(n,k)$ , as the number of distinct partitions into exactly $k$ parts; it is the number of solutions of

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

Equivalently, it is the number of solutions of

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

The difference from the discussion above is that, because the parts are distinct, the new equation has at most one zero part. The same invariant conclusion holds: if exactly $j$ parts are not $0$ , then there are exactly $pd(n-k,j)$ solutions, where $j$ can only be $k$ or $k-1$ . Thus we directly obtain the recurrence

pd(n,k)=pd(n-k,k-1)+pd(n-k,k)

As with binomial coefficients, we can lay out a table. The number in each cell equals the numbers in the column-number-many cells above the cell in the preceding column, plus the numbers in the column-number-many cells above the cell.

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

Computing the Number of Partitions into Distinct Parts

Compute the number of partitions into distinct parts, $pd_n$ . There are multiple test cases; $n$ is at most $50000$ , and all answers are taken modulo $1000007$ .

Looking at the table and recurrence, updating by column is more favorable for storage. The code saves space by reducing the latter dimension to two, retaining only adjacent terms.

#include <cstdio>
#include <cstring>

int pd[50005][2]; /*Number of distinct ways to partition the natural number n into k 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] depends only on pd[][j] and pd[][j-1]*/
      }
      for (i = 0; i <= n; ++i) {
        if (i - j >= 0) /*All parts of pd[i-j][j] are greater than 1*/
        {
          pd[i][j & 1] = (pd[i - j][j & 1] + pd[i - j][(j - 1) & 1]) %
                         1000007; /*pd[i-j][j-1] has at least one part equal to 1.*/
        }
      }
      ans = (ans + pd[n][j & 1]) % 1000007;
    }
    printf("%d\n", ans);
  }
}

Partitions into Odd Parts

The number of partitions into odd parts: $po_n$ , the number of ways to partition the natural number $n$ so that every part is odd. (Odd)

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 expression is the generating function for partitions into distinct parts, and the rightmost expression is the generating function for partitions into odd parts. Their corresponding coefficients are equal, so the numbers of partitions into odd parts and into distinct parts are equal:

po_n=pd_n

However, the number of partitions into $k$ odd parts and the number of partitions into $k$ distinct parts are clearly different concepts, so we omit the former here.

We introduce two more concepts:

The number of partitions into distinct even parts: $pde_n$ , the number of distinct partitions of the natural number $n$ with an even number of parts. (Even)

The number of partitions into distinct odd parts: $pdo_n$ , the number of distinct partitions of the natural number $n$ with an odd number of parts. (Odd)

Therefore,

pd_n=pde_n+pdo_n

There are corresponding notions for partitions into $k$ parts as well. They are too complicated to list here.

The Pentagonal Number Theorem

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

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

Expanding this expression brings to mind partitions into distinct parts and the parity of their number of parts.

Specifically, partitions into a distinct even number of parts are counted positively in the expansion, while partitions into a distinct odd number of parts are counted negatively. Therefore, each coefficient in the expansion is the difference between the two counts. That is,

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

We next show that in most cases the two counts above are equal, so the coefficient in the expansion is $0$ ; only at a few positions do the two counts differ by $1$ or $-1$ .

Here we can construct a correspondence.

Draw the Ferrers diagram of each distinct partition. The last row is called the base of the diagram, and let $b$ (Bottom) be the number of dots on the base. The longest $45$ -degree line segment connecting the last dot of the top row to a dot in the diagram is called the slide of the diagram, and let $s$ (Slide) be the number of dots on the slide.

$Figure: bottom slide$

To construct a correspondence between partitions into a distinct even number of parts and partitions into a distinct odd number of parts, define transformations that change the number of rows by $1$ while preserving distinctness:

Transformation A: when $b$ is less than or equal to $s$ , move the base to the right, making it a new slide.

Transformation B: when $b$ is greater than $s$ , move the slide to the bottom, making it a new base.

For any distinct partition of most $n$ , exactly one of these two transformations can be performed, thereby constructing a bijection between partitions into a distinct even number of parts and partitions into a distinct odd number of parts. Since a bijection has been constructed, the numbers of the two types of partitions are equal, and the coefficient of the $n$ -th term in the expansion is $0$ .

However, for some $n$ , there is exactly one distinct partition for which neither of the transformations above can be performed.

Case 1: when $b=s$ and the base and slide have one common point, Transformation A cannot be performed. In this case,

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

The $n$ -th term of the expansion depends on the parity of the number of parts in the partition and is $(-1)^s x^n$ .

Case 2: when $b=s+1$ and the base and slide have one common point, Transformation B cannot be performed. In this case,

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

The $n$ -th term of the expansion is $(-1)^s x^n$ .

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

Since the two cases cannot occur for the same $n$ , we can combine the two conditions. The condition on $n$ is

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

We have therefore 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 that this expression is the reciprocal of the generating function for partition numbers, so multiplying it by the generating function for partition numbers gives $1$ . Rearranging and comparing the coefficients on both sides gives the recurrence for the sequence of partition numbers.

(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 number of partitions of a negative number to be $0$ (the number of partitions of $0$ has already been defined as $1$ ), it simplifies to finitely many terms.

Example

Computing Partition Numbers

Compute the partition number $p_n$ . There are multiple test cases; $n$ is at most $50000$ , and all answers are taken modulo $1000007$ .

Use the pentagonal number theorem. The code is as follows:

#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 are 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++) /*The result may be negative; add 1000007 in the formula*/
    {
      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]);
  }
}