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

### 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 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/
```
Associated Topics:
High School Number Theory
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