 |
|
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
add-on 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, Self-Conjugate
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. 101-164, 1952.
Gordon, B. and Ono, K. "Divisibility of Certain Partition
Functions by Powers of Primes." Ramanujan J. 1, 25-34,
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. 273-296, 1979.
Savage, C. "Gray Code Sequences of Partitions." J.
Algorithms 10, 577-595, 1989.
Skiena, S. "Partitions." §2.1 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with
Mathematica. Reading, MA: Addison-Wesley, pp. 51-59,
1990.
Sloane, N. J. A. Sequences A000041/M0663,
A001156/M0221,
A003108/M0209,
and A046042
in "The On-Line 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, © 1999-2002 Wolfram Research,
Inc.
|
