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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/