In number theory and combinatorics, a partition of a non-negative integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. (If order matters, the sum becomes a composition.) For example, 4 can be partitioned in five distinct ways:
4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1 The only partition of zero is the empty sum, having no parts. The order-dependent composition 1 + 3 is the same partition as 3 + 1, and the two distinct compositions 1 + 2 + 1 and 1 + 1 + 2 represent the same partition as 2 + 1 + 1. An individual summand in a partition is called a part. The number of partitions of n is given by the partition function p(n). So p(4) = 5. The notation λ ⊢ n means that λ is a partition of n. Partitions can be graphically visualized with Young diagrams or Ferrers diagrams. They occur in a number of branches of mathematics and physics, including the study of symmetric polynomials and of the symmetric group and in group representation theory in general.
Examples The seven partitions of 5 are
5 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 Some authors treat a partition as a non-increasing sequence of summands, rather than an expression with plus signs. For example, the partition 2 + 2 + 1 might instead be written as the tuple (2, 2, 1) or in the even more compact form (22, 1) where the superscript indicates the number of repetitions of a part. This multiplicity notation for a partition can be written alternatively as 1 m 1 2 m 2 3 m 3 ⋯ {\displaystyle 1^{m_{1}}2^{m_{2}}3^{m_{3}}\cdots } , where m1 is the number of 1's, m2 is the number of 2's, etc. (Components with mi = 0 may be omitted.) For example, in this notation, the partitions of 5 are written 5 1 , 1 1 4 1 , 2 1 3 1 , 1 2 3 1 , 1 1 2 2 , 1 3 2 1 {\displaystyle 5^{1},1^{1}4^{1},2^{1}3^{1},1^{2}3^{1},1^{1}2^{2},1^{3}2^{1}} , and 1 5 {\displaystyle 1^{5}} .
Diagrammatic representations of partitions There are two common diagrammatic methods to represent partitions: as Ferrers diagrams, named after Norman Macleod Ferrers, and as Young diagrams, named after Alfred Young. Both have several possible conventions; here, we use English notation, with diagrams aligned in the upper-left corner.
Ferrers diagram The partition 6 + 4 + 3 + 1 of the number 14 can be represented by the following diagram:
The 14 circles are lined up in 4 rows, each having the size of a part of the partition. The diagrams for the 5 partitions of the number 4 are shown below:
Young diagram
An alternative visual representation of an integer partition is its Young diagram (often also called a Ferrers diagram). Rather than representing a partition with dots, as in the Ferrers diagram, the Young diagram uses boxes or squares. Thus, the Young diagram for the partition 5 + 4 + 1 is
while the Ferrers diagram for the same partition is
While this seemingly trivial variation does not appear worthy of separate mention, Young diagrams turn out to be extremely useful in the study of symmetric functions and group representation theory: filling the boxes of Young diagrams with numbers (or sometimes more complicated objects) obeying various rules leads to a family of objects called Young tableaux, and these tableaux have combinatorial and representation-theoretic significance. As a type of shape made by adjacent squares joined together, Young diagrams are a special kind of polyomino.
Partition function
The partition function p ( n ) {\displaystyle p(n)} counts the partitions of a non-negative integer n {\displaystyle n} . For instance, p ( 4 ) = 5 {\displaystyle p(4)=5} because the integer 4 {\displaystyle 4} has the five partitions 1 + 1 + 1 + 1 {\displaystyle 1+1+1+1} , 1 + 1 + 2 {\displaystyle 1+1+2} , 1 + 3 {\displaystyle 1+3} , 2 + 2 {\displaystyle 2+2} , and 4 {\displaystyle 4} . The values of this function for n = 0 , 1 , 2 , … {\displaystyle n=0,1,2,\dots } are:
1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... (sequence A000041 in the OEIS). The generating function of p {\displaystyle p} is
… excerpt ends here. Continue reading the full article.
