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
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
to the Diophantine
For example, the partitions of four, given by
(1, 1, 1, 1), (1, 1, 2), (2, 2), (4), and (1, 3) correspond to the
(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
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).
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
||p = 1
||p = 2
||p = 3
||p = 4|
Function b, Partition
Function P, Partition
Function Q, Perfect
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,
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,
Sloane, N. J. A. Sequences A000041/M0663,
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
Author: Eric W. Weisstein
© 1999 CRC Press
LLC, © 1999-2002 Wolfram Research,