Sum of Natural Numbers

Date: 11/23/97 at 15:45:57
From: Helmut Lerche
Subject: Combinatorics

Hello,

Is there a formula for counting all the possibilities for writing a 
natural number (1,2,3, etc.) as the sum of natural numbers (order is 
not important)?

Example: The natural number 4 can be written as:
1+1+1+1
1+1+2
1+3
2+2
4

This means that for 4 there are 5 possibilities.

Thank you very much for helping me. Yours sincerely,

Helmut Lerche from Germany (Upper Bavaria near Munich)

Date: 11/23/97 at 16:49:47
From: Doctor Anthony
Subject: Re: Combinatorics

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. There is a recurrence relationship which allows you to fill 
in a table of values. 

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
 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
 Check out our web site!  http://mathforum.org/dr.math/