Partitions, Compositions, and Young Tableaux

A partition of a positive integer $n$ is a set of $k$ strictly positive integers that sum up to $n$. A composition of $n$ is a particular arrangement of non­negative integers that sum up to $n$. A Young tableaux is a structure of integers $1,\; ...,\; n$ where the number of elements in each row is defined by an integer partition of $n$. Further, the elements of each row and column are in increasing order, and the rows are left justified. These three related combinatorial objects have a host of interesting applications and properties.

Here are the eleven partitions of 6. Observe that they are given in reverse lexicographic order.

Partitions[6]

Although the number of partitions grows exponentially, it does so more slowly than permutations or subsets, so complete tables can be generated for larger values of $n$.

Length[Partitions[20]]

Ferrers diagrams represent partitions as patterns of dots. They provide a useful tool for visualizing partitions, because moving the dots around provides a mechanism for proving bijections between classes of partitions. Here we construct a random partition of 100.

FerrersDiagram[RandomPartition[100]]

Here every composition of 6 into 3 parts is generated exactly once.

Compositions[6,3]

The list of tableaux of shape $\{\; 3,\; 2,\; 1\; \}$ illustrates the amount of freedom available to tableaux structures. The smallest element is always in the upper left­hand corner, but the largest element is free to be the rightmost position of the last row defined by the distinct parts of the partition.

Tableaux[{3,2,1}]

By iterating through the different integer partitions as shapes, all tableaux of a particular size can be constructed.

Tableaux[3]

The hook length formula can be used to count the number of tableaux for any shape. Using the hook length formula over all partitions of $n$ computes the number of tableaux on $n$ elements.

NumberOfTableaux[10]

Each of the 117,123,756,750 tableaux of this shape will be selected with equal likelihood.

TableForm[ RandomTableau[{6,5,5,4,3,2}] ]

A pigeonhole result states that any sequence of $n^2\; +\; 1$ distinct integers must contain either an increasing or a decreasing scattered subsequence of length $n\; +\; 1$.

LongestIncreasingSubsequence[
 RandomPermutation[50] ]

Combinatorica functions for partitions, compositions and Young tableaux.