Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search