Number of Unordered Partitions

Date: 08/18/99 at 03:40:29
From: Nicolae Bonciocat
Subject: Formula for the unordered partitions of n

Dear Professor,

I kindly ask you to inform me if there is any known formula for the 
number of unordered partitions of a positive integer p(n).

Many thanks,
Nicolae Bonciocat

Date: 08/18/99 at 07:40:12
From: Doctor Anthony
Subject: Re: Formula for the unordered partitions of n

The generating function for the number of partitions of a number n is 
the coefficient of x^n in the expansion of

                        1
        -----------------------------
        (1-x)(1-x^2)(1-x^3)(1-x^4)... 

     = (1-x)^(-1) * (1-x^2)^(-1) * (1-x^3)^(-1) * ...

     = [1+x+x^2+x^3...]*[1+x^2+x^4+x^6+...]*[1+x^3+x^6+x^9+...]*...

Clearly this infinite product need not be continued beyond terms x^n.

This generating function is not of much practical use unless you have 
a mathematics package like Mathcad or Mathematica to handle the heavy 
algebra. Fortunately there is a recursion formula which can be used 
without the heavy algebra.

The recursion formula for p(n), the TOTAL number of partitions of n is 
given by:

     p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15)
            - p(n-22) - ...

Note that the signs follow the pattern  ++ -- ++ -- ++ -- and so on.

The numbers 1, 2, 5, 7, 12, 15, 22, 26, ... inside the brackets are 
of the form  (m/2)(3m-1) and (m/2)(3m+1)

It is useful to have a table showing how these values go.

          m        1     2     3     4     5     6     7     8
     ---------------------------------------------------------
     (m/2)(3m-1)   1     5    12    22    35    51    70    92       
     (m/2)(3m+1)   2     7    15    26    40    57    77   100

Take p(0) = 1 and p(1) = 1

     p(2) = p(1) + p(0) = 2
     p(3) = p(2) + p(1) = 3
     p(4) = p(3) + p(2) = 5
     p(5) = p(4) + p(3) - p(0) = 3+5-1 = 7
     p(6) = p(5) + p(4) - p(1) = 7+5-1 = 11  
     p(7) = p(6) + p(5) - p(2) - p(0) = 11+7-2-1  = 15
     p(8) = p(7) + p(6) - p(3) - p(1) = 15+11-3-1 = 22

and so on.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/