Partitioning an Integer

Date: 11/14/98 at 06:25:51
From: Sam Huckin
Subject: triples like (1,2,2), (3,1,1) = 5   

I'm investigating how many different ways there are of making a number 
using different combinations of three numbers. For example, you can 
make a 5 by adding these triples: (1,2,2), (3,1,1). Does this have a 
formula?  

Thanks,
Sam

Date: 11/14/98 at 07:28:55
From: Doctor Anthony
Subject: triples like (1,2,2), (3,1,1) = 5  

This problem relates to the 'partition' of numbers. There is extensive 
literature on the subject, and it is algebraically quite demanding. For 
example the number of partitions of n into any number of parts but none 
exceeding q is the coefficient of x^n in the expansion of:

  (1-x)^-1 (1-x^2)^-2 (1-x^3)^-1 .....  (1-x^q)^-1.

I will use the notation P(n,p) to represent the partition of n into p 
parts, for example P(50,10) is number of partitions of 50 into 10 
parts. One example is (1,2,2,3,4,5,6,7,9,11).

There is a recurrence relationship which allows you to fill in a table 
of values. So if you have the patience you can complete a table to get 
the answer you want.

The recurrence relationship is P(n,p) = P(n-1,p-1) + P(n-p,p)

And if this is applied continuously we get:

   P(n,p) = P(n-p,1) + P(n-p,2) + P(n-p,3) + .... + P(n-p,p)

So for example:

   P(20,5) = P(15,1) + P(15,2) + P(15,3) + P(15,4) + P(15,5)
           =    1  +    7     +     19   +    27   +    30
           =   84

Below is the start of such a table: 

n|1 2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
-+--------------------------------------------------------------------
p|
1|1 1  1  1  1  1  1  1  1   1   1   1   1   1   1   1   1   1   1   1
2|  1  1  2  2  3  3  4  4   5   5   6   6   7   7   8   8   9   9  10
3|     1  1  2  3  4  5  7   8  10  12  14  16  19  21  24  27  30  33
4|        1  1  2  3  5  6   9  11  15  18  23  27  34  39  47  54  64
5|           1  1  2  3  5   7  10  13  18  23  30  37  47  57  70  84
6|              1  1  2  3   5   7  11  14  20  26  35  44  58  71  90
7|                 1  1  2   3   5   7  11  15  21  28  38  49  65  82
8|                    1  1   2   3   5   7  11  15  22  29  40  52  70
9|                       1   1   2   3   5   7  11  15  22  30  41  54
10|                          1   1   2   3   5   7  11  15  22  30  42

If you require P(50,10) you should take the table as far as the n = 40 
column, and then find:

   P(50,10) = P(40,1) + P(40,2) + P(40,3) + ..... + P(40,10)        
 
- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/