= Integer partition
{title2=$p(n)$}
{wiki}
An <integer partition> of a <nonnegative integer> $n$ is a <multiset> of <positive integers> whose <sum> is $n$: repetitions matter, but the order of the summands does not. Equivalently, write its parts in decreasing order, allowing equality:
$$
\lambda=(\lambda_1,\ldots,\lambda_\ell),\qquad
\lambda_1\geq\cdots\geq\lambda_\ell>0,\qquad
\sum_{i=1}^{\ell}\lambda_i=n.
$$
The notation $\lambda\vdash n$ says that $\lambda$ is an <integer partition> of $n$. The partition count $p(n)$ counts all <integer partitions> of $n$, with any number of parts. Zero has one empty <integer partition>, so $p(0)=1$. The <partition of an integer> article develops the same objects in <representation theory of the symmetric group>.<Enumerative Combinatorics, Volume 1 (second-edition draft) by Richard Stanley>[section 1.7, definitions of partitions and diagrams]{ref}
\b[Computed example.] The seven <integer partitions> of five are exactly
$$
5;\quad 4+1;\quad 3+2;\quad 3+1+1;\quad
2+2+1;\quad 2+1+1+1;\quad 1+1+1+1+1.
$$
Thus $p(5)=7$. Sorting each list of positive summands into decreasing order prevents repetitions in this enumeration. Grouping by largest part verifies completeness: largest parts $5,4,3,2,1$ contribute respectively $1,1,2,2,1$ possibilities. For largest part $3$, the remaining $2$ is either $2$ or $1+1$; for largest part $2$, the remaining $3$ uses only $2$ and $1$, giving $2+1$ or $1+1+1$.
\Image[/integer-partitions-of-five.png]
{title=All seven <integer partitions> of five, drawn as <Ferrers diagrams>: each row has as many dots as its part}
An <integer partition> keeps sizes without named positions. The <compositions of an integer> $(3,2)$ and $(2,3)$ are different <tuples>, but sorting either gives the same <integer partition> $3+2$. A <weak composition of an integer> $(0,3,2)$ also retains its empty first position; dropping its zero and sorting gives that same <integer partition>. Conversely, a <set partition> records which distinct elements belong to each block. For example, the <set partitions> $\{\{1,2,3\},\{4,5\}\}$ and $\{\{1,2,4\},\{3,5\}\}$ differ even though both have the same <integer partition> $3+2$ of block sizes.
The <Ferrers diagram> makes an <integer partition> into a shape. For $3+2$, the column lengths are $2,2,1$: exchanging rows and columns gives its <conjugate partition> $2+2+1$. Exchanging again recovers $3+2$, so this operation is a <bijection>. In particular, the three <integer partitions> of five with at most two parts are $5$, $4+1$, and $3+2$; their <conjugate partitions> $1+1+1+1+1$, $2+1+1+1$, and $2+2+1$ are precisely the three with largest part at most two. This visible symmetry explains the equal counts for these two restrictions. The square-cell version is the existing <Young diagram>.
\b[Counting by a generating function.] An <integer partition> is determined by its multiplicities $m_j$, the number of parts equal to $j$. Its size condition is $\sum_{j\geq1}j m_j=n$. Consequently its <ordinary generating function> is
$$
\sum_{n\geq0}p(n)q^n
=\prod_{j\geq1}\left(1+q^j+q^{2j}+\cdots\right)
=\prod_{j\geq1}\frac{1}{1-q^j}.
$$
\b[Proof outline.] Choose the term $q^{jm_j}$ from the $j$th <geometric series>. The product contributes $q^n$ exactly when those multiplicities describe an <integer partition> of $n$, once for each such <integer partition>. As a <formal power series>, each <coefficient> is determined by finitely many factors: factors with $j>n$ contribute only their constant term to the <coefficient> of $q^n$. For $n=5$, multiplication through $j=5$ gives $1+q+2q^2+3q^3+5q^4+7q^5$ up to degree five, independently recovering $p(5)=7$. Restricting the factors gives the <generating function for partitions with bounded parts>. This is useful because restrictions on summands become choices of factors, while <conjugate partitions> turn restrictions on numbers of rows into restrictions on row lengths.<Enumerative Combinatorics, Volume 1 (second-edition draft) by Richard Stanley>[section 1.8, conjugation and partition generating functions]{ref}
Back to article page
