Drexel dragonThe Math ForumDonate to 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?

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

[Privacy Policy] [Terms of Use]

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

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/