

A partition is a way of writing an integer
n as a sum of positive
integers where the order of the addends is not
significant, possibly subject to one or more additional constraints.
By convention, partitions are normally written from largest to
smallest addends (Skiena
1990, p. 51), for example, .
All the partitions of a given positive integer n can be
generated using Partitions[n]
in the Mathematica
addon package DiscreteMath`Combinatorica` (which can be
loaded with the command <<DiscreteMath`), or the
undocumented Mathematica
command
DiscreteMath`IntegerPartitions`IntegerPartitions[n].
PartitionsQ[p]
can be used to test if a list consists of positive integers and
therefore is a valid partition.
Andrews (1998, p. 1) used the notation
to indicate "a sequence is
a partition of n," and the notation
to abbreviate the partition .
The partitions on a number n correspond to the set of
solutions
to the Diophantine
equation
For example, the partitions of four, given by
(1, 1, 1, 1), (1, 1, 2), (2, 2), (4), and (1, 3) correspond to the
solutions ,
(2, 1, 0, 0), (0, 2, 0, 0), (0, 0, 0, 1), and (1, 0, 1, 0).
Particular types of partition functions include the partition
function P, giving the number of partitions of a number
as a sum of smaller integers without regard to order, and partition
function Q, giving the number of ways of writing the integer
n as a sum of positive
integers without regard to order and with the constraint that
all integers
in each sum are distinct. The partition
function b, which gives the number of partitions of
n in which no parts are multiples of k, is sometimes
also used (Gordon and Ono 1997).
The Euler
transform
gives the number of partitions of n into integer parts of
which there are
different types of parts of size 1, of size 2, etc. For example, if for all n, then is the number of partitions of n into integer
parts. Similarly, if
for n prime and
for n composite, then
is the number of partitions of n into prime parts (Sloane and
Plouffe 1995, p. 21).
A partition of a number n into a sum of elements of a list
L can be determined using a greedy
algorithm. The following table gives the number of partitions of
n into a sum of positive powers p for multiples of
n.
n 
p = 1 
p = 2 
p = 3 
p = 4 
Sloane 
A000041 
A001156 
A003108 
A046042 
10 
42 
4 
2 
1 
50 
204226 
104 
10 
4 
100 
190569292 
1116 
39 
9 
150 
40853235313 
6521 
97 
15 
200 
3972999029388 
27482 
208 
24 
250 
230793554364681 

388 
34 
300 
9253082936723602 

683 
49 
Amenable
Number, Conjugate
Partition, Durfee
Square, Elder's
Theorem, Ferrers
Diagram, Göllnitz's
Theorem, Graphical
Partition, Greedy
Algorithm, Partition
Function b, Partition
Function P, Partition
Function Q, Perfect
Partition, Plane
Partition, Prime
Partition, SelfConjugate
Partition, Set
Partition, Solid
Partition, Stanley's
Theorem
References
Andrews, G. E. The
Theory of Partitions. Cambridge, England: Cambridge
University Press, 1998.
Dickson, L. E. "Partitions." Ch. 3 in History
of the Theory of Numbers, Vol. 2: Diophantine Analysis.
New York: Chelsea, pp. 101164, 1952.
Gordon, B. and Ono, K. "Divisibility of Certain Partition
Functions by Powers of Primes." Ramanujan J. 1, 2534,
1997.
Hardy, G. H. and Wright, E. M. "Partitions."
Ch. 19 in An
Introduction to the Theory of Numbers, 5th ed. Oxford,
England: Clarendon Press, pp. 273296, 1979.
Savage, C. "Gray Code Sequences of Partitions." J.
Algorithms 10, 577595, 1989.
Skiena, S. "Partitions." §2.1 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with
Mathematica. Reading, MA: AddisonWesley, pp. 5159,
1990.
Sloane, N. J. A. Sequences A000041/M0663,
A001156/M0221,
A003108/M0209,
and A046042
in "The OnLine Encyclopedia of Integer Sequences." http://www.research.att.com/~njas/sequences/.
Sloane, N. J. A. and Plouffe, S. The
Encyclopedia of Integer Sequences. San Diego, CA: Academic
Press, 1995.
Author: Eric W. Weisstein © 1999 CRC Press
LLC, © 19992002 Wolfram Research,
Inc.
