Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Discrete Mathematics
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search