The way we can write a whole number as a sum of whole numbers
has long interested mathematicians. They are called partitions
and have many practical applications.
Integer Sums
Contents of this page
The icon means there is a
Things to do section of questions to start your own investigations.
The calculator icon
indicates that there is a live interactive calculator in that section.
Sums in their different forms
How many ways can you write a number as a sum?
That is basically what we are looking at on this page, the various forms and what happens if we put
extra conditions on the sum, such as it must only be odd numbers that are used.
These are called partitions of n but other words are used too depending on what we mean by
the same sum. For instance is 2+1 the same sum as 1+2 or do we want to
count it as a different answer. If a different order of the same numbers gives a different
answer, we will call them compositions of n (following D E Knuth and G E Andrews and others)
and if the order of the numbers in the
sum does not matter so that different orders of summands are counted as the same sum, then we
call them partitions of n.
Here we are interested in
partitioning a number meaning to write a positive whole number as a sum of smaller
positive whole numbers, e.g:
9 = 5 + 2 + 1 + 1
Rods
There are also different ways that we can classify our partitions. A useful illustration is
the rods of different lengths that children play with.
We assume there are as many of each length as we need,
each length having its own unique colour, from
single red ones
(length 1 which are cubes), length 2 are orange,
length 3 are blue and so on as shown in this table:
length 1
length 2
length 3
length 4
length 5
...
...
With this scenario, we are interested in putting rods in a line to make a given length.
We are sometimes interested in the order of the colours, and other times just the number of
each kind of rod used. Sometimes we will want any colour to be used no more than once in each line.
Partitions and Compositions
Both of these names have many uses in mathematics.
The word partition can mean partitioning a set into
subsets (as in partitioning a computer hard-drive so that various parts are used for various separate and
distinct purposes). Also a composition in maths can apply to combining two functions into one
by applying two or more functions in order one after the other. Neither of these uses are the subject of this webpage!
So let's be a little more precise about how these two words as used in Number Theory, though
be careful because other mathematicians use different words.
Some just use the single word partition
but then qualify it by saying "of distinct numbers" and "where the order is important".
Partitions of an integer N (the order in the collection does not matter)
A set of whole numbers (a collection of unique numbers, no repetitions) whose sum is N,
where the order does not matter.
In terms of the rods, we are interested in the number of each colour used.
For instance, the partitions of 3 are [1,1,1], [1,2] and [3] only. [2,1] is the same partition
(contains exactly the same elements) as [1,2].
If numbers may be repeated in the sum
then the collection is called a multi-set or bag.
Here we allow [1,1,1] but [1,2] is the same collection as [2,1].
Compositions of an integer (the order of the parts in the sum is important).
A sequence or list of whole numbers whose sum in N,
where the order does matter and numbers may be repeated in the sequence.
These are sometimes called ordered partitions (as in MathWorld)
meaning that the only collections used are those
with the parts "in order" but we will use the term
compositions.
Other names for a sequence are:
a list and
as a generalisation of
double, triple, quadrulple, ... they are also called tuples.
Again we ask if items are allowed to be repeated in a composition sequence. If not, the parts
of any composition must be unique, distinct.
Compositions without repetitions (distinct or unique parts)
For instance, the compositions of 3 are [1,2], [2,1] and [3] because the order is now important.
If repetition is not allowed then we must exclude [1,1,1].
For the rods, the sequence of colours along the line is important so that [1,2] is red-orange
whereas [2,1] is orange-red so they are different arrangements.
Compositions with repetition allowed.
In these collections the order matters (a different ordering
of the components gives a separate composition) but items can be repeated.
Here all 4 sequences that sum to 3, namely [1,1,1], [1,2],[2,1] and [3] are all counted and are all different.
Notation
Using {} and [] brackets
Sets are traditionally written using curly brackets: {3,1,2}. Lists are written in a variety of bracket styles,
sometimes inside round brackets () or square [] or angled brackets<>. We will use [] on this page.
Items are listed once since in a set the property of interest is if a number is in the set or not
so repetitions are irrelevant and no item is listed more than once.
For the rods illustration, no colour of rod may be used more than once and it is the collections of colours
that we want to count.
For a multiset, we are now not only interested in whether or not an element is in the
collection but also the frequency of an item is needed.
There are a variety of notations for a multi-set but here we will still use curly brackets.
There are 3 multisets of integers that sum to 3: {3}, {1,2} and {1,1,1}.
There are 3 sequences of distinct numbers that sum to 3, namely [3], [1,2] and [2,1].
We will also include [1,1,1] if we are allowed to repeat items in the list.
Partitions can involve repetitions or not. Compositions are sometimes called ordered partitions too.
A common notation is to use p( n | conditions ) where we note the conditions on a partition
after the vertical line.
The parts of the partition are therefore p_{i} with p_{1} being the first number in the partition
and often we ues p_{k} for the last so that there are k numbers in the partition; it has length k.
Partitions mean we list the parts in order (smallest to largest or largest to smallest):
Partitions with repetition: p(n | p_{1} ≥ p_{2} ≥ ... ≥p_{last})
Partitions without repetition: p(n | p_{1} > p_{2} > ... >p_{last})
Compositions the order counts so we do not include the inquality conditions above.
A more compact notation for the parts:
Sometimes, writing a partition as {1,1,1,1,1,1,3,3,3,3,3} would be easier
if we showed the frequency of the parts.
A shorthand notation that is used is based on how multiplication and powers are written
even though we are looking at sums! The superscript means the frequency of the number.
So the example partition here has 6 1s and 5 3s and would be written
1^{6} 3^{5}
The short-notation partition a^{p} b^{q} c^{r}...
has sum a p + b q + c r + ...
A source of confusion: sorted or ordered
One source of confusion is that with the collections where the order does not matter, in fact it does!
By "order does not matter" we mean that reordering the elements will not produce a different answer;
any order is equivalent to any other order provided the frequencies of the elements are the same.
Among the Partitions of 7 we have:
[1,1,2,3] which is the same as [1,2,1,3] and [1,1,3,2] and [3,2,1,1] and some others
Show the others?
[1,2,3,1],[1,1,3,2],[1,3,1,2],
[2,1,1,3],[2,1,3,1],[2,3,1,1],
[3,1,2,1],[3,1,1,2]
12 in all since we choose any of the 4 for the first in the list, leaving any of the remaining 3
for second place, any of the final 2 for third place (and so the final element is in fourth place)
giving 4×3×2=24 ways,
except that there are two 1s so we have counted each collection twice (
the second having the two 1s "invisibly" swopped).
Thus there are
4×3×2
= 12
2
different permutations of 1 + 1 + 2 + 3.
since each of these contains two 1s, one 2 and one 3 and these are the same partition of 7.
So one simple way to remove the duplicates is to filter the possible permutations of the items
and only
include those that are sorted, already in order, that is
only count those in increasing order say. Except that, where we may have values repeated, we
allow equal items. This is usually written as "non-decreasing" instead of "increasing" to allow
for the equal items.
In the example permutations above, only the first is chosen as the representative
of the rest because it has its elements in order.
So "order does not matter" is equivalent to "counting only those lists that
are already sorted or ordered"!
"Order does matter" means that every collection counts, whether it is sorted into some order
or not!
This is important particularly when writing a program to find various partitions and compositions
but often leads to confusion on first meeting partitions and compositions.
Mathematical Definitions
We can use the idea of a sum to define our various kinds of partitions:
Each sum is a list a_{1}, a_{2}, a_{3}, ...a_{k}
of k terms or parts,
where all the parts a_{i} are positive whole numbers.
The main condition is thata_{1} + a_{2} + ... + a_{k} = n.
Usually we want all the variables (parts) to be positive (non-zero) whole numbers.
Notation:
The set of natural numbers: {0,1,2,3,...} is
ℕ
If we want to exclude 0 and just indicate the strictly positive integers {1,2,3,...}, we
use ℕ^{+}
The symbol ∀, an upside down "A", means for all so ∀ i=1..k some condition
means the condition applies to
all the indices i from i to k.
Partition bag or Partition multi-set
Any solution of
a_{1} + a_{2} + ... + a_{k} = n ∀ i=1..k, a_{i}∈ℕ^{+}and
1 ≤ a_{1} ≤ a_{2} ≤ ... ≤ a_{k} ≤ n The possibility of equality between each pair of terms allows for terms to be repeated.
Partition set (distinct parts)
Any solution of
a_{1} + a_{2} + ... + a_{k} = n ∀ i=1..k, a_{i}∈ℕ^{+}and
0 < a_{1} < a_{2} < ... < a_{k} < n
Here all the a_{i} are unique and there is no equality allowed between items:
no value appears more than once in the partition. This is also
the condition that the partition forms a set (no repetitions):
a_{i} = a_{j} if and only if i = j (for 1≤i<j≤k)
Composition of n with repetitions
Any solution of
a_{1} + a_{2} + ... + a_{k} = n, ∀ i=1..k, a_{i}∈ℕ^{+} Since each term in the sum is separately named, the order in the sum matters
and terms may be repeated.
Composition sequence without repetitions
Any solution of
a_{1} + a_{2} + ... + a_{k} = n ∀ i=1..k, a_{i}∈ℕ^{+}and
a_{i} = a_{j} if and only if i = j The second condition ensures no numbers are repeated in a partition but
the a's can be in any order.
We are considering the numbers in sequence here, not as a set.
How many?
There is one solution to a collection of positive numbers whose
sum is 0, namely the empty sequence [] or the empty set {}.
Compositions (Sequences with repetitions)
These are sequences that sum to a given value and items in the sequence may be repeated.
Here we use the short notation where the number of repetitions of a number is
indicated as a superscript, a "power" and all the numbers are single digits in the following tables.
The number of compositions (sequences with repetition allowed) of a number n is the easiest to
find a formula for.
Do you recognize the counts in the final column?
But why? Can you find a reason? Show an answer
We can write the compositions as follows:
... write n 1s in a row then put a "," or a "+" between
them in all possible ways.
The composition is found by performing the additions:
[1, 1, 1, 1]
1 , 1 , 1 , 1
3 commas, 0 additions
[1, 1, 2]
1 , 1 , 1 + 1
2 commas, 1 addition
[1, 2, 1]
1 , 1 + 1 , 1
[2, 1, 1]
1 + 1 , 1 , 1
[1, 3]
1 , 1 + 1 + 1
1 comma, 2 additions
[2, 2]
1 + 1 , 1 + 1
[3, 1]
1 + 1 + 1 , 1
[4]
1 + 1 + 1 + 1
no commas
There are two choices for each of the n-1 spaces between the n 1s
so there are 2^{n-1} compositions of n allowing repetitions.
The number of compositions of n allowing repetitions in a composition: 1, 1, 2, 4, 8, 16, 32, 64, 128, 256,... A011782.
The Calculator below will provide approximations to the number of compositions
(sequences with repetition) for very large n up to around
n=1000 before even the approximations become too large for JavaScript when
they exceed 1.7×10^{308}).
Compositions (sequences without repetitions)
Sequences with no repeated elements and with a given sum n.
They are also called compositions with distinct parts .
n
Sequences without repeated items
Count
1
1
1
2
2
1
3
3, 12, 21
3
4
4, 13, 31
3
5
5, 14, 41, 23, 32
5
6
6, 15, 51, 24, 41, 123, 132, 213, 231, 312, 321
11
The counts are 1,1,3,3,5,11,13,19,27,57, ... A032020
Counting compositions without repetition where
~ indicates an approximate number:
n
Count
10
57
50
107 59321
100
109 38301 18491
500
~9.184809494×10^{37}
1000
~1.541212300×10^{60}
2000
~3.042018006×10^{94}
10000
~4.355395751×10^{259}
Partitions (sets with repetition: multi-sets or bags)
1,2,3,5,7,11,15,22,30,42, ... A000041
The number of partitions (multi-sets with repetitions) of n is usually denoted by p(n).
n
p(n)
10
42
100
1905 69292
200
397 29990 29388
500
23 00165 03257 43239 95027
The number of digits in a value x is calculated by 1+log_{10}(x)
Here are some graphs of the number of partitions (bags) to show that the number
increases very rapidly:
1..20:
1..30:
1..100:
1..500:
Number of digits, 1..500:
The Calculator below will provide approximations to p(n) for very large n up to around
n=76000 before even the approximations become too large JavaScript (they exceed 1.7×10^{308})!
The counts are
1,1,2,2,3,4,5,6,8,10, ... A000009
There are 444793 Partition-sets for 100 and
86 35565 79574 41551 61506 for 1000.
Partitions and Compositions into parts
If we specify that our partitions and compositions are to be of a given length k, we are saying that
they must contain exactly k non-zero numbers or have k parts.
Compositions into parts
We can further classify compositions by how many numbers are in the list:
There are 2^{3} = 8 compositions of 4:
Compositions of 4 with 4 parts: [1,1,1,1]
Compositions of 4 with 3 parts: [2,1,1], {1,2,1], [1,1,2]
Compositions of 4 into 2 parts: [1,3], [3,1], [2,2]
Compositions of 4 into 1 part: [4]
Count comparison for partitions and compositions
Here is a table of the number of partitions and compositions for small values and some large ones
n
Partitions (sets/bags)
Compositions (sequences)
no reps
with reps
no reps
with reps
1
1
1
1
1
2
1
2
1
2
3
2
3
3
4
4
2
5
3
8
5
3
7
5
16
6
4
11
11
32
7
5
15
13
64
8
6
22
19
128
9
8
30
27
256
10
10
42
57
512
20
64
627
1555
524288
30
296
5604
41867
5.369×10^{8}
50
3658
204226
10759321
~5.630×10^{14}
100
~4.447×10^{5}
~1.905×10^{8}
~1.093×10^{12}
~6.338×10^{29}
200
~4.870×10^{8}
~3.973×10^{12}
~1.011×10^{20}
~8.034×10^{59}
Partitions and Compositions Calculator
A Partition:
a set (without repetition of items) or bag (with repetition allowed);
The order of items in the collection does not matter.
Collections are equal only if they contain the same number of
each kind of item.
Shown using {} brackets;
A Composition:
a sequence (list); shown using [] brackets.
The order in the collection does matter.
Collections are equal only if they contain the exactly same items in the same order
This Calculator uses formulae and recursion to compute exact and for approximate counts
when the choices are unrestricted (are all the whole numbers).
NaN means Not a Number and indicates that an approximation formula is not yet implemented here for Compositions without Repetition.
Use the Restricted Partitions calculator below if the choices are restricted or you want
only a specific number or range of part lengths.
The counts from n=1 onwards are: 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, ...
Another special case is to look at the partitions that are sets, that is,
the ones that contain no repeated item: p(n| no repeated parts)
Partitions with only unique elements
n:
1
2
3
4
5
6
Partitions
{1}
{2}
{1, 2} {3}
{1, 3} {4}
{1, 4} {2, 3} {5}
{1, 2, 3} {1, 5} {2, 4} {6}
Counts
1
1
2
2
3
4
The counts from n=1 onwards are: 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, ...
Is this just coincidence?
No, since the match continues for ever. The series is A000009.
The famous Swiss mathematician Euler noticed this and wrote about it in 1748 and we look at this again below.
1,1,1,1: number of distinct parts: 1 1,1,2: number of distinct parts: 2 1,3: number of distinct parts: 2 2,2: number of distinct parts: 1 4: number of distinct parts: 1
Total: 1+2+2+1+1 = 7 distinct parts
Some partition multisets contain a 1 (possibly more) as here for 4 where we count the number of 1s used in all the partitions on the left.
If we look at the number of distinct integers used in each of these partitions we have this table on the right.
These counts will always be the same for every n!
Partition sets and Partition bags of odds
The number of partition on n into distinct parts (sets) is the same as
the number of partitions of n using only odd numbers but with repeats allowed:
n
4
5
6
7
8
9
10
11
12
13
14
15
16
#
2
3
4
5
6
8
10
12
15
18
22
27
32
Show why
Let's look at example:
7 as a sum of distinct integers in 5 ways: {1,2,4}, {1,6}, {2,5}, {3,4}, {7}.
For each partition we can convert it into a bag (multiset) of odd numbers as follows:
express each part as (sum of powers of 2)×odd where odd is an odd number and its
frequency will be the number in binary that precedes it.
{3,4} becomes { (2^{0})×3 + (2^{2})×1}
The numbers in brackets are the frequencies of the odd numbers after the × symbol:
{3,1,1,1,1}.
Check the correspondence with the other (set) partitions of 7:
partition set
as binary×odd
partition (bag) of odds
1,2,4
(2^{0})×1,(2^{1})×1, (2^{2})× 1
1 + 1+1 + 1+1+1+1
1,6
(2^{0})×1,(2^{1})×3
1 + 3+3
2,5
(2^{1})×1, (2^{0})×5
1+1 + 5
3,4
(2^{1})×3, (2^{2})×1
3 + 1+1+1+1
7
(2^{0})×7
7
Similarly, a bag of odd numbers may be transformed into a set of distinct numbers with the same sum:
1,3,5 is a partition of 9 into odd numbers but none are repeated so it corresponds to the same as a (set) partition.
1+1+1+1+5 is a partition of 9 into odd numbers. This is also (2^{2})×1,(2^{0})×5 so
corresponds to 4+5 as a sum of distinct parts.
Mathematical Gems III Ross Honsberger,
Math. Assoc. of Amer. in ch 6 Two Applications of Generating Functions section 1 A Theorem of Euler
pages 64-68 which also has a proof of this correspondence
Diagrams of Partitions: Ferrers Diagrams and proofs-without-words
A visual approach to partition bags and sets is to consider how many different
arrangements of n dots there are on a square grid.
The number of dots in a line corresponds to one part or the partition. Since we
are dealing with sets and bags, we can order the numbers in each partition from largest to
smallest.
For example, 12 = 6 + 3 + 2 + 1 and we can show this as dots or as squares:
These pictures of a partition are called Ferrers Diagrams or Ferrers boards and also
Young digrams. They immediately illustrate a fact about partitions:
# partitions with largest part k = # partitions with k items
The # symbol (hash) means the number of.
The number of partitions (sets and bags) with k parts is equal to
the number of partitions (sets and bags) with largest part k
By looking at the Ferrers diagram in two ways, can you see why?
Show why
The length of the rows are the parts of the partition, e.g.6,3,2,1.
The largest row is the largest number in the partition, in our example it is 6.
By looking at the columns we have a partition with exactly k parts.
In our example there are 6 columns.
Since every diagram can be viewed in these two ways, as rows and as columns,
the two counts must be identical:
The number of partitions with largest part equal to k (as rows, with k in the longest row) and
The number of partitions with k parts (as k columns).
# partitions into even parts = # partitions where each part occurs with even frequency
Using the same reasoning we can see that
The number of partitions of n into parts all of which are even numbers is the same as
the number of partitions of n where each part in it occurs an even number of times
Consider this example of 12 = 6 + 2 + 2 + 2 and it corresponds to 12 = 4 + 4 + 1 + 1 + 1 + 1
where 4 occurs twice and 1 occurs four times, and the frequencies one and four are even numbers:
The conjugate partition of a partition is found by
flipping its Ferrers diagram so that the rows become columns and the columns become rows. This is the same as
reflecting the shape in the diagonal from top-left to bottom-right.
For example:
{6, 3, 2, 1}
flips to
{4,3,2,1,1,1}
↔
If a Ferrers diagram is the same when flipped then the
partition is called self-conjugate. For example:
12 = 5 + 3 + 2 + 1 + 1 : {5,3,2,1,1}
Since these self-conjugate diagrams have the same number of rows as columns, we can remove the top row and
the leftmost column and we will still have another self-conjugate partition:
The total number of dots on the top row plus the left edge must always be
an odd number (we only count the top left corner dot once).
It is now but a short step to see that we can always match a self-conjugate partition with one
made with only odd parts by repeatedly stripping off all the top-row-and-left-edges
and noting how many dots are removed each time. For example, in the diagram above, we remove
9 and then 3 so self-conjugate partition {5,3,2,1,1} corresponds to the
partition of only odd numbers: {9,3}.
The number of self-conjugate partitions of n is the same as
the number of partitions of n with distinct odd parts.
Generating Functions
The essential idea here is to relate a series with a polynomial with the
the series' numbers as it coefficients, so that s_{i}, the i^{th} member of the series
is also the coefficient of x^{i} in the polynomial.
Since the series of infinite, so is the polynomial. Such infinite polynomials in a power of a variable (often x)
are called power series.
the series: s_{0}, s_{1}, s_{2}, ... ↔ s_{0} + s_{1}x + s_{2}x^{2} + ... :the power series
We know a lot about polynomials and when we can find a simple expression for the polynomial then we can
deduce more things about the series related to its coefficients.
The sequence 1,1,1,1,...
This is the basic series and its generating function, let's call it G(x) for now, is
G(x) = 1 + x + x^{2} + x^{3} + ...
This is the same as a simple expression involving x:
We express x G(x) is two ways:
x G(x) = x + x^{2} + x^{3} + ...
but if we add 1 to the right-hand side we have G(x) again:
1 + x G(x) = G(x)
Now we can rearrange this to find an expression for G(x):
1
= G(x) − x G(x)
1
= ( 1 − x) G(x)
1
= G(x)
1 − x
so we see that
1 + x + x^{2} + x^{3} + ... =
1
1 − x
The decimal fraction for 1/9
Once we put a value for x into a generating function, we need to be careful about whether
the series converges or not. We will not pursue this further on this page but it is an important
condition.
If we let x=1/10=0.1 in the power-series for 1/(1-x) we have
Since x can be any number, not just 1/10, then with x=1/2 we have the binary value
1.11111..._{2} = 2
With x=1/3, 1.11111..._{3} = 3/2 = 1 + 1/2. This is a quick proof that
1
+
1
+
1
+
1
+ ... =
1
3
3^{2}
3^{3}
3^{4}
2
The decimal fraction for 1/98
Another example uses x=^{1}/_{100} in the power-of-two generating function which we find by replacing
x by 2x in the GF above:
Looking at the fraction form with x=1/100 we have:
x
=
1/100
=
1
=
1
1 - 2 x
1 - 2/100
100 - 2
98
and this explains why the decimal fraction for ^{1}/_{98} is the powers-of-two
in blocks of 2 digits!
Number of partitions (sets)
Another easy association between a series and a generating function (power series) is the series
that counts the number of partition sets with sum n (partitions without repetition, partition sets):
n
1
2
3
4
5
6
7
8
9
10
11
12
...
#
1
1
2
2
3
4
5
6
8
10
12
15
... A000009
Here we will see that it the counts are just the coefficients in the (infinite) expansion of
To see this, we can find only one way to get the coefficient 1, by picking the "1" from each of the brackets.
There is similarly only one way to get x^{2}, by choosing the 1 frmo all the brackets and the
x^{2} from the (1 + x^{2}) bracket.
When it comes to x^{3}, we can choose (1 + x)(1 + x^{2}) and 1 from all the other brackests
OR 1's from all except the (1 + x^{3}) brackets, since 3 is 1+2 and 3.
For 4, since 4 = 1+3 where are two ways of choosing the terms. This is because each powers of x can only be used once
so there are no repetitions, and also there is essentially only one order to choose each collection of x's
that multiply to x^{4}.
The Generating Function for the number of partition (sets) for n is
where the capital Pi symbol Π stands for Product, meaning we multiply all the terms
(1 + x)^{i} for values of i from 1 up to infinity.
The General Pentagonal Numbers
If we make a list of the number of partitions of n (sets without repetition) for n from 1 to 20 say) and count the number of partitions of n that are of even length
and the number of odd length. For some numbers, these are equal.
Counts of Partitions of n without repetition by number of parts (even or odd length)
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
p(n)
1
1
2
2
3
4
5
6
8
10
12
15
18
22
27
32
38
46
54
64
76
89
104
122
142
165
# even length
0
0
1
1
2
2
3
3
4
5
6
7
9
11
11
16
19
23
27
32
38
45
52
61
71
83
# odd length
1
1
1
1
1
2
2
3
4
5
6
8
9
11
12
16
19
23
27
32
38
44
52
61
71
82
difference
+1
+1
-1
-1
+1
+1
-1
-1
k
1
1
2
2
3
3
4
4
For which numbers are they not equal?
For n = 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, .... A001318
These are the General Pentagonal Numbers, given by the expression n = (3 k^{2} ± k)/2, for k=1,2,3,... which are
the Pentagonal Numbers for positive and negative k.
The sign of the difference depends on k.
If k is odd the difference is +1; if k is even, the difference is -1. Show the k values in the Table above
This was implied (known) by Euler but not stated by him as such. (See Dickson Vol II, page 113)
Number of partitions with repetition (bags or multi-sets)
This time we can repeat any number in our collection whose sum is n.
We have already seen that
1 + x + x^{2} + x^{3} + ... =
1
1 − x
This essentially relates to choosing 1 (the coefficient) and number of times (as given by the power of x).
If we replace x by x^{2} we have
1 + x^{2} + x^{4} + x^{6} + ... =
1
1 − x^{2}
which gives us powers which are multiples of 2. Similarly for multiples of 3
1 + x^{3} + x^{6} + x^{9} + ... =
1
1 − x^{3}
So we make a partition of n which allows repetitions, we choose one term from the first series to represent
the number of 1s or choose 1 itself if we do not want to use any 1's;
choose one term from the second series to represent 2s, and so on,
provided that the product of all the terms used is x^{n}!
We therefore have
number of partition bags with sum n are the coefficients of
1
1
1
1
...
(1 - x)
(1 - x^{2})
(1 - x^{3})
(1 - x^{4})
A Historical note
The connection with these generating functions is why the term partition is linked with this
particular form of partition: a multiset (bag) with repetition allowed.
The connection goes back to Euler and intrigued
Ramanujan
and many others as it is rich in interesting connections and theorems.
If we let p(n) denote the number of partitions (bags with repetition allowed)
then Ramanujan noticed and proved that
S Ramanujan (in Proceedings of the London Mathematical Society, Series 2, vol 16 (1918) pages 352-4)
published some results about p(n), the number of partitions (bags with repetitions allowed)
of n: (a ≡ 0 (mod b) means a is a multiple of b)
Ramanujan thought he had found a more general pattern based on a large table of partitions and on
his observations, but he was slightly wrong.
It was quite a few years later (1967) before a correct generalisation was found and proved by
A O L Atkin:
Theorem: If 24 n leaves a remainder of 1 when divided by 5^{a} 7^{b} 11^{c}
then p(n) is a multiple of 5^{a} 7^{(b+2)/2} 11^{c}
Andrews (Theory of Partitions, page 160) gives an example to show why this new form was needed and not,
as Ramanujan conjectured, the simpler
... then p(n) is a multiple of 5^{a} 7^{b} 11^{c}:
Let n=243 and a=0,b=3,c=0.
Then 24 n = 24×243 does have a remainder of 1 when divided by 7^{3} but
p(n) = p(243) = 133978259344888 which is not a multiple of 7^{3}.
The modified (correct) theorem
excludes this case because (b+2)/2 is not an integer when b=3.
Proof of a Conjecture of Ramanujan A O L Atkin Glasgow Math Journal8 (1967) pages 14-32
Number of compositions (sequences with repetition)
We have already seen that there are 2^{n-1} composition sequences with sum n if we allow
repetitions in a sequence. So how do we find the generating function for
1, 1, 2, 4, 8, 16, ... ?
We can start from the powers-of-2 generating function:
Number of compositions (sequences without repetition)
1, 1, 1, 3, 3, 5, 11, 13, 19, 27, 57, ... A032020
This it seems is not possible as a simple power series!
Application: giving coins in change
Suppose a shopkeeper has a cash drawer with lots of £1, £2 coins and £5 notes.
A customer needs change to the value of £12. In how many ways can the shopkeeper give £12 using
only those denominations in the cash drawer?
Since we can repeat coins and the order of coins does not matter in the change, we have paritions with
repetition or multi-sets or bags (of change).
The repetition of 1s has the generating function
1
= 1 + x + x^{2} + x^{3} + ...
1 − x
The repetition of 2s has the generating function
1
= 1 + x^{2} + x^{2×2} + x^{3×2} + ...
1 − x^{2}
The repetition of 5s has the generating function
1
= 1 + x^{5} + x^{2×5} + x^{3×5} + ...
1 − x^{5}
The GF for the number of ways of giving change is therefore
1
(1 − x)(1 − x^{2})(1 − x^{5})
We are interested in the coefficient of x^{12} in this GF which begins:
and we see there are 13 ways to give the change to the value of £12.
Why not try to find them yourself and then check with this Calculator
("Show partitions (sets) with sum 12 and parts from 1,2,5 with repetitions"):
On Picture Writing G Pólya Amer Math Monthly 63 (1956) pages 689-697
A wonderful article that popularised generating functions for counting change-giving solutions and to solve two other
example problems.
A GF for Counting the number of parts in partitions
Euler also found that there is a simple GF for generating not only the number of partitions of n, but also
the counts for each size of partition of n. He introduced an extra variable z as a coefficieint of the powers
of the main variable x:
the z terms come from a single x power z
term and 1s from the rest of the brackets;
the z^{2} terms come from two of the x powers and
in general, the z^{k} terms come from
k of the x powers where the x power sum is n and so count the partitions for n of length k.
For example, in the z^{2} line
there is a term 2 x^{5}.
This means there are 2 partitions (the coefficient) of 5 (the power of x)
of length 2 (because the power of z is 2): x^{2}z × x^{3}z
and also
x^{1}z × x^{4}z.
Another term is 4 z^{3} x^{10},
telling us that there are 4 partitions of 10 of length 3
where the powers of x give the parts in the partitions of 10:
1+2+7, 1+3+6, 1+4+5, 2+3+5.
We see that the parts are distinct and that the order of the parts does not matter.
A GF for self-conjugate partitions and sets of odds
We saw above that the number of self-conjugate partitions (multisets with repetition) of n
is the same as the number of partitions (sets) of n into unrepeated odd parts.
It is easy to find a GF for the number of partitions into unrepeated odd numbers:
J J Sylvester (1882-3) showed this also has the following form (see Dickson, Vol II, page 137)
where the terms give the GFs for sums of 1, of 2, of 3 ... odd numbers.
Only the odd numbers themselves
are a sum of 1 odd number so the series 0,1,0,1,0,1,0,... (starting from 0) are the coefficients of
x
1 - x^{2}
.
The numbers of ways to make n by adding 2 distinct odd numbers is 1+3=4. 1+5=6. 3+5=1+7=8, ...
so 4 has 1 partitions (1 is the coefficient of x^{4}),
6 has only 1 also (1 is the coefficient of x^{6}),
8 has 2 (2 is the coefficient of x^{8})
giving the sequence of coefficients of x
as
0,0,0,1,0,1,0,2,... and these are the coefficients of x in
x^{4}
(1 - x^{2})(1 - x^{4})
and so on for the other terms in Sylvester's expression:
= 1 +
x
+
x^{4}
+ ... +
x^{k2}
+ ...
1 - x^{2}
(1 - x^{2})(1 - x^{4})
(1 - x^{2})(1 - x^{4})...(1 - x^{2 k})
The sequence of coefficients is 1, 1, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, ... A000700.
You Do The Maths ...
There are 3 self-conjugate partitions (bags with repetition) of 12 and therefore also 3
partitions (sets) of 12 with parts that are odd numbers. Find these.
Self-conjugate (multiset) partitions of 12 are 1^{4} 2 6, 1^{2} 2 3 5,
2^{2} 4^{2}
The partitions (sets) of partitions of distinct odd numbers for 12 are {1, 11}, {3, 9}, {5, 7}
Show the answers
There are 7 self-conjugate partitions (bags with repetition) of 20 and therefore also 7
partitions (sets) summing to 20 with parts drawn from the odd numbers. Find these.
Self-conjugate (multiset) partitions of 20 are 1^{8} 2 10, 1^{6} 2 3 9,
1^{4} 2^{2} 4 8, 1^{2} 2^{3} 5 7, 1^{2} 4^{3} 6,
2^{4} 6^{2}, 2 4^{2} 5^{2}
The partitions (sets) of distinct odd numbers for 20 are
{1, 3, 5, 11}, {1, 3, 7, 9}, {1, 19}, {3, 17}, {5, 15}, {7, 13}, {9, 11}
Show the answers
Partitions Calculator with restricted choices
This Calculator searches for partitions so is slower than the unrestricted Calculator above.
The parts may be repeated. If you wanted, say, up to three 1s in a partition then choose
and put "1,1,1" in the chosen from input. However, these repetition are
essentially different objects but with the same numeric value;
think of them as having differing colours. Total count will give the total number of partitions (in a given range) for each sum. Count parts will give a count for each part length for each sum.
Restricted Partitions C A L C U L A T O R
Leave inputs empty if not needed
chosen from
leave blank for whole numbers 1,2,3,...
Change for a US dollar
You have a dollar bill (100 cents).
In how many ways can you change it using quarters (25 cents)? 1 way
In how many ways can you change it if you have quarters (25 cents) and dimes (10 cents) available? 3 ways
In how many ways can you change it if quarters (25 cents), dimes (10 cents) and nickels (5 cents) are available? 29 ways
Show the answers
Binary weights
I have a set of 4 weights in grams: 1g, 2g, 4g, 8g.
What is the maximum I can weigh? 1+2+4+8=15g
In how many ways can I make a given value of grams up to that weight? just 1 way
If I have several copies of each of the weights, in how many ways can I make 12g? 16 ways
Show the answers
Binary with repetitions
Extend the last question by making a table of the number of ways to make n using powers of two, repetition allowed,
with n from 0 to 20.
Let b(n) count the number of partitions (bags) of n with repetitions
when the parts are powers of 2. Can you form some conjectures?
Can you prove some of them? Show the table
Partitions (bags) of 1..20 using {1,2,4,8,16} with repetition:
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#
1
2
2
4
4
6
6
10
10
14
14
20
20
26
26
36
36
46
46
60
Show a hint
Hint: Look at the differences in the (pairs of) counts. Where have you seen that series?? Show some conjectures
Conjecture: Values repeat in pairs
b(2n + 1) = b(2n) for all n
For an odd number, its partition must begin with 1. The rest of the partition is
a partition of 2n. We can form every partition of an odd number by prepending a 1
to any partition of the even number before it.
Conjecture: The even-indexed values (n is even)
b(2n) = b(2n - 1) + b(n)
Look at the difference between successive pairs. Why?
Case 1: You can get such a partition of 2n by adding 1 to the front of any of the partitions of 2n-1.
Case 2: Alternatively, if all the parts are even, then halving a partiton of 2n is a partition of n.
All such partitions of 2n are covered by just one of these two cases.
Conjecture: All values after n=1 are even
b(n) is even, n>1. This follows if the above two conjectures are true.
Conjecture: From n=12, alternate pairs are divisible by 4
b(12)=b(13)=20=4×5 ✓ b(14)=b(15)
b(16)=b(17)=36=4×9 ✓ b(18)=b(19)
b(20)=b(21)=60=4×15 ✓ b(22)=b(23)
b(24)=b(25)=94 ✗ is not a multiple of 4.
But there is a pattern in the multiples of 4 if we take alternate alternate pairs
starting from b(4)=b(5), b(12)=b(13), ...
Base 3 with repetition
Repeat the previous question but for powers of 3.
Another change problem (Euro coins)
A vending machine accepts the euro coins of 10 cents, 20 cents and 50 cents. In how many ways
can I insert coins to the value of 70 cents? Show the answer 26
Throwing 3 dice
Galileo in the 1600's asked why a sum of 10 seemed to appear more often than others when
throwing 3 dice.
I have three ordinary dice with the usual faces 1,2,3,4,5 and 6.
If the three dice had different colours, in how many ways can I throw a total of 10?
27
The position in the sequence gives the "colour" of the dice, so we need to count
Compositions with repetition with exactly 3 parts chosen from 1,2,3,4,5,6
What is the least and most we can throw with 3 dice?
1+1+1=3 up to 6+6+6=18
How many throws (sequences) are possible for the 3 dice ?
6×6×6 = 216
How many of these will have a sum of 10?
27 (Compositions with repetitions from 1..6 with sum 10 and exactly 3 parts )
Is 10 the most likely sum?
No: 10 and 11 are equally likely and the most probable
Compositions with repetition chosen from 1,2,3,4,5,6 with sum from 3 to 18 with exactly 3 parts, total count:
sum
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#
1
3
6
10
15
21
25
27
27
25
21
15
10
6
3
1
Which sum(s) would be most probable if throwing n dice?
The least sum is n 1s = n and the maximum is n 6s = 6n.
The average is 7n/2 which will be the most probable value but,
if n is odd this is not a whole number so both whole numbers either side of this value
(7n/2 ± 1/2) are equally most probable.
Show the answers
Philip Naudé's Problem for Euler
In September 1740, Philip Naudé wrote to Euler asking:
How many ways can the number 50 be written as a sum of 7 different positive integers?
Use the Calculator above to count them. Show the answer 522 partitions (sets, without repetition)
Alcuin's sequence
Make a table of the number of partitions of n that have parts from {2,3,4} that contain a 3.
The partitions (bags) of 7 with repetition are 2,2,3 and 3,4, both of which contain a 3.
Make a table of T(n), the number of non-congruent triangles with distinct integer sides (scalene triangles)
and perimeter n. Non-congruent means we have the same collection of 3 sides just once. We count the triangle with sides 4,6,8 as different
to that with sides 2,3,4 because
though they are the same shape (have exactly the same angles) their side-lengths are different (they are of differing sizes or areas).
There are 5 integer-sided triangles with perimeter 13:
4,4,5; 3,5,5; 1,6,6; 2,5,6; 3,4,6
but only 2 of them are scalene, that is have no side-length repeated: 2,5,6 and 3,4,6
the number of partitions of n-3 with parts from {2,3,4}
which is exactly the same as
the number of partitions of n with parts from {2,3,4} which contain a 3
a(7)=2 and the partitions of 7 containing a 3: 2^{2}3 and 3 4
the partitions of 10 from {2,3,4} that contain a 3: 2^{2}3^{2} and 3^{2}4
the number of triangles with perimeter n
a(7) = 2 and there are 2 with perimeter 7: 2,2,3 and 1,3,3
the number of triangles with distinct sides (scalene triangles)
and perimeter n+6
a(7) = 2 and there are 2 with perimeter 7+6=13: 2,5,6 and 3,4,6
A problem of Henry Ernest Dudeney's
In Dudeney's 536 Puzzles and Curious Problems, problem 467 is about an archery match:
On a target on which the scoring was 40 for the bull's-eye and 39, 24, 23, 17 and 16 respectively
for the rings from the centre outwards, three players had a match with 6 arrows each.
The result was
Miss Dora Talbot, 120 points;
Reggie Watson 110 points;
Mrs Finch 100 points.
Every arrow scored and the bull's eye was only hit once.
From these facts can you determine the exact 6 hits made by each competitor?
Show the answer
For each person it is the collection of scores that is of interest, not the order in which the arrows scored,
so we need to find Partitions (sets/bags).
More than one arrow can land in any ring, so we can have repetition.
The choices are 40, 39, 24, 23, 17 and 16. The number of parts is excatly 6.
There are three problems, for a sum of 120, 110 and 100. Using the Calculator we find that two of them have a unique solution: Reggie Watson's 110: 16,16,16,16,23,23 Mrs Finch's 100: 16,16,17,17,17,17
In neither of these does the bull's-eye score of 40 appear so it must have been hit by an arrow fired by Miss Dora Talbot in her score of 100.
There are 6 solutions with a sum of 100, only one of which contains 40:
Miss Dora Talbot's 120 including a bull's-eye: 16,16,16,16,16,40
Number Bases
Prove (by induction or otherwise) that
1
= (1 + z)(1 + z^{21})(1 + z^{22})(1 + z^{23})...
1 − z
What does this tell us about the number of ways to represent each whole number as a sum of powers of 2? Show the answer
Both expand to 1 + z + z^{2} + z^{3} + z^{4} + ...
The right-hand side coefficient of z^{n} is the number of ways of expressing n as a sum of powers of 2, each used no more than once.
So there is always just one way of expressing n in binary.
Both expand to 1 + z + z^{2} + z^{3} + z^{4} + ...
The right-hand side coefficient of z^{n} is the number of ways of expressing n as a sum of powers of 3, each used 0 1 or 2 times only.
So there is always just one way of expressing n in base 3.
Partition Identities
Show that the number of partitions of n is the same as the number of partitions of 2n into parts of length n.
Take a partition on n. At most it has length n (n 1s).
Pad it out with 0s to make it up to length n.
Increase each of the n parts by 1 to give a partition of n+n=2n of length n with no 0s.
This process is reversible so there are many partitions of 2n of length n as there are partitions of n of we remove any 0 parts.
Show that the number of partitions of n−1 is the same as the number of partitions of n into parts where the
smallest element is 1.
Take any partition on n−1.
Since partitions (multisets) allow repetition, we can add on a 1 at the beginning to give a partion of n whose smallest part is 1.
The process is reversible for each partition of n beginning with 1 so there are an equal number of each.
Show the answers
Applications of Partitions
Partitions as Integer Solutions to Equations
In Mathematics Definitions above we saw that partitions can be expressed as
equations in many variables for which each partition is a solution.
Such an equation where there are several variables to solve for are called Diophantine Equations
after Diophantus (200?-284?)
who wrote about such equations and finding their solutions.
For instance, if we want partitions of 5 where the parts are restricted to a specific set of numbers,
say {1,2,3}, we can write: a_{1} + a_{2} + a_{3} + a_{4} + a_{5} = 5,
a_{i} in {0,1,2,3}, a_{1} ≤ a_{2} ≤ a_{3} ≤ a_{4} ≤ a_{5}
to find sequences of up to 5 numbers from the set {1,2,3}. In allowing some of the a to be 0
we allow for up to 5 parts. If we removed the 0 as a choice, then we have exactly 5 parts.
By removing the inqualities conditions, the order of the parts becomes important as each variable can take any value
and so we have compositions.
An example would be
A farmer is selling vegetables in the market at 7 florins for a bag of potatoes and 5 florins for a bag of carrots.
The farmer remembers a customer spent 70 florins on potatoes and carrots but cannot now remember
how many bags of each they bought. Can you help? How many bags of each did the customer purchase?
If the customer bought p bags of potatoes and c of carrots, then we need to solve
7 p + 5 c = 70 solved in integers.
Have a go and then check your answer:
Show the answer There are 3 solutions:
p=0, c=14 OR p = 5, c = 7 OR p = 10 , c = 0 but the problem states that the customer bought potatoes and carrots, so the only answer
is 5 bags of potatoes and 7 of carrots.
This example is related to Partitions because it is the same as finding a partition (a multiset
with repetition) of 70 with parts 7 and 5 only.
Pythagorean Triangles
Pythagoras' Theorem applies to integer-sided right-angled triangles and states that a^{2} + b^{2} = c^{2} where
a and b are the sides adjacent to the right-angle and c is the hypotenuse.
We are looking for two squares whose sum is a third square number: p(c^{2}|two parts only, part are square numbers).
If we write a number as a sum of a run of consecutive positive numbers we have a runsum.
p( n | parts are consecutive numbers without repetition).
If the consecutive numbers start at 1 then the sum is a triangular number, for example, 1+2+3+4 = 10.
There is a page on runsums on this site.
A Partition identity on runsums
There are two remarkable connections between the number partitions which are runsums (a set of distinct parts):
# partitions (sets) of n which are runsums
= # odd divisors of n
For example 15 = 7+8 = 4+5+6 = 1+2+3+4+5 so 15 has 4 (set) partitions.
The divisors of 15 are 1,3,5 and 15 all of which happen to be odd, so there are also 4
# partitions (sets) of n which are a runsum of odd length
=
# odd divisors of n which are less than √2 n
For example 50 = 8+9+10+11+12 = 11+12+13+14 and there are 2 of odd length
(the first and last).
The divisors of 50 are 1,2,5,10,50 of which the odd ones are 1,5,50.
and there are 2 of these (1 and 5) that are less than √100 = 10.
# partitions (sets) of n which are a runsum of even length
=
# odd divisors of n which are bigger than √2 n
Using 50 as an example again, there is only 1 runsum partition of even length (11+12+13+14)
and only one odd divisor that is bigger than √100 = 10, namely 50.
Partitions into Consecutive Parts M D Hirschhorn, P M Hirschhorn,
Mathematics Magazine 78 (2005) pages 396-397
gives a proof of these referring back to a more general theorem of Sylvester:
A Constructive Theory of Partitions, arranged in three acts, an interact and an exodion
J J Sylvester Amer. J Maths (1882) pages 251-320
Polygonal or Figurate Numbers
If triangular numbers are the sum of consecutive integers starting at 1, then squares are the sum of consecutive odd integers
starting at 1: 1 + 3 + 5 = 9 = 3^{2}. Other shapes are also the sum of numbers in other simple arithmetic series.
The details and much more are on this page .
Number bases
When we write a number in base 10 or any other base, we are finding a collection of powers of the base which sum to the value.
Each power can be absent or repeated a number of times, up to one less than the base.
p( n | parts are powers of base, with repetition, parts chosen from 0..(base-1) )
Fibonacci Numbers
If we make a line of squares and dominoes (of lengths 1 and 2) allowing repetitions and
noting all the different orders of the squares and dominoes, then the number of
ways to make a line of length n (sequence with repetition allowed) is as follows:
n
compositions:
sequences with repetition
#
1
1
1
2
1+1, 2
2
3
1+1+1, 1+2, 2+1
3
4
1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2
5
Can you see why the counts will always be the Fibonacci Numbers?
Show why
Consider how we might find all the compositions for 5 using the table above.
EITHER the composition begins with 1
in which case the rest of it is any composition of 4;
OR the composition begins with 2
in which case the rest of it is any composition of 3
These are the only two cases and all compositions of 5 fall into exactly one of these cases.
So the number of compositions of 5 is
the number of compositions of 4 (with a 1 in front of each) plus the number of compositions
of 3 9with a 2 in front of each).
This applies to any number n: the number of compositions is the sum of the number of compositions
of n-1 and of n-2.
Since the number of compositions of 1 is 1 and of 2 is 2 then we have the same starting values as in
the Fibonacci series (0,1), 1,2,3,5,8,13,21,...
Fibonacci again!
Cauchy in 1876 (see Dickson, Volume II, page 130) mentions another way in which the number of compositions are the Fibonacci numbers.
If we do not count any composition which contains the part 1, so that the parts are chosen from 2,3,4,... then the number of compositions on n
(sequences, repetition allowed) is a Fibonacci number:
n
Compositions
#
2
2
1
3
3
1
4
4; 2,2
2
5
5; 2,3; 3,2
3
6
6; 2,4; 3,3; 4,2; 2,2,2
5
Can you prove why this is so? Show a hint
If c(n) counts the number of compositions of n using 2,3,4,... with repetition allowed then
we need to prove that
c(2)=1, c(3)=1 and c(n)=c(n-1) + c(n-2) for n>3.
Show a proof
If n>3, then any composition (a sequence where the order matters) ends with 2 or ends with a number bigger than 2.
We can take any of the valid compositions of n-1 and increase the final number by 1 so that these will end with a number 3 or more and the new sum will be n.
We can also take any valid compositions of n-2 and append a 2 as an extra part at the end again making the new sum n.
Clearly these actions cannot give the same composition and each gives a composition of n, and all compositions of n must be
in one of these two categories (end with a number 3 or bigger or else end with 2).
So c(n) is c(n-1) + c(n-2).
Formulas for the Number of Partitions and Compositions
Here are recursive formulas for the 4 types of partition/composition that are used in the Calculators
on this page. Both n and k are positive non-zero whole numbers otherwise the result is 0.
The total number of partitions of each kind is the sum for k from 1 to n.
We can have a set, multiset (bag) or sequence abbreviated to set, bag, seq. Also we can
allow repetition rep or, once used, remove an item from later choices making the choices distinct
(rem).
The recursion equations are used in turn, the first to match giving the result of the function.
In all cases we have (with f being the function computing the number of collections with sum n and k parts):
there cannot be more parts k than the sum n. So if n<k then the result is 0: f(n,k) = 0 if n<k
There must be at least 1 part so k≥1 otherwise the result is 0: f(n,k) = 0 if k<1
a collection (set, bag or sequence) of size k=1 with sum n is always possible and the collection is unique: f(n,1) = 1
Partitions (multisets/bags with repetition)
pbagrep(n, k), the number of multisets of k positive numbers with sum n is
pbagrep(n, k) = 0 if n<k or k<1
pbagrep(n, 1) = 1
pbagrep(n, k) = pbagrep(n−1, k−1) + pbagrep(n−k, k)
Let the bag be represented as a list of numbers in non-decreasing order (because repetitions are allowed).
A bag (list) of size k and sum n either
begins with 1
so the rest of the bag is any solution for a bag with sum n-1 and length k-1
or begins with a number > 1
so we can find it by increasing every part by 1 in any bag with the sum n-k and k parts
Both of these maintain the invariant that each list is a non-decreasing sequence
Partitions (sets, distinct numbers)
psetrem(n, k) counts the number of sets of k (distinct) numbers whose sum is n
psetrem(n, k) = 0 if n<k or k<1
psetrem(n, 1) = 1
psetrem(n, k) = psetrem(n−k, k−1) + psetrem(n−k, k)
The total can be found by summing for k from 1 up to
floor(
√8n+1 - 1
)
2
Let the set be represented as a list of (distinct) numbers in increasing order.
A set (list) with sum n consisting of k members (parts) is
Compositions (sequences) with repetition
pseqrep(n, k) counts the number of sequences of k positive integers (with repetition allowed) whose sum is n
pseqrep(n, k) = 0 if n<k or k<1
pseqrep(n, 1) = 1
pseqrep(n, k) = pseqrep(n−1, k−1) + pseqrep(n−1, k)
This is just the recurrence for the Binomial numbers so that a direct formula is
pseqrep(n, k) = Binomial(n−1, k−1) =
(n−1)!
(k−1)! (n−k)!
The total number of compositions of n (with repetition allowed) is 2^{n-1}
The first item is 1 or something bigger than 1.
If it is a 1, remove it to get a seqrep of n-1 of length k-1.
If it is greater than 1, then it is a seqrep of n-1 of length k but the first part has been increased by 1
Compositions (sequences) without repetition
pseqrem(n, k) counts the number of sequences of k distinct positive numbers whose sum is n
pseqrem(n, k) = 0 if n<k or k<1
pseqrem(n, 1) = 1
pseqrem(n, k) = pseqrem(n−k, k) + k pseqrem(n−k, k−1)
Partitions and Composition Connections
A remarkable connection between partitions (bags) of n and "the sum of the divisors of n"
Show p plot to n=20:
Show p plot to n=50:
Show sigma plot to n= 200:
Show sigma plot to n=1000:
If p(n) denotes the total number of multisets (bags) with sum n, Euler also found that
The recurrence involving the General Pentagonal Numbers has another surprise, again found by Euler.
Let's introduce the sum of all the divisors of a number n which is often denoted
using the greek small letter σ.
For example: σ(10) = the sum of the divisors of 10 =
1 + 2 + 5 + 10 = 18
Since the divisors include 1 and the number itself, σ(n) is always n+1 for the prime numbers
and only for the prime numbers.
Yet Euler found that the recurrence relation for partition bags that involves the General
Pentagonal Numbers is also exactly the same recurrence as for
σ(n), except for the value of σ(0)
which is the number itself whereas p(0) is 1 for partition bags.
This is remarkable and unexpected because
the function p(n) smoothly increases as n increases whereas σ(n)
varies up and down from one number to the next
as shown in the graph on the right.
The maximal values of n are those for which sigma(n) exceeds sigma(k) for all smaller values of k (k<n).
They are
n = 1, 2, 3, 4, 6, 8, 10, 12, 16, 18, 20, 24, 30, ... A002093.
The minimal numbers for sigma are the primes since sigma(n) is always at least 1 + n
for divisors 1 and n
and equals this minumum only for the prime numbers n.
Our discussion is over, but we sense that the mystery is only partially revealed.
How can the problem of expressing a number as a sum, be at all related to expressing that same number as a product?
Euler was astonished at these results
Integer Partitions G E Andrews, K Eriksson
(Cambridge 2010 edition) is an excellent little paperback with many examples of Partition Identities and proofs.
Theory of Partitions
G E Andrews, (Cambridge Uni press, 1998 paperback edition)
This is now the classic text on Partitions and well worth getting if you are interested in Partitions, though much
of the maths is at degree level.
It was first published in 1984 but the 1998 paperback version includes recent results up to that date.
How Euler Did It
by C E Sandifer, (Math Assoc of America, 2007)
Chapter 14 is on Philipe Naudé's problem and on the GF for the number of partitions of n of length k.
The book is well worth reading to see how Euler's developed so
many important results in so many areas of mathematics.
A Note on Partitions and Triangles With Integer Sides G E Andrews,
Amer Math Monthly vol 86 (1979) pages 477-478.
This proves a slightly different formulation for T(n)
that we met in the Alcuin's sequence problem above, namely that
floor(n/2)
T(n) = p_{3}(n) −
Σ
p_{2}(j)
j = 1
where p_{k}(n) is the number of partitions of n into k parts floor(x) is the nearest integer
less than x if x is not a whole number otherwise it is x itself.
and another remarkably simple equation which does not use the number of partitions:
T(n) = round( ^{n2}/_{12} ) − floor(^{n}/_{4}) floor(^{(n+2)}/_{4})
where round(x) is the integer nearest to x.
History of the Theory of Numbers:
Vol II Diophantine Analysis by L E Dickson
is a classic and monumental reference work on all aspects of the History and development
of Number Theory, in 3 volumes (Vol 1 Divisibility and Primality and
volume III on Quadratic and Higher Forms).
The original edition was 1920 but Dover reprinted it in 2005 with no changes.
Nothing since 1920 is covered in the book but
it is still a comprehensive summary of useful, fundamental results and a
historical survey of references to the famous and not-so-famous mathematicians who have developed
the area of mathematics we now call Number Theory.
The link above is to a new cheap Dover paperback edition (2005) of Volume II where chapter 3 is on
Partitions from Euler to MacMahon.
Surprising Connections between Partitions and Divisors
T J Osler, A Hassen, T R Chandrupatla
The College Mathematics Journal 38 (Sep 2007), pages 278-287
JSTOR pdf
Explains and proves the recursion equation that Euler discovered for both the partition (bags) and the
sum of the divisors of a number are the same apart from the base cases.