Computing the Partitions of n
Let p(n) denote the number of ways in which a positive integer n can
be expressed as a sum of positive integers, without regard to order.
There are quite a few ways of determining the number of partitions
p(n) of a given integer n. Euler gave the well-known generating
function for p(n) (see Additive and Multiplicative Partitions), but
there are many other interesting ways of characterizing and computing
the values of p(n). For example, we have the following formula
involving the sum-of-divisors function
1 n
p(n) = - SUM s(k) p(n-k)
n k=1
with the understanding that p(0)=1. Here s(k) denotes the sum
of the divisors of k. If k has the prime factorization
(p1^a1)(p2^a2)...(pt^at) then the sum of the divisors of k is
t pj^(aj+1) - 1
s(k) = PROD ---------------
j=1 pj - 1
One of the easiest ways of computing the sequence p(n) is recursively
using the formula
p(n) = SUM (-1)^(k-1) p(n - k(3k+-1)/2)
where the sum is evaluated over all k such that k(3k+-1)/2 is in the
range from 1 to n.
More generally, given any set C of distinct integers (such as {2,3}
or the set of primes, or the set of squares, etc.) there are fairly
efficient algorithms for computing the number of ways in which n
can be expressed as a sum of elements of C, allowing multiplicities
but without regard to order. Let c_1,c_2,c_3,... denote the elements
of C in increasing order and set c_0 = 0 to represent the null element.
Then for every pair of integers i,j we define the function f(i,j)
with the assignments
f(0,0) = 1
f(i,j) = 0 if either i or j is less than or equal to zero
(but not both zero)
and the recursive relation
j
f(i,j) = SUM f(i - c_j, k)
k=0
for all i,j > 0. Then the number of ways in which an integer n
can be expressed as the sum of elements of C is given by
n
v(n) = SUM f(n,k)
k=1
Interestingly, there exist "dual" sets of integers such that the
nth element of one is the number of partitions of n into elements
of the other, and vice versa. See Partition Transform Cycles.
By the way, Euler's generating function
1
--------------------- = 1 + p(1) x + p(2) x^2 + p(3) x^3 + ...
(1-x)(1-x^2)(1-x^3)...
can immediately be generalized to cover partitions into arbitrary
sets of integers. We simply place a factor of (1 - x^s) in the
denominator for each allowable summand s. For example, the generating
function for the partitions of n into primes is
1
---------------------------------------
(1-x^2)(1-x^3)(1-x^5)(1-x^7)(1-x^11)...
= 1 + 0x + 1x^2 + 1x^3 + 1x^4 + 2x^5 + 2x^6 + 3x^7 + ...
For another example, suppose we wish to determine the number of distinct
ways of making change for a dollar in terms of the available coins. This
is the same as asking for the number of partitions of 100 into sums of
elements of the set 1, 5, 10, 25, 50, and 100 (representing the penny,
nickel, dime, quarter, fifty-cent piece, and silver dollar, respectively).
The basic generating function is
1
-----------------------------------------------
(1-x^1)(1-x^5)(1-x^10)(1-x^25)(1-x^50)(1-x^100)
= 1 + 1x + 1x^2 + 1x^3 + 1x^4 + 2x^5 + 2x^6 + 2x^7 + ...
The coefficient of x^100 in this expansion is 293, which is the desired
result. However, this isn't a very practical way of computing the answer.
One way of simplifying the calculation is to set aside the pennies, since
they can complete any sum, and just consider the number of ways of
expressing numbers less than or equal to 100 as a sum of the numbers
5, 10, 25, 50, and 100. Each of these expressions corresponds to a unique
way of expressing the number 100 when augmented with the required number
of pennies. Furthermore, we can divide all the numbers in our simplified
problem by 5, so we are seeking the number of ways of expressing 20 or
less in terms of the numbers 1, 2, 5, 10, 20. The generating function for
sums of these numbers is
1
-------------------------------------
(1-x^1)(1-x^2)(1-x^5)(1-x^10)(1-x^20)
= 1 + 1x + 2x^2 + 2x^3 + 3x^4 + 4x^5 + 5x^6 + 6x^7 + 7x^8
+ 8x^9 + 11x^10 + 12x^11 + 15x^12 + 16x^13 + 19x^14
+ 22x^15 + 25x^16 + 28x^17 + 31x^18 + 34x^19 + 41x^20 + ...
so the number of ways of expressing 20 or less is the sum of the
coefficients up to x^20, i.e.,
1 + 1 + 2 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 11
+ 12 + 15 + 16 + 19 + 22 + 25 + 28 + 31 + 34 + 41 = 293
These coefficients can be determined using the f array for sums of the set
{1,2,5,10,20} as described previously. This gives the easily-tabulated array
shown below:
0 1 2 3 4 5 sum
0 1 0 0 0 0 0 1
1 0 1 0 0 0 0 1
2 0 1 1 0 0 0 2
3 0 1 1 0 0 0 2
4 0 1 2 0 0 0 3
5 0 1 2 1 0 0 4
6 0 1 3 1 0 0 5
7 0 1 3 2 0 0 6
8 0 1 4 2 0 0 7
9 0 1 4 3 0 0 8
10 0 1 5 4 1 0 11
11 0 1 5 5 1 0 12
12 0 1 6 6 2 0 15
13 0 1 6 7 2 0 16
14 0 1 7 8 3 0 19
15 0 1 7 10 4 0 22
16 0 1 8 11 5 0 25
17 0 1 8 13 6 0 28
18 0 1 9 14 7 0 31
19 0 1 9 16 8 0 34
20 0 1 10 18 11 1 41
---
Total = 293
Taking a more sophisticated analytical approach, Hardy and Ramanujan studied
the partition function extensively around 1918, and found that the log of p(n)
is asymptotic to PI sqrt(2n/3), which led to the approximate formula
e^(PI sqrt(2n/3))
p(n) ~ -----------------
4n sqrt(3)
Subsequently, their celebrated "circle method" was used to obtain the
formula
1 d / e^(PI sqrt(2n/3 - 1/36)) \
p(n) = ----------- --( ------------------------- ) + O(e^(k sqrt(n))
2PI sqrt(2) dn \ sqrt(n - 1/24) /
where k < PI/6. Further refinements led to a formula (with correction terms)
that gives p(200) to within 0.004 of the actual value 3972999029388. Later still,
Rademacher made more improvements along these lines and was able to give an exact
series expansion for p(n). That formula is given in Abramowitz and Stegun's
"Handbook of Mathematical Functions", but it's quite complicated and not especially
useful for actual computations.
Return to MathPages Main Menu