Partitions of integers and their generalisations

One of the simplest and most natural mathematical operations is the adding of integers. Integer partitions describe the ways in which a positive integer can be written as the sum of other positive integers. For example the number $4$ can be written as

$$4 \qquad = \qquad \begin{array}{lll... ...+1, & 1+3, &\\ 2+2, && \\ 2+1+1, & 1+2+1, & 1+1+2, \\ 1+1+1+1 && \end{array}$$

So there are $8$ ways of writing the number $4$ as a sum of positive integers. These $8$ different sums are compositions.

Definition 9
A composition of a positive integer $n$ is an ordered finite sequence of positive integers $\lambda_1, \dots, \lambda_k$ such that $\sum_{i=1..k} \lambda_i = n$.

Implicit in this definition is that we care about the order in which the summands appear; the composition $3+1$ is not the same as $1+3$. Since addition is commutative, this distinction seems a little artificial, and it would be more natural to consider the compositions $3+1$ and $1+3$ to be the same object. One way of ensuring this is to require the summands to be in non-increasing order -- this leads us to partitions.

Definition 10
A partition of a positive integer $n$ is a finite sequence of non-increasing positive integers $\lambda_1, \dots, \lambda_k$ such that $\sum_{i=1..k} \lambda_i = n$.

Using this we find that there are $5$ partitions of the number $4$.

$$4 \qquad = \qquad \begin{array}{lll} 4, & 3+1, & 2+2, \\ 2+1+1, & 1+1+1+1 & \end{array}$$

There is a vast array of combinatorial and algebraic structure to be explored in the theory of partitions, far more than we have time for here (see [1] for more on this subject). Instead let us consider the graphical representation of partitions and compositions.

Let us represent a positive integer, $k$, by a column of $k$ cells. A sequence of positive integers is represented by a sequence of columns. In this way every composition can be uniquely represented by a sequence of columns of cells -- the total number of cells is the total of the composition (see figure 18).

Figure 18: Representing the $8$ compositions of the number $4$ by sequences of columns.

These sequences of columns are bargraph polygons and so the number of compositions of $n$ is equal to the number of bargraph polygons of area $n$.

Figure 19: Representing the $5$ partitions of the number $4$ by sequences of columns.

If we consider partitions instead of compositions, then the sequence of columns must be non-increasing -- this gives us Ferrers diagrams (see figure 19). Generalising this idea, we consider other subsets with other conditions; for example, if we require that the sequence be unimodal then we obtain stack polygons. Polyominoes can be seen as a generalisation of these objects.