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