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

### Partitions of Set {1,2,3, ...n}

```
Date: 7/25/96 at 15:35:28
From: Scott Turner
Subject: Partitions of Set {1, 2, 3, ...n}

I'm trying to count the partitions of the set {1, 2, 3, ... n}.  Is
there a generic way to do this, or some formula?

Thanks.

ST
```

```
Date: 7/25/96 at 19:33:23
From: Doctor Anthony
Subject: Re: Partitions of Set {1, 2, 3, ...n}

There are a variety of formulae, tables and recurrence relationships
that are used in evaluating the number of partitions of a number 'n'.
The notation used is:

P(n,p,q) = number of partitions of n into p parts,the greatest of
which is q.

P(n,p,*)= number of p-partitions of n.

P(n,<= p,*) = number of partitions of n into p parts or any smaller
number of parts.

Q(n,*,<=q) = number of partitions of n into unequal parts, none of
which exceeds q.

The table for P(n,p,*) will be found in many textbooks, and is
constructed using the recurrence relationship:

P(n,p,*) = P(n-1,p-1,*) + P(n-p,p,*)

Euler used series to enumerate partitions, thus

Q(n,*,<=q) is the coefficient of x^n in the expansion of
(1+x)(1+x^2)(1+x^3).....(1+x^n)

P(n,*,<=q) is the coefficient of x^n in the expansion of
(1-x)^(-1)*(1-x^2)^(-1)*......(1-x^q)^(-1)
= (1+x+x^2+...)(1+x^2+x^4+...)...(1+x^q+x^2q+...)

Q(n,p,<=q) is the coefficient of of z^p*x^n in the expansion of
(1+zx)(1+zx^2)(1+zx^3).....(1+zx^q)

As you see the algebra can be very heavy, and in practice, tables or
computer printouts from a recurrence relationship would be used.

-Doctor Anthony,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations

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