Partition
A partition is a way of writing an integer 
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 
can be generated
in the Wolfram Language using IntegerPartitions[list].
PartitionQ[p]
in the Wolfram Language package Combinatorica`
can be used to test if a list consists of positive integers and therefore is a valid
partition.
Andrews (1998, p. 1) uses the notation 
to indicate
"a sequence 
is a partition of 
," and the
notation 
, known as the frequency
representation, to abbreviate the partition 
.
The partitions on a number 
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 
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
bk, which gives the number of partitions of 
in which no parts
are multiples of 
, is sometimes also used (Gordon and Ono
1997).
The Euler transform 
gives the number
of partitions of 
into integer parts of which there are
different types of parts of size 1, 
of size 2, etc.
For example, if 
for all 
, then 
is the number
of partitions of 
into integer parts. Similarly, if 
for 
prime and 
for 
composite, then
is the number of partitions of 
into prime parts
(Sloane and Plouffe 1995, p. 21).
A partition of a number 
into a sum of elements of a list 
can be determined using a greedy
algorithm. The following table gives the number of partitions of 
into a sum of positive
powers 
for multiples of 
.
 |  |  |  |  |
| 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 | 94987 | 388 | 34 |
| 300 | 9253082936723602 | 284316 | 683 | 49 |
Contact the MathWorld Team
partitions
