next up previous
Next: Polymer models Up: Why do we want Previous: Percolation models

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

% latex2html id marker 3829
$\displaystyle 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$.

% latex2html id marker 3871
$\displaystyle 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.
% latex2html id marker 3887
\includegraphics[scale=0.4]{figs/compose.eps}
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.
% latex2html id marker 3903
\includegraphics[scale=0.4]{figs/partition.eps}

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.


next up previous
Next: Polymer models Up: Why do we want Previous: Percolation models
Andrew Rechnitzer 2002-12-16