In mathematics, a partition of a positive integer n is a way of writing n as a sum of positive integers. Two sums which only differ in the order of their summands are considered to be the same partition; if order matters then the sum becomes a composition. A summand in a partition is also called a part. The number of partitions of n is given by the partition function p(n). Main article: History of mathematics The evolution of mathematics can be seen to be an ever increasing series of abstractions. ... The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ... Addition is one of the basic operations of arithmetic. ... In mathematics, a composition of a positive integer n is a way of writing n as a sum of positive integers. ... In number theory, the partition function p(n) represents the number of possible partitions of a natural number n, which is to say the number of distinct (and order independent) ways of representing n as a sum of natural numbers. ...

Examples

The partitions of 4 are listed below:

• 4
• 3 + 1
• 2 + 2
• 2 + 1 + 1
• 1 + 1 + 1 + 1

The partitions of 8 are listed below:

• 8
• 7 + 1
• 6 + 2
• 6 + 1 + 1
• 5 + 3
• 5 + 2 + 1
• 5 + 1 + 1 + 1
• 4 + 4
• 4 + 3 + 1
• 4 + 2 + 2
• 4 + 2 + 1 + 1
• 4 + 1 + 1 + 1 + 1
• 3 + 3 + 2
• 3 + 3 + 1 + 1
• 3 + 2 + 2 + 1
• 3 + 2 + 1 + 1 + 1
• 3 + 1 + 1 + 1 + 1 + 1
• 2 + 2 + 2 + 2
• 2 + 2 + 2 + 1 + 1
• 2 + 2 + 1 + 1 + 1 + 1
• 2 + 1 + 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Among the 22 partitions for the number 8, 6 contain only odd parts:

• 7 + 1
• 5 + 3
• 5 + 1 + 1 + 1
• 3 + 3 + 1 + 1
• 3 + 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Curiously, if we count the partitions of 8 with distinct parts, we also obtain the number 6:

• 8
• 7 + 1
• 6 + 2
• 5 + 3
• 5 + 2 + 1
• 4 + 3 + 1

Is this only coincidence, or is it true that, for all positive numbers, the number of partitions with odd parts always equals the number of partitions with distinct parts? This and other results can be obtained by the aid of a visual tool, a Ferrers graph (also called Ferrers diagram, since it is not a graph in the graph-theoretical sense, or sometimes Young diagram, alluding to the Young tableau). A diagram of a graph with 6 vertices and 7 edges. ... In mathematics, a Young tableau is a combinatorial object useful in representation theory. ...

Ferrers graph

The partition 6 + 4 + 3 + 1 of the positive number 14 can be represented by the following graph:

 o o o o o o o o o o o o o o 6+4+3+1 

The 14 circles are lined up in 4 columns, each having the size of a part of the partition. The graphs for the 5 partitions of the number 4 are listed below:

 o o o o o o o o o o o o o o o o o o o o 4 3+1 2+2 2+1+1 1+1+1+1 

If we now flip the graph of the partition 6 + 4 + 3 + 1 along the NW-SE axis, we obtain another partition of 14:

 o o o o o o o o o o o o o o o o o o o o --> o o o o o o o o 6+4+3+1 4+3+3+2+1+1 

By turning the rows into columns, we obtain the partition 4 + 3 + 3 + 2 + 1 + 1 of the number 14. Such partitions are said to be conjugate of one another. In the case of the number 4, partitions 4 and 1 + 1 + 1 + 1 are conjugate pairs, and partitions 3 + 1 and 2 + 1 + 1 are conjugate of each other. Of particular interest is the partition 2 + 2, which has itself as conjugate. Such a partition is said to be self-conjugate.

Claim: The number of self-conjugate partitions is the same as the number of partitions with distinct odd parts.

Proof (sketch): The crucial observation is that every odd part can be "folded" in the middle to form a self conjugate graph:

 o o o --> o o o o o o o 

One can then obtain a bijection between the set of partitions with distinct odd parts and the set of self-conjugate partitions, as illustrated by the following example:

 o * x o o o o o o * x o * * * * o * x <--> o * x x o * o * x o * o * o * o * o o 9+7+3 5+5+4+3+2 distinct odd self-conjugate 

Similar techniques can be employed to establish, for example, the following equalities:

• The number of partitions of n into no more than k parts is the same as the number of partitions of n into parts no larger than k.
• The number of partitions of n into no more than k parts is the same as the number of partitions of n+k into exactly k parts.

Number of partitions

The number of partitions of a positive integer n is given by the partition function p(n). The number of partitions of n into exactly k parts is denoted by p_k(n). In number theory, the partition function p(n) represents the number of possible partitions of a natural number n, which is to say the number of distinct (and order independent) ways of representing n as a sum of natural numbers. ...

Ferrers graph techniques also allow us to prove results like the following:

• There are p(n) − p(n − 1) partitions of n in which each part is at least 2.
• p(1) + p(2) + ... + p(n) < p(2n)

See also

• Young tableau
• Partition of a set
• Ewens's sampling formula
• Combinadic

In mathematics, a Young tableau is a combinatorial object useful in representation theory. ... A partition of U into 6 blocks: a Venn diagram representation. ... In population genetics, Ewenss sampling formula, introduced by Warren Ewens, states that under certain conditions (specified below), if a random sample of n gametes is taken from a population and classified according to the gene at a particular locus then the probability that there are a1 alleles represented once... A combinadic is similar to a factoradic, but used for combinations. ...

Bibliographical notes

An elementary introduction to the topic of integer partition, including a discussion of Ferrers graphs, can be found in the following reference:

Miklós Bóna, A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific Publishing, 2002. ISBN 9810249004.

Another highly accessible introduction is:

Andrews and Eriksson, Integer Partitions, Cambridge University Press, 2004. ISBN 0521600901.

External links

• Partition and composition calculator
• Mathworld entry