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$.

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$.

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$:

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 conjugate of $\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.

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 Theorem

The 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.

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.