combinat::tableaux
--
Young tableaux
The library combinat::tableaux
provides functions for counting,
generating, and manipulating Young tableaux.
p
be a partition of n
. Recall that a partition
can be depicted by a diagram of boxes (see
combinat::partitions
). Fill now the boxes with numbers.
Such a filling is a Young tableau, or, shorter,
a tableau if the numbers in the
boxes are non-decreasing along rows and (strictly) increasing from
bottom to top along columns. The partition p
is called the
shape of the tableau. Here is an example of tableau of
shape [5,3,1]
:
+---+ | 4 | +---+---+---+ | 2 | 3 | 3 | +---+---+---+---+---+ | 1 | 1 | 2 | 2 | 3 | +---+---+---+---+---+Moreover, if every positive integer up to
n
appears exactly
once, the tableau is standard. Here is an example of
standard tableau of shape [5,3,1]
:
+---+ | 9 | +---+---+---+ | 3 | 4 | 6 | +---+---+---+---+---+ | 1 | 2 | 5 | 7 | 8 | +---+---+---+---+---+Currently,
combinat::tableaux
deals mainly with standard
tableaux.[[9],[3,4,6],[1,2,5,7,8]]
. Cat::CombinatorialClass
The MuPAD domainused to represent tableaux: DOM_LIST
.
The MuPAD type used to represent standard tableaux.
isA(tableau T <, partition p>)
T
is a
tableau of shape p
or not.
isAStandard(tableau T <, partition p>)
T
is a standard tableau or not.T
is a
standard tableau of shape p
or not.
shape(tableau T)
T
.
toWord(tableau T)
T
,
from top to bottom, and from left to right.
fromWord(word w)
w
. Be careful:
if w
is a natural reading of a tableau, one recovers the tableau,
but if it is not the case, the result is not necessarily a tableau.
fromShapeAndWord(partition shape, word w)
shape
whose natural reading
is the word w
. Be careful: the result is not necessarily a
tableau.
count(partition p)
p
.
We make use of the hook-length formula.
list(partition p)
p
.
generator(partition p)
p
.
conjugate(filling f)
f
.
Geometrically, this operation amounts to a reflection of
the diagram with respect to the main diagonal.
canonical(partition p)
p
obtained by
filling consecutive rows starting from the bottom.
columnCanonical(partition p)
p
obtained by
filling consecutive columns starting from the left.
rowStabilizer(standard filling t)
t
that stabilize the rows of t
.
columnStabilizer(standard filling t)
t
that stabilize the columns of t
.
indexFilling(standard tableau t)
t
, during the
computation of the cocharge.
cocharge(standard tableau t)
t
.
insertWord(tableau t, word w)
w
in t
.
schensted(word w)
w
. Generally, the result is a pair composed
of a semi-standard tableau and a standard tableau.
invSchensted(semi-standard tableau t1, standard tableau t2)
The following list of lists of integers is a tableau but not a standard tableau:
>> combinat::tableaux::isA([[4, 4], [1, 2, 4]]);
combinat::tableaux::isAStandard([[4, 4], [1, 2, 4]]);
TRUE FALSE
Moreover, the shape of this tableau is confirmed to be [3,2], and not of shape [3,1,1].
>> combinat::tableaux::isA([[4, 4], [1, 2, 4]],[3,2]);
combinat::tableaux::isA([[4, 4], [1, 2, 4]],[3,1,1]);
TRUE FALSE
There are 5 tableaux of shape (3,2):
>> combinat::tableaux::count([3,2])
5
Here is the list:
>> combinat::tableaux::list([3,2])
[[[4, 5], [1, 2, 3]], [[3, 5], [1, 2, 4]], [[2, 5], [1, 3, 4]], [[3, 4], [1, 2, 5]], [[2, 4], [1, 3, 5]]]
If you want to run through the tableaux of a shape, you can generate them one by one to save memory:
>> g := combinat::tableaux::generator([3,2]):
g(); g(); g(); g(); g(); g()
[[4, 5], [1, 2, 3]] [[3, 5], [1, 2, 4]] [[2, 5], [1, 3, 4]] [[3, 4], [1, 2, 5]] [[2, 4], [1, 3, 5]] FAIL
Typically, this would be used as follows:
>> g := combinat::tableaux::generator([3,2]):
while (p := g()) <> FAIL do print(p): end:
[[4, 5], [1, 2, 3]] [[3, 5], [1, 2, 4]] [[2, 5], [1, 3, 4]] [[3, 4], [1, 2, 5]] [[2, 4], [1, 3, 5]]
The tableau [[3, 4], [1, 2, 5]]
is of shape:
>> combinat::tableaux::shape([[3, 4], [1, 2, 5]])
[3, 2]
Its conjugate is the tableau:
>> combinat::tableaux::conjugate([[3, 4], [1, 2, 5]])
[[5], [2, 4], [1, 3]]
The shape of the conjugate is the conjugate of the shape:
>> t:=[[7], [3, 4], [1, 2, 5, 6]];
combinat::tableaux::shape(combinat::tableaux::conjugate(t));
combinat::partitions::conjugate(combinat::tableaux::shape(t))
[[7], [3, 4], [1, 2, 5, 6]] [3, 2, 1, 1] [3, 2, 1, 1]
The tableau [[3, 4], [1, 2, 5]]
corresponds to the word:
>> combinat::tableaux::toWord([[3, 4], [1, 2, 5]])
[3, 4, 1, 2, 5]
The tableau can be reconstructed back from the word:
>> combinat::tableaux::fromWord([3, 4, 1, 2, 5])
[[3, 4], [1, 2, 5]]
The row-canonical and column-canonical tableaux of shape (3,2) are:
>> combinat::tableaux::canonical([3,2]);
combinat::tableaux::columnCanonical([3,2]);
[[4, 5], [1, 2, 3]] [[2, 4], [1, 3, 5]]
Exchanging the values $2$ and $5$ in the filling
T:=[[2,5], [1,3,4]]
yields T:=[[5,2], [1,3,4]]
: this
operation stabilize the rows of T
. In general, all the
following $12$ permutations stabilize the rows of T
:
>> combinat::tableaux::rowStabilizer([[2, 5], [1, 3, 4]])
[[1, 2, 3, 4, 5], [1, 2, 4, 3, 5], [3, 2, 1, 4, 5], [3, 2, 4, 1, 5], [4, 2, 1, 3, 5], [4, 2, 3, 1, 5], [1, 5, 3, 4, 2], [1, 5, 4, 3, 2], [3, 5, 1, 4, 2], [3, 5, 4, 1, 2], [4, 5, 1, 3, 2], [4, 5, 3, 1, 2]]
Similarily, there are 4
permutations which stabilize the
columns of T
:
>> combinat::tableaux::columnStabilizer([[2, 5], [1, 3, 4]])
[[1, 2, 3, 4, 5], [2, 1, 3, 4, 5], [1, 2, 5, 4, 3], [2, 1, 5, 4, 3]]
To compute the cocharge of the tableau [[3, 5], [1, 2, 4]]
,
we compute the indexes:
>> combinat::tableaux::indexFilling([[3, 5], [1, 2, 4]])
[[1, 2], [0, 0, 1]]
The cocharge is their sum:
>> combinat::tableaux::cocharge([[3, 5], [1, 2, 4]])
4
To insert a word in a tableau, we compute:
>> combinat::tableaux::insertWord([[3],[1,2,4]],[5,1]);
[[3], [2], [1, 1, 4, 5]]
To get the two tableaux arising from the insertion of a word in the Robinson-Schensted correspondence, we compute:
>> combinat::tableaux::schensted([1, 3, 5, 2, 4]);
[[[3, 5], [1, 2, 4]], [[4, 5], [1, 2, 3]]]
Conversely, starting from two tableaux, one recovers the word they correspond to, by using:
>> combinat::tableaux::invSchensted([[3, 5], [1, 2, 4]], [[4, 5], [1, 2, 3]]);
[1, 3, 5, 2, 4]
Ax::systemRep
MuPAD Combinat, an open source algebraic combinatorics package