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