Partition — Definition, Formula & Examples

A partition of a positive integer

n

is a way of expressing

n

as a sum of positive integers, where the order of the summands does not matter. For example, the number 4 has five partitions:

4

3+1

2+2

2+1+1

, and

1+1+1+1

A partition of a positive integer $n$ is a non-increasing sequence of positive integers $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k > 0$ such that $\lambda_1 + \lambda_2 + \cdots + \lambda_k = n$ . Each $\lambda_i$ is called a part of the partition. The partition function $p(n)$ counts the total number of distinct partitions of $n$ .

Key Formula

\prod_{k=1}^{\infty} \frac{1}{1 - x^k} = \sum_{n=0}^{\infty} p(n)\, x^n

Where:

$p(n)$ = The number of partitions of the non-negative integer n, with p(0) = 1 by convention
$x$ = A formal variable in the generating function
$k$ = Index representing each possible part size

How It Works

To find all partitions of

n

, systematically list every way to write

n

as a sum of positive integers in non-increasing order. Start with

n

itself as a single part, then break off the smallest possible pieces while keeping parts in descending order. Two partitions are considered the same if they contain exactly the same parts —

3+1

and

1+3

count as one partition. The partition function

p(n)

grows rapidly:

p(1)=1

p(5)=7

p(10)=42

p(100)=190{,}569{,}292{,}356

Worked Example

Problem: Find all partitions of 5 and determine p(5).

Largest part = 5: The number itself as a single part.

5

Largest part = 4: The remaining 1 can only be expressed as 1.

4 + 1

Largest part = 3: The remaining 2 can be split as 2 or 1+1.

3 + 2, \quad 3 + 1 + 1

Largest part = 2: The remaining 3 must use parts no larger than 2.

2 + 2 + 1, \quad 2 + 1 + 1 + 1

Largest part = 1: All parts equal to 1.

1 + 1 + 1 + 1 + 1

Answer: There are 7 partitions of 5, so

p(5) = 7

Visualization

Why It Matters

Partitions appear throughout combinatorics, algebra, and mathematical physics. They classify representations of symmetric groups and general linear groups, making them essential in abstract algebra courses. Hardy and Ramanujan's asymptotic formula for

p(n)

is a landmark result in analytic number theory.

Common Mistakes

Mistake: Counting different orderings as distinct partitions (e.g., treating 3+2 and 2+3 as two partitions of 5).

Correction: Order does not matter in partitions. Always write parts in non-increasing order. If order matters, you are counting compositions, not partitions.