A partition of an integer is a way of writing it as a sum of positive integers. For example, partitions of 5 are:
5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
The order of numbers in a partition doesn’t matter. The number of partitions of a number \(n\) is given by the partition function \(p(n)\).
The first few values of \(p(n)\) are 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, … (A000041).
The partition function can be computed using a dynamic programming table-filling algorithm. Here it is in C:
#include <stdlib.h> unsigned int partition(unsigned int n) { unsigned int i, j; unsigned int result; unsigned int **table; if (n == 0) { return 1; } table = malloc((n + 1) * sizeof(unsigned int *)); for (i = 0; i <= n; i++) { table[i] = malloc((n + 1) * sizeof(unsigned int)); } for (i = 0;i <= n; i++) { table[i][0]=0; } for (i = 1; i <= n; i++) { table[0][i] = 1; } for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (j > i) { table[i][j] = table[i][j - 1]; } else { table[i][j] = table[i][j - 1] + table[i - j][j]; } } } result = table[n][n]; for (i = 0; i <= n; i++) { free(table[i]); } free(table); return result; }
Example program:
#include <stdio.h> int main(void) { unsigned int i; for (i = 0; i < 31; i++) { printf("%d\n",partition(i)); } return 0; }
Output:
1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958 2436 3010 3718 4565 5604