Additive and Multiplicative Partitions
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