Number Partitions

Why

How many ways are there to split $n$ objects into nonoverlapping groups, when the objects are indistinguishable?

Definition

Suppose $n$ is a nonzero natural number. A partition of $n$ is a nonincreasing list of nonzero natural numbers whose sum is $n$. The requirement that the list of numbers be nonincreasing makes the representation unique. The terms of the list are called the parts of the partition. The number $n$ is sometimes called the weight of the partition. The number of times a particular number appears in the list is called the multiplicity of that part.

Examples

What are the partitions of the number 5?

\[ \begin{aligned} 5 &= 5 \\ &= 4 + 1 \\ &= 3 + 2 \\ &= 3 + 1 + 1 \\ &= 2 + 2 + 1 \\ &= 2 + 1 + 1 + 1 \\ &= 1 + 1 + 1 + 1 + 1 \end{aligned} \]

These seven identities correspond to the seven partitions of 5, namely $(5,)$, $(4, 1)$, $(3, 2)$, $(3,1,1)$, $(2,2,1)$, $(2,1,1,1)$, $(1,1,1,1,1)$. The multiplicity of 1 in these partitions is 0, 1, 0, 2, 1, 3, 5, respectively.

Notation

Suppose $\lambda $ is a list in $\N $ of length $r \geq 1$. Then $\lambda = (\lambda _1, \dots , \lambda _r)$ is a partition of $n \in \N $ if

\[ \lambda _1 + \lambda _2 + \cdots + \lambda _r = n \]

and $\lambda _1 \geq \lambda _2 \geq \cdots \geq \lambda _r$. The terms of $\lambda $ are the parts of the partition, so $\lambda _i$ is the $i$th part, where $i = 1, \dots , r$. Some authors denote the weight of $\lambda $ by $\num{\lambda }$.

Partition function

How many partitions are there of the number $n$? We denote this number by $p(n).$ From the examples above, $p(5) = 7$.