[go: up one dir, main page]

TOPICS
Search

Partition


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, 10=3+2+2+2+1. All the partitions of a given positive integer n 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 lambda|-n to indicate "a sequence lambda is a partition of n," and the notation (1^(a_1)2^(a_2)...), known as the frequency representation, to abbreviate the partition {1,...,1_()_(a_1),2,...,2_()_(a_2),...}.

The partitions on a number n correspond to the set of solutions (j_1,j_2,...,j_n) to the Diophantine equation

 1j_1+2j_2+3j_3+...+nj_n=n.

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 (j_1,j_2,j_3,j_4)=(4,0,0,0), (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 bk, 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 b_n gives the number of partitions of n into integer parts of which there are a_1 different types of parts of size 1, a_2 of size 2, etc. For example, if a_n=1 for all n, then b_n is the number of partitions of n into integer parts. Similarly, if a_n=1 for n prime and a_n=0 for n composite, then b_n 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.

np=1p=2p=3p=4
SloaneA000041A001156A003108A046042
1042421
50204226104104
1001905692921116399
1504085323531365219715
20039729990293882748220824
2502307935543646819498738834
300925308293672360228431668349

See also

Amenable Number, Conjugate Partition, Durfee Square, Elder's Theorem, Ferrers Diagram, Frequency Representation, Göllnitz's Theorem, Graphical Partition, Greedy Algorithm, Partition Function, 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 Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

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: Dover, pp. 101-164, 2005.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."Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.

Referenced on Wolfram|Alpha

Partition

Cite this as:

Weisstein, Eric W. "Partition." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Partition.html

Subject classifications