Integer Partition (algorithm and recursion)

Question

Finding how many combinations of a sum number (the variable n in code). For ex.:

3 = 1+1+1 = 2+1 = 3 => ANS is 3

5 = 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1 => ANS is 7

In the following example, m is the max number and n is sum, the aim is to find how many (sum) combination does it have.

I just want to know why do p(n, m) = p(n, m - 1) + p(n - m, m) ?

The code here:

int p (int n, int m) {     if (n == m)         return 1 + p(n, m - 1);     if (m == 0 || n < 0)         return 0;     if (n == 0 || m == 1)         return 1;      return p(n, m - 1) + p(n - m, m);  } 

Appreciated!

Answer 1

Consider all ways of resulting n by adding some numbers less than or equal to m. As you said, we call this p(n,m). For example, p(7,3)=8 because there are 8 ways to make 7 out of numbers less than 3 as listed below: (For simplicity we can assume that always we add numbers in order from greatest to least)

• 3+3+1
• 3+2+2
• 3+2+1+1
• 3+1+1+1+1
• 2+2+2+1
• 2+2+1+1+1
• 2+1+1+1+1+1
• 1+1+1+1+1+1+1

Now we can split these combinations in two groups:

1. Combinations whose first element is equal to m(=3 in our example:)

   • 3+3+1
   • 3+2+2
   • 3+2+1+1
   • 3+1+1+1+1

2. Combinations whose first element is less than m:

   • 2+2+2+1
   • 2+2+1+1+1
   • 2+1+1+1+1+1
   • 1+1+1+1+1+1+1

Because every member of combinations of p(n,m) will be either in Group1 or in Group2, we can say p(n,m)=size(Group1) + size(Group2). Now if we prove that size(Group1)=p(n-m, m) and size(Group2)=p(n,m-1) by substitution we reach p(n,m)=p(n-m,m)+p(n,m-1)

Prove for size(Group1)=p(n-m, m):

By aforementioned definition p(n-m, m) is number of ways of resulting n-m by adding some numbers less than or equal to m.

• If you append m to each combination of p(n-m, m), it will result a member of Group1. so p(n-m, m) <= size(Group1)
• If you remove first m of each member of Group1, it will result a combination for p(n-m, m). so size(Group1) <= p(n-m, m)

=> size(Group1) = p(n-m, m). In our example:

Group1 <===correspondence===> p(4, 3) :

• 7=3+3+1 <===========> 3+1=4
• 7=3+2+2 <===========> 2+2=4
• 7=3+2+1+1 <=======> 2+1+1=4
• 7=3+1+1+1+1 <===> 1+1+1+1=4

So there is one to one correspondence between any member of p(n-m,m) and Group1 and their size is equal.

Prove for size(Group2)=p(n, m-1):

By definition, p(n,m-1) is the number of ways to result n by adding some numbers less than or equal to m-1 (less than m). If you re-read the definition of Group2, you will see that these two definitions are same as each other. => size(Group2) = p(n, m-1)

Answer 2

        / 0 (k>n) p(k,n)={  1 (k=n)         \ p(k+1,n)+p(k,n-k) (k<n) 

Number of partitions of n is p(1,n).

p(k,n) is number of partitions of n, allowing only addends >=k.

Like the OP's recursive formula, it adds them (as luiges90 put it) one by one (with the added inefficiency of numerous zeroes). Fortunately, though, it can be calculated inside an array with great speed:

#include <stdio.h>  /* 406 is the largest n for which p(n) fits in 64 bits */ #define MAX 406 long long int pArray[MAX][MAX];  /* Emulate array starting at 1: */ #define p(k,n) pArray[k-1][n-1]  int main(int argc, char **argv) {     int n, k;     for (n = 1; n < MAX; n++) {         for (k = n; k > 0; k--) {             if (k > n) {                 p(k, n) = 0;             } else if (k == n) {                 p(k, n) = 1;             } else {                 p(k, n) = p(k, n - k) + p(k + 1, n);             }         }     }     for (n = 1; n < MAX; n++) {         printf("p(%d)=%lld\n", n, p(1, n));     } }