Computing the Partitions of n

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

Hardy and Ramanujan did a lot of work with partitions 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.

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 Cyclical Partition Sequences.

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