For any positive integer n let A(n) denote the number of distinct ways in which n can be expressed as a sum of positive integers, without regard to the ordering of the terms. Thus the function A(n) signifies the number of distinct additive partitions of n. We can also define a(n) the same as A(n) except that distinct orderings of the terms are counted as distinct partitions. To illustrate, with n=5 we have the following seven partitions 5 4+1 3+2 3+1+1 2+2+1 2+1+1+1 1+1+1+1+1 so A(5) = 7. On the other hand, if we take the ordering of the terms into account, we see that the expression "5" still contributes just one partition, but each of the expressions "4+1" and "3+2" contribute two partitions, because we can reverse the order of the summands. Likewise each of the expressions "3+1+1" and "2+2+1" have three distinct permutations, the expression "2+1+1+1" has four, and the expression "1+1+1+1+1" has only one. Thus the total number of additive partitions of 5, taking order into account, is a(5) = 1 + 2 + 2 + 3 + 3 + 4 + 1 = 16 In general we can see that a(n) = 2^(n-1), because if we place n objects in a line the number of additive partitions is just the number of ways that we can place "walls" in the n-1 gaps between the objects. Therefore, this function is quite simple to compute. However, the function A(n) is not quite so trivial. Goldbach once wrote to Euler asking him to characterize the values of A(n) for any integer n. In his usual creative fashion, Euler originated the method of "generating functions" to provide an answer. He considered the infinite product (1 + x + x^2 + ...)(1 + x^2 + x^4 + ...)(1 + x^3 + x^6 + ...)... If we expand this product we see that the coefficient of x^n is the number of ways in which n can be expressed as a sum of one number from each of the sets {0,1,2,...}, {0,2,4,...}, {0,3,6,...}, and so on. This equals A(n), because each of these sums uniquely corresponds to a distinct sum of a certain number of 1's, a certain number of 2's, a certain number of 3's, and so on. Thus these sums represent all the partitions of n, so the coefficient of x^n in the expanded product is precisely A(n). Euler remembered that, as Euclid showed, the geometric series can be expressed formally as 1 1 + x + x^2 + x^3 + x^4 + ... = ------- 1 - x and likewise the infinite sum 1 + x^2 + x^4 + ... can be expressed as 1/(1 - x^2), and so on. Thus we have / 1 \ / 1 \ / 1 \ ( ----- )( ------- )( ------- )... = A(0) + A(1)x + A(2)x^2 + ... \1 - x/ \1 - x^2/ \1 - x^3/ It's also worth noting that if we include just the first k factors on the left hand side, then the coefficient of n is the number of partitions of n into k or fewer parts. We will call this A_k(n). Euler's generating function for the partitions of n is certainly clever, and leads to many powerful techniques in combinatorics, but it isn't the easiest way to compute A(n) or A_k(n). Some other ways are discussed in Computing the Partitions of n, but here we will just mention one very elementary methods. A table of A_k(n) can be constructed quite simply based on the following two observations: (1) The number of partitions into k or fewer parts is equal to the number of partitions into exactly k parts plus the number of partitions into k-1 or fewer parts. (2) Given a partition of n into exactly k parts, we can subtract 1 from each part, leaving a partition of n-k in k or fewer parts. Thus there is a one-to-one correspondence between the partitions of n into exactly k parts and the partitions of n-k into k or fewer parts. Putting these two facts together, we have the simple recurrence relation A_k(n) = A_{k-1}(n) + A_k(n-k) with which we can easily generate a table such as shown below. k n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 3 1 2 3 3 3 3 3 3 3 3 3 3 3 3 4 1 3 4 5 5 5 5 5 5 5 5 5 5 5 5 1 3 5 6 7 7 7 7 7 7 7 7 7 7 6 1 4 7 9 10 11 11 11 11 11 11 11 11 11 7 1 4 8 11 13 14 15 15 15 15 15 15 15 15 8 1 5 10 15 18 20 21 22 22 22 22 22 22 22 9 1 5 12 18 23 26 28 29 30 30 30 30 30 30 10 1 6 14 23 30 35 38 40 41 42 42 42 42 42 11 1 6 16 27 37 44 49 52 54 55 56 56 56 56 12 1 7 19 34 47 58 65 70 73 75 76 77 77 77 13 1 7 21 39 57 71 82 89 94 97 99 100 101 101 14 1 8 24 47 70 90 105 116 123 128 131 133 134 135 The total number of partitions A(n) is obviously just A_n(n) from this table, so we have the sequence of values for A(n) for n=1,2,... n = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... A(n) = 1 2 3 5 7 11 15 22 30 42 56 77 101 135 ... The above discussion focused on additive partitions, but we can also consider multiplicative partitions, i.e., the number of ways in which a positive integer n can be expressed as a product of integers (each greater than 1). Let M(n) denote the number of multiplicative partitions if the ordering of the factors is NOT taken into account, and let m(n) denote the number of multiplicative partitions of n if the ordering IS taken into account. Neither of these functions of entirely trivial. Clearly the number of multiplicative partitions of the integer n = (p1^a1)(p2^a2)...(pk^ak) depends only on the non-zero exponents a1,a2,..,ak. Therefore, it's more appropriate to write m(n) as m(a1,a2,..,ak). These numbers can most efficiently be generated by means of recurrence relations, similar to those that generate the binomial coefficients. In general, m(a1,a2,..,ak) is the sum of all the m(b1,b2,..,bk) for bj ranging from 0 to aj, excluding the single cell with bj=aj for j=1,2,..,k. Consequently, the values of M can be generated by a recurrence based on the surrounding values using inclusion-exclusion. For example, in the trivial case k=1 we have m(a1) = 2 [ m(a1-1) ] with the initial value F(0) = 1/2. This generates the sequence of values a1 0 1 2 3 4 5 6 m(a1) = (1/2) 1 2 4 8 16 32 ... Likewise with k=2 we have the recurrence m(a1,a2) = 2 [ m(a1-1,a2) + m(a1,a2-1) - m(a1-1,a2-1) ] and we can take the initial value m(0,0)=1/2 to generate all subsequent slices (although this assignment messes up the sum of the rectangles discussed below.) This generates the symmetrical array a2 0 1 2 3 4 5 6 0 (1) 1 2 4 8 16 32 1 1 3 8 20 48 112 2 2 8 26 76 208 a1 3 4 20 76 252 4 8 48 208 5 16 112 6 32 Notice that each cell in this table is the corner of a rectangle of which the opposite corner is the (0,0) cell, and the number in the cell equals the sum of all the other entries in that rectangle. This enables us to determine the recurrence formula noted above. Thus to find m(2,2) we simply compute m(2,2) = 2[8+8-3] = 26. Likewise to find m(2,3) we just compute m(2,3) = 2[26+20-8] = 76. (By the way, note that it's helpful to set m(0,0) = 1/2 instead of 1 to be consistent with the recurrence formulas.) With k=3 we consider a three-dimensional array of numbers, and each value of M is the sum of all the other values inside the rectangular box containing the origin. This leads to the recurrence formula m(a1,a2,a3) = 2 [ m(a1-1,a2,a3) + m(a1,a2-1,a3) + m(a1,a2,a3-1) - m(a1-1,a2-1,a3) - m(a1-1,a2,a3-1) - m(a1,a2-1,a3-1) + m(a1-1,a2-1,a3-1) ] again setting the initial value m(0,0,0) = 1/2 to simplify the initial conditions. For k=3 the a3=0 plane is identical to the k=2 array shown above, (as are the a1=0 and a2=0 planes, by symmetry). Then the a3=1 plane is 1 3 8 20 48 112 .... 3 13 44 132 368 8 44 176 604 20 132 604 48 368 112 In general, we have a recurrence for m(a1,a2,..,ak) as an inclusion- exclusion sum of 2^k - 1 terms. Of course, we don't really need to save the whole array, because of all the symmetry. To cover numbers whose sum of exponents in their prime factorizations are s = a1 + a2 + ... + ak we need only give A(s) numbers, where A(s) is the number of additive partitions of s. So we can make a little table of the non-zero exponents, without regard to order s a1 a2 a3 a4 a5 a6 a7 m(a1,a2,..) --- -- -- -- -- -- -- -- ----------- 1 1 1 2 2 2 2 1 1 3 3 3 4 3 2 1 8 3 1 1 1 13 4 4 8 4 3 1 20 4 2 2 26 4 2 1 1 44 4 1 1 1 1 75 5 5 16 5 4 1 48 5 3 2 76 5 3 1 1 132 5 2 2 1 176 5 2 1 1 1 308 5 1 1 1 1 1 541 6 6 32 6 5 1 112 6 4 2 208 6 3 3 252 6 4 1 1 368 6 3 2 1 604 6 2 2 2 818 6 3 1 1 1 1076 6 2 2 1 1 1460 6 2 1 1 1 1 2612 6 1 1 1 1 1 1 4683 7 7 64 7 6 1 256 7 5 2 544 7 4 3 768 7 5 1 1 976 7 4 2 1 1888 7 3 3 1 2316 7 3 2 2 3172 7 4 1 1 1 3408 7 3 2 1 1 5740 7 3 1 1 1 1 10404 = (102)^2 7 2 2 2 1 7880 7 2 2 1 1 1 14300 7 2 1 1 1 1 1 25988 7 1 1 1 1 1 1 1 47293 This covers any number whose sum of exponents is 7 or less, and this table can easily be extended indefinitely. For example that to determine m(2,1,1,1) in the above table, we proceed like this m(2,1,1,1) = 2[ m(1,1,1,1) + 3m(2,1,1) - 3m(1,1,1) - 3m(2,1) + m(2) + 3m(1,1) - m(1) ] = 308 Likewise to compute m(1,1,1,1,1) we proceed like this m(1,1,1,1,1) = 2[ 5m(1,1,1,1) - 10m(1,1,1) + 10m(1,1) - 5m(1) + m(0) ] = 541 If we neglect the ordering of factors, then M(a1,a2,..) represents the number of multiplicative partitions of n = p1^a1 p2^a2.. pk a^k. Again we can define M_d(a1,a2,...) as the number of partitions into d or fewer factors. Some of these values are obvious. For example, we clearly have M_d(p^k) = A_d(k) At the other extreme, if p1,p2,...,pk are all distinct primes, then k! M(1,1,...,1) = SUM --------------------------------------- (1!)^c1 c1! (2!)^c2 c2! ... (k!)^ck ck! where the summation is taken over all sets of non-negative integers ci such that c1 + 2 c2 + 3 c3 + ... + k ck = k For more general sets of exponents, the multiplicative partitions are as tabulated below for s ranging from 1 to 8. ai M_d - M_{d-1} i =1 2 3 4 5 6 7 8 d = 1 2 3 4 5 6 7 8 M(a1,a2,..) - - - - - - - - -- -- -- -- -- -- -- -- ---------- 1 1 1 1 2 2 1 1 2 1 1 1 1 2 3 3 1 1 1 3 2 1 1 2 1 4 1 1 1 1 3 1 5 4 4 1 2 1 1 5 3 1 1 3 2 1 7 2 2 1 4 3 1 9 2 1 1 1 5 4 1 11 1 1 1 1 1 7 6 1 15 5 5 1 2 2 1 1 7 4 1 1 4 4 2 1 12 3 2 1 5 6 3 1 16 3 1 1 1 7 8 4 1 21 2 2 1 1 8 11 5 1 26 2 1 1 1 1 11 16 7 1 36 1 1 1 1 1 1 15 25 10 1 52 6 6 1 3 3 2 1 1 11 5 1 1 5 6 4 2 1 19 4 2 1 7 10 7 3 1 29 3 3 1 7 11 8 3 1 31 4 1 1 1 9 14 9 4 1 38 3 2 1 1 11 20 14 5 1 52 2 2 2 1 13 26 19 6 1 66 3 1 1 1 1 15 30 20 7 1 74 2 2 1 1 1 17 38 27 8 1 92 2 1 1 1 1 1 23 58 41 11 1 135 1 1 1 1 1 1 1 31 90 65 15 1 203 7 7 1 3 4 3 2 1 1 15 6 1 1 6 9 7 4 2 1 30 5 2 1 8 15 12 7 3 1 47 4 3 1 9 18 16 9 3 1 57 5 1 1 1 11 21 17 9 4 1 64 4 2 1 1 14 33 29 15 5 1 98 3 3 1 1 15 36 34 17 5 1 109 3 2 2 1 17 46 44 22 6 1 137 4 1 1 1 1 19 49 43 21 7 1 141 3 2 1 1 1 23 68 66 31 8 1 198 2 2 2 1 1 26 85 87 40 9 1 249 3 1 1 1 1 1 31 104 102 46 11 1 296 2 2 1 1 1 1 35 128 135 59 12 1 371 2 1 1 1 1 1 1 47 196 215 90 16 1 566 1 1 1 1 1 1 1 1 63 301 350 140 21 1 877 8 8 1 4 5 5 3 2 1 1 22 7 1 1 7 12 11 7 4 2 1 45 6 2 1 10 21 21 13 7 3 1 77 5 3 1 11 26 28 18 9 3 1 97 4 4 1 12 29 32 21 10 3 1 109 6 1 1 1 13 30 29 18 9 4 1 105 5 2 1 1 17 48 52 32 15 5 1 171 4 3 1 1 19 58 67 43 18 5 1 212 4 2 2 1 22 73 88 55 23 6 1 269 3 3 2 1 23 80 100 64 25 6 1 300 5 1 1 1 1 23 72 78 47 21 7 1 250 4 2 1 1 1 29 108 132 81 32 8 1 392 3 3 1 1 1 31 120 152 96 35 8 1 444 3 2 2 1 1 35 148 198 124 44 9 1 560 2 2 2 2 1 40 183 259 163 55 10 1 712 4 1 1 1 1 1 39 164 206 123 47 11 1 592 3 2 1 1 1 1 47 224 310 191 64 12 1 850 2 2 2 1 1 1 53 274 403 251 79 13 1 1075 3 1 1 1 1 1 1 63 342 496 300 96 16 1 1315 2 2 1 1 1 1 1 71 416 643 397 117 17 1 1663 2 1 1 1 1 1 1 1 95 634 1041 640 176 22 1 2610 1 1 1 1 1 1 1 1 1 127 966 1701 1050 266 28 1 4140 For an interesting application of both the additive and multiplicative partition functions, see Polyomino Enumerations. Incidentally, if we run the recurrence for m(a1,a2) in reverse to determine the coefficients of progressively earlier cells, we find the sequence 2 2 -2 4 8 -8 4 -8 4 8 24 -24 24 -48 24 8 -24 24 -8 16 64 -64 96 -192 96 64 -192 192 -64 16 -64 96 -64 16 32 160 -160 320 -640 320 320 -960 960 -320 160 -640 960 -640 160 32 -160 320 -320 160 -32 Each row, column, and hypotenuse of each of these arrays is proportional to a row of Pascal's triangle.

Return to MathPages Main Menu