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)