# Partition of an Integer

A **partition** of a positive integer $n$ is an expression of $n$ as the sum of one or more positive integers (or **parts**). The order of the integers in the sum "does not matter": that is, two expressions that contain the same integers in a different order are considered to be the same partition.

The number of different partitions of $n$ is denoted $p(n)$. This function is called the **partition function**.

The partitions of $5$ are as follows:

$\begin{aligned} &5 \\ &4+1 \\ &3+2 \\ &3+1+1 \\ &2+2+1 \\ &2+1+1+1 \\ &1+1+1+1+1. \end{aligned}$

So $p(5)=7$.

#### Contents

## Recursions and Closed-form Formulas

Combinatorial functions such as $p(n)$ often lend themselves to recursions that make them easier to compute. For instance, consider the number of decompositions of $n$ as the sum of positive integers in which order *does* matter (sometimes called **compositions**). Let $c(n)$ be the number of compositions of $n$. For instance, $c(3) = 4$ because $3 = 1+1+1 = 1+2 = 2+1 = 3$.

Then there is a recursion for $c(n)$: if the first term of a composition of $n$ is $k$, the remaining terms are a composition of $n-k$. So the number of such compositions is $c(n-k)$. This leads to the recursive formula $c(n) = c(n-1) + c(n-2) + \cdots + c(1) + 1.$ Solving this recursion is not hard: note that $c(n+1) = c(n)+c(n-1)+\cdots+c(1)+1 = c(n)+c(n) = 2c(n)$, and $c(1)=1$, so $c(n) = 2^{n-1}$. (Exercise for the reader: there are direct, non-recursive proofs of this formula as well.)

However, proceeding in the same way for the partition function is not as straightforward, because of the possibility of over-counting partitions. For instance, a partition of $4$ that starts with $1$ is $1+2+1$, which corresponds to the partition $2+1$ of $3$, and a partition of $4$ that starts with $2$ is $2+1+1$, which corresponds to the partition $1+1$ of $2$; but *these are the same partition*, so any recursive formula must avoid counting them twice.

In fact, there is no closed-form formula for $p(n)$ in any meaningful sense. Many down-to-earth questions about the partition function are quite difficult and mysterious: for instance, it is not even known whether there are infinitely many $n$ such that $p(n)$ is divisible by $3$.

$\begin{aligned} p(17) &= 297 \\ p(18) &= 385 \\ p(19) &= 490 \\ p(20) &= 627 \\ p(21) &= 792 \end{aligned}$

Let $p(n)$ be the number of partitions of an integer $n$. The values of $p(17), p(18),p(19),p(20), p(21)$ are as shown above.

How many partitions of 20 are there that do not contain any parts equal to 1?

## Pictorial Representations

Partitions are represented pictorially in **Ferrers diagrams**: each part of the permutation is represented by a row of dots, where the number of dots equals the part. The rows, like the parts, are laid out in descending order of size:

$\begin{aligned} &\bullet\, \bullet\, \bullet \\ &\bullet\, \bullet \\ &\bullet\, \bullet \\ &\bullet \end{aligned}$

This diagram represents the partition $8 = 3+2+2+1$.

**Young diagrams** are similar, but use squares instead of dots. Here is the Young diagram for $10 = 5+4+1$:

## Conjugate Partitions

One concept that is most easily understood from diagrams of partitions is the notion of conjugacy.

Let $\pi$ be a partition of $n$, and let $a_k$ be the number of parts of $\pi$ that are $\ge k$. Suppose the largest part is $d$. Then the

conjugateof $\pi$ is the partition$n = a_1 + a_2 + \cdots + a_d.$

There is something to prove in the definition, namely that the sum of the $a_i$ actually equals $n$. To see this, note that a part of size $b$ is counted once in $a_1, a_2, \ldots, a_b$. So, a part of size $b$ contributes $b$ to the sum, and therefore the sum is the same as the sum of the parts of $\pi$.

This is not the easiest way to think about conjugate partitions. They are most simply described in terms of Ferrers diagrams: *the Ferrers diagram of the conjugate partition is obtained from the Ferrers diagram of the original partition via reflection along the top-left to bottom-right diagonal.* The operation is similar to a matrix transpose; the columns of the diagram change to rows and the rows change to columns.

The partition $8=3+2+2+1$ has the following Ferrers diagram:

$\begin{aligned} & \bullet\, \bullet\, \bullet \\ & \bullet\, \bullet \\ & \bullet\, \bullet \\ & \bullet \end{aligned}$

Its conjugate has the following Ferrers diagram:

$\begin{aligned} & \bullet\, \bullet\, \bullet\, \bullet \\ & \bullet\, \bullet\, \bullet \\ & \bullet \end{aligned}$

So, it is $8 = 4+3+1$.

Note that the description via Ferrers diagrams shows without any work that conjugating twice returns the original partition, which was not necessarily immediately clear from the definition of conjugation.

Conjugate partitions are used in many bijective proofs of results about partitions; here is one basic example.

Show that the number $p(n,k)$ of partitions of a positive integer $n$ into exactly $k$ parts equals the number of partitions of $n$ whose largest part equals $k$. For instance, $7 = 5+1+1 = 4+2+1 = 3+2+2 = 3+3+1$ and $7 = 3+3+1 = 3+2+2 = 3+2+1+1 = 3+1+1+1+1$, so $p(7,3) = 4$.

Let $S(n,k)$ be the set of partitions of $n$ into $k$ parts and let $T(n,k)$ be the set of partitions of $n$ whose largest part equals $k$. Then there is a bijection $f\colon S(n,k) \to T(n,k)$ defined by $f(\pi) =$ the conjugate of $\pi$. This is because the Ferrers diagram of a partition in $S(n,k)$ has a first column of length $k$, so its conjugate has top row of length $k$. And $f$ is a bijection because it has an inverse map, namely conjugation. So the two sets have the same size. $_\square$

For example, for $n=7,k=3$, the function $f$ is

$\begin{aligned} f(5+1+1) &= 3+1+1+1+1 \\ f(4+2+1) &= 3+2+1+1 \\ f(3+2+2) &= 3+3+1 \\ f(3+3+1) &= 3+2+2. \end{aligned}$

Other examples are given in the wiki on bijective proofs.

## Generating Functions

Main Article: Generating Functions

Many theorems about partitions that have complicated combinatorial proofs are easier and more accessible via generating functions. It is often the case that formal power series of the form $\sum a_n x^n$, where the $a_n$ count certain types of partitions, can be expressed as infinite products in useful ways.

Express $\displaystyle \sum_{n=0}^\infty p(n) x^n$ as an infinite product of power series.

Consider the product $\big(1+x+x^2+x^3+\cdots\big)\big(1+x^2+x^4+x^6+\cdots\big)\big(1+x^3+x^6+x^9+\cdots\big)(\cdots).$ The coefficient of $x^n$ in this expansion is $p(n)$: suppose a partition of $n$ has $a_1$ 1s, $a_2$ 2s, and so on. Then $n = a_1+2a_2+\cdots+na_n$, and this corresponds to the term in the expansion of the infinite product given by $x^{a_1}$ from the first sum, times $x^{2a_2}$ from the second sum, and so on.

Rewriting this using geometric series gives $\sum_{n=0}^\infty p(n) x^n = \prod_{k=1}^{\infty} \frac1{1-x^k}.\ _\square$

Euler's Pentagonal Number TheoremThe product $\prod_{k=1}^{\infty} \big(1-x^k\big) = 1 - x - x^2 + x^5+x^7- x^{12}-\cdots$ equals $\sum_{m=-\infty}^{\infty} (-1)^m x^{\frac{m(3m-1)}2}.$

Note: Numbers of the form $\frac{m(3m-1)}2$ are called

pentagonal numbers.

The theorem can be proved using partitions as well: the coefficient of $x^k$ in the product counts the number of partitions of $k$ with an even number of parts minus the partitions of $k$ with an odd number of parts. It can be shown (using Ferrers diagrams) that there is a bijection between these two sets of partitions unless $k$ is a pentagonal number, in which case there is a bijection between the sets with one specific partition removed.

Let the partition function $P(n)$ enumerate the ways $n$ can be expressed as a distinct sum of positive integers, e.g. $P(4) = 5$ since $4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1$ are the only ways to represent $4$.

$\prod_{p \ \text{prime}} \left[ \sum_{n=0}^{\infty} P(n)p^{-n} \right]$

Does the above product converge?

Euler's pentagonal number theorem implies the following beautiful recurrence relation for $p(n)$: $p(n) = p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)\cdots,$ where the sign of $p(n-k)$ is the opposite of the sign of $x^k$ in the sum expansion in Euler's pentagonal number theorem.

**Cite as:**Partition of an Integer.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/partition-of-an-integer/