Wolfram ResearchWolfram Research MathWorldMathWorld
Researchwww.wolfram.com ProductsServicesSolutionsResource LibraryNewsOnline StoreOur Company


Wolfram Web Resources Astronomy Biography Chemistry Mathematics Physics
MathWorld Logo
   
     
Index by subject
Alphabetical Index
About this site
Eric's other sites
Order books
AlgebraApplied MathematicsCalculus and AnalysisDiscrete MathematicsFoundations of MathematicsGeometryHistory and TerminologyNumber TheoryProbability and StatisticsRecreational MathematicsTopologyAbout MathWorldAuthor's note about CRC's lawsuitFAQWhat's newRandom entryContributeSign the guestbookEmail commentsHow can I help?Terms of site usageOrder Eric Weisstein's encyclopedia from the Wolfram storeOrder Eric Weisstein's encyclopedia from amazon.com
  Discrete Mathematics  >    Combinatorics  >    Partitions  v 



Partition
    

download Partition.nbMathReader
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.



header
logo logo