The Unapologetic Mathematician

Mathematics for the interested outsider

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 Posted by | Algebra, Group theory, Representation Theory, Representations of Symmetric Groups | 10 Comments