Partitions With No Ones

Each partition of $n$ can be uniquely written as $k + (\text{partition of}\ n-k\ \text{with no terms greater than}\ k.)$ Define therefore $C'_{n,k} = \text{number of partitions of}\ n\ \text{without 1 and with no terms greater then}\ k.$ The trick is to generate $C'_{n,k}$ inductively; clearly, $C'_n = C'_{n,n}$ .

Some simple observations: $C'_{0,k} = 1\ \ \ C'_{1,k} = 0\ \ \text{for all}\ k\geq 1.$ $C'_{n,0} = 0.\ \ \ C'_{n,k} = C'_{n,n}\ \ \text{for all}\ k > n.$ and the most important one is the recursion formula $C'_{n,k} = C'_{n,k-1} + C'_{n-k,k}.$ (The partitions of $n$ with no terms greater than $k$ consist of the partitions of $n$ with no terms greater than $k-1$ , plus those of the form ( $k +$ a partition of $n-k$ with no terms greater than $k$ ).)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

final int mx_n = 50;
int C[][] = new int[mx_n+1][mx_n+1];

for (int i = 0; i <= mx_n; i++) { C[0][i] = 1; C[1][i] = 0; }

for (int n = 2; n <= mx_n; n++) {
    C[n][0] = 0;
    for (int i = 1; i <= n; i++) {
        C[n][i] = C[n][i-1] + C[n-i][i];
    }
    for (int i = n+1; i <= mx_n; i++)
        C[n][i] = C[n][n];
}
System.out.println(C[mx_n][mx_n]);

Output:

1

30701

For more information about the sequence, see this site .

Partitions of N without any addend of any partition being 1 is

$P(N) - P(N-1)$

$P(50) - P(49) = 30701$