```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.
```