Mélodie Lapointe ([email protected]) and Pauline Hubert ([email protected])
Recall that a partition \mu of n, one writes \mu \vdash n or n = |\mu|, is an sequence of integers (\mu_0,\mu_1,\dots,\mu_{k-1}) (the m_i's are the parts of \mu) with \mu_0 \geq \mu_1 \geq \dots \geq \mu_{k-1} \geq 0 and n = \mu_0 + \mu_1 + \dots + \mu_{k-1}. The number \ell(\mu):= k of parts of \mu is said to be its length. A partition \mu may also be described as a Ferrers diagram, which is the n-subset of \mathbb{N}\times \mathbb{N} :
\left\{(a,b)|0 \leq a \leq \mu_i \text{ and } b < \ell(\mu)\right\}.
This set is also denoted \mu, and its elements are the cells of \mu. The conjugate of \mu, is the partition \mu' such that
\mu' = \{(b,a) \vert (a,b) \in \mu\}.
Parts of \mu are the lengths of the rows of its diagram, and parts of \mu are the lengths of its columns.
For more, see https://en.wikipedia.org/wiki/Partition_(number_theory)
We mostly follow the notation convention of Macdonald's book: Symmetric Functions and Hall Polynomials, Second Edition, Oxford Mathematical Monographs, 1998.
Partition can be created/declared in SAGE the following way:
sage: Partition([10,10,5,2,2,1]) [10, 10, 5, 2, 2, 1]
One can also list all partitions of a given integer.
sage: Partitions(4).list() [[4], ...]
Or simply count them.
(We underline that this function does not actually generate the partitions of n in order to count them; hence it is amazingly fast.)
sage: Partitions(3000).cardinality() 4960251...
sage: Partitions(100000).cardinality() 274935...
One may add constraints on partitions; for instance, to get partitions of 5 of length 2.
sage: p = Partitions(5,length=2) sage: p.list() [[4, 1], ...]
or get all partitions of 6 with length between 3 and 5.
sage: p = Partitions(6,min_length=3,max_length=5) sage: p.list() [[4, 1, 1], ...]
By default SAGE uses the English convention, but it has become the tradition in recent years to use the more natural (cartesian coordinates) French notation. Here is how to set this
sage: Partitions.options(convention='french')
sage: mu = Partition([8,5,5,5,4,3,3,2]) sage: print(mu.ferrers_diagram()) ...
The list of cells of m may be obtained as follows
sage: mu = Partition([8,5,5,5,4,3,3,2]) sage: mu.cells() [(0, 0), ...]
If one insists on using the English convention, one could globally switch back as follows
sage: Partitions.options(convention='english') sage: mu = Partition([8,5,5,5,4,3,3,2]) sage: print(mu.ferrers_diagram()) ...
A partition \mu is included in a partition \lambda if \mu_i \leq \lambda_i, \forall i. In other words, the diagram of \mu is a subset of the diagram of \lambda. For example, one can list all partitions \lambda of 5 such that the partition [2,1] is included in \lambda.
sage: p = Partitions(5,inner= [2,1]) sage: p.list() [[4, 1], ...]
Or all partitions of 5 included in the partition [4,3,2,1].
sage: p = Partitions(5,outer=[4,3,2,1]) sage: p.list() [[4, 1], ...]
The default (total) order on partitions is the lexicographic order.
sage: mu = Partition([4,3,3]) sage: nu = Partition([4,4,1]) sage: mu < nu True
*Exercise:*
Let \lambda be the partition [15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]. Compute:
\sum\limits_{i=0}^{20} \sum\limits_{\mu \vdash i \subseteq \lambda} q^i.
sage: q = var('q')
sage: mu = [15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
sage: show(sum(Partitions(i,outer=mu).cardinality()*q^i for i in range(20)))
...
An A-valued Young tableaux of shape \mu is a "filling" of the cells of a Ferrers diagram of \mu with elements of an ordered set A. Hence, it is a function \tau:\mu \rightarrow A. A tableau is said to be standard if it is bijective (hence A has cardinality equal to the number of cells of \mu), and its entries on each row (and each column) are strictly increasing from left to right (from bottom to top in french convention). A tableau (not necessarily bijective) is said to be semistandard if its entries are weakly increasing from left to right on each row, and strictly increasing on each column. These object can be constructed in the following way.
sage: t = SemistandardTableau([[1,2,4],[3,3,6],[5,7],[8]])
sage: t.pp()
1 2 4
...
sage: print('')
sage: s = StandardTableau([[1,2,4],[3,6],[5,7],[8]])
sage: s.pp()
1 2 4
...
The function pp() ("pp" stands for pretty print) gives a nicer display for Young tableaux. Observe that if you set options (like French vs English convention) for partitions, these will also apply to Young tableaux.
It is possible to list all semistandard and standard Young tableaux of a given partition.
sage: x = SemistandardTableaux([4,3,3,2,1]) sage: print(x.cardinality()) 39... sage: y = StandardTableaux([4,3,3,2,1]) sage: print(y.cardinality()) 15...
The functions for partitions, such as display, options, cardinality, and list, are also found in Young tableaux.
*Exercise:*
Verify that the number of standard Young tableaux of shape :math:`[n,n]` is equal to the Catalan number for :math:`0 leq n leq 20`. (The function catalan_number(:math:`n`) returns the nth catalan number).
sage: all(catalan_number(i)==StandardTableaux([i,i]).cardinality() for i in range(1,10)) True
*Exercise:*
Compute the sum of all monomials of degree 5 in three variables using partitions and standard tableaux.
sage: var('x y z')
(x, y, z)
sage: young_tableaux = []
sage: monomials = []
sage: for i in Partitions(5):
....: young_tableaux.extend(SemistandardTableaux(i,max_entry=3).list())
sage: for j in young_tableaux:
....: k = reduce(operator.add,j)
....: monomials.append(x^k.count(1)*y^k.count(2)*z^k.count(3))
sage: show(sum(monomials))
...
The classical hook formula
\begin{eqnarray}f^{\mu}: = \frac{n!}{\prod_{c \in \mu} h(c,\mu)},\end{eqnarray}
with h((i,j),\mu) := \mu_i + \mu'_j -i -j - 1, may be coded as
sage: def hook_formula(mu): ....: return factorial(add(k for k in mu))/prod(mu.hook_length(i,j) for i,j in mu.cells())
sage: hook_formula(Partition([4,3,1,1])) 216