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/