The number of partitions of n is the number of ways to express n as a sum of positive integers, where the order of the addends doesn't matter.

Recurrence relation

p(n) =  p(n-1) + p(n-2)    (m = 1)
       -p(n-5) - p(n-7)    (m = 2)
       +p(n-12) + p(n-15)  (m = 3)
       - . . .
       -(-1)^m p(n-m(3m-1)/2) - (-1)^m p(n-m(3m+1)/2)  (m ≥ 1)

For example: p(12)= p(11) + p(10) - p(7) - p(5) + p(0)
                  =  56   +  42   -  15  -  7   +  1   = 77

 . . . . . .

Internet references

Partitioning Integers, from Bob's Positive Integer Pages (fascinating reading!)

Mathworld: Partition and the Partition Function, P

Related pages in this website

Partition recurrence relation: part(n,k) = part(n-1,k-1) + part(n-k,k)

The webmaster and author of this Math Help site is Graeme McRae.