The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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?



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 

P(n,*,<=q) is the coefficient of x^n in the expansion of
        = (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 

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!   
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.