# The Unapologetic Mathematician

## Partitions and Ferrers Diagrams

We’ve discussed partitions before, but they’re about to become very significant. Let $\lambda=(\lambda_1,\dots,\lambda_k)$ be a sequence of positive integers with $\lambda_1\geq\dots\geq\lambda_k$. We write

$\displaystyle\lvert\lambda\rvert=\sum\limits_{i=1}^k\lambda_i$

If $\lvert\lambda\rvert=n$ we say $\lambda$ is a partition of $n$, and we write $\lambda\vdash n$. A partition, then, is a way of breaking a positive integer $n$ into a bunch of smaller positive integers, and sorting them in (the unique) decreasing order.

We visualize partitions with Ferrers diagrams. The best way to explain this is with an example: if $\lambda=(3,3,2,1)$, the Ferrers diagram of $\lambda$ is

$\displaystyle\begin{array}{ccc}\bullet&\bullet&\bullet\\\bullet&\bullet&\bullet\\\bullet&\bullet&\\\bullet&&\end{array}$

The diagram consists of left-justified rows, one for each part in the partition $\lambda$, and arranged from top to bottom in decreasing order. We can also draw the Ferrers diagram as boxes

$\displaystyle\begin{array}{|c|c|c|}\cline{1-3}\hphantom{X}&\hphantom{X}&\\\cline{1-3}&&X\\\cline{1-3}&&\\\cline{1-2}&&\\\cline{1-1}\end{array}$

The dangling vertical lines aren’t supposed to be there, but I’m having a hell of a time getting WordPress’ $\LaTeX$ processor to recognize an \hfill command so I can place \vline elements at the edges of columns. This should work but.. well, see for yourself:

$\displaystyle\begin{array}{ccc}\cline{1-3}\vline\hfill\hphantom{X}\hfill\vline&\hphantom{X}\hfill\vline&\hfill\vline\\\cline{1-3}\vline\hfill\hfill\vline&\hfill\vline&X\hfill\vline\\\cline{1-3}\vline\hfill\hfill\vline&\hfill\vline&\\\cline{1-2}\vline\hfill\hfill\vline&&\\\cline{1-1}\end{array}$

So, if anyone knows how to make this look like the above diagram, but without the dangling vertical lines, I’d appreciate the help.

Anyway, in both of those ugly, ugly Ferrers diagrams, the $X$ is placed in the $(2,3)$ position; we see this by counting down two boxes and across three boxes. We will have plenty of call to identify which positions in a Ferrers diagram are which in the future.

December 8, 2010