|
The tableaux module in Magma is loosely based on the
computational algebra system SYMMETRICA developed by
Adalbert Kerber and Axel Kohnert [KKL92].
The main reference for the theory of this section is "Young Tableaux" by
William Fulton [Ful97].
A Young diagram, or Ferrers diagram, is a collection of
boxes, or cells, arranged in left-justified
rows, with a weakly decreasing number of cells in each row. Listing the number
of cells in each row gives a partition (its shape) of n,
where n is the total number of cells in the diagram.
Conversely, each partition corresponds to a unique
Young diagram. A numbering of a Young diagram is an assignment of
a positive integer to
each box.
More generally a numbering can be done using any ordered set of labels,
in Magma this means the generators
of some ordered monoid, (see section Words).
A Young tableau, or simply tableau, is a numbering
of a Young diagram which has
(i) weakly increasing entries across each row, and (ii) strictly increasing
entries down each column.
These tableaux form a monoid with respect to a multiplication which
may be defined in either of
two ways, Schensted's "bumping" row insertion, or Schützenberger's
"sliding" jeu de taquin, (see [Ful97] for full
details).
A tableau monoid is constructed from an ordered monoid (see section
Words), the generators of the ordered monoid
comprising the tableau labels.
A tableau monoid and a plactic monoid derived from the same
ordered monoid are in fact isomorphic to one another.
Flipping a diagram over its main diagonal gives the conjugate
diagram, its shape being the ConjugatePartition
of the original shape.
A skew diagram or skew shape is the diagram obtained
by deleting a smaller Young diagram from inside a larger one. A
skew tableau is a numbering on a skew diagram obeying the same
restrictions on its entries.
Let O be an ordered monoid, elements of O are expressed as
products of its generators.
The generators of O can be used as the set of labels
for a family of tableaux M, called a tableau monoid.
A tableau monoid has only one defining characteristic, the ordered
monoid which specifies its labels.
The most important tableau monoid is the one defined over the
set of all positive integers.
TableauMonoid(P) : MonPlc -> MonTbl
Given an ordered monoid O or a plactic monoid P, (in which case
let O be the ordered monoid on which P is based),
then return the tableau monoid of tableaux whose labels are the
generators of O.
Return the tableau monoid over the positive integers.
Given a tableau monoid M, return the ordered monoid from which M
gets its labels.
We create the tableau monoid over the positive integers.
We take a word in the associated ordered monoid and look at its image
in the tableau monoid.
> M := TableauIntegerMonoid();
> M;
Monoid of Tableaux labelled by the generators of:
The monoid of words over the positive integers
>
> w := OrderedMonoid(M) ! [3,6,2,8,3,9,1];
> w;
3 6 2 8 3 9 1
> M ! w;
Tableau of shape: 4 2 1
1 3 8 9
2 6
3
We create a tableau monoid over a finite set of labels, and look
at the image of a word.
> O<x,y,z> := OrderedMonoid(3);
> M := TableauMonoid(O);
> M;
Monoid of Tableaux labelled by the generators of:
The monoid of words over 3 generators: x y z
>
> M ! (z*y*x*z*y*y*x*y*x*z);
Tableau of shape: 5 3 2
x x x y z
y y y
z z
Tableaux are created from the words of some ordered monoid.
For tableaux over the positive integers, the rows can be input directly as
sequences. Words
can be used to exactly specify the rows of a tableau, or
an entire word can be mapped to a tableau using row insertion.
Given a sequence of sequences of non-negative integers Q,
return the tableau with
the elements of Q as its rows. Zeroes will indicate skew
entries.
The resulting tableau must have weakly increasing rows
and strictly increasing
columns.
Given a sequence Q of words from some ordered monoid, return the
(non-skew) tableau with the words of Q as its rows.
The resulting tableau must have weakly increasing rows
and strictly increasing
columns.
Given a sequence of nonnegative integers S which is a partition,
and a sequence of sequences of positive integers Q.
Create a skew tableau with skew (inner) shape given by the partition S,
and the non-skew part of each row being given by the entries
of Q.
The resulting tableau must have weakly increasing rows and strictly
increasing columns.
Given a sequence of nonnegative integers S which is a partition,
and a sequence Q of words from some ordered monoid.
Create a skew tableau with skew (inner) shape given by the partition S,
and the non-skew part of each row being given by the words
of Q.
The resulting tableau must have weakly increasing rows and strictly
increasing columns.
WordToTableau(u) : MonPlcElt -> Tbl
Given a word w from an ordered monoid,
return the tableau obtained by row inserting the entries of w
(from the left) into the empty tableau.
If given an element u of a plactic monoid, any word of its
Knuth equivalence class is used.
This map is invariant under Knuth equivalence and so is well defined
for elements of the plactic monoid.
It is a surjective homomorphism from the ordered
monoid to the tableau monoid, and an isomorphism from the plactic monoid
to the tableau monoid.
Given a tableau monoid M and a word w from its associated ordered
monoid, return the tableau corresponding to w through row insertion.
Given a tableau monoid M and an element u from a plactic monoid
associated with the same ordered
monoid as M, return the tableau corresponding to u through row insertion.
Given the tableau monoid M over the positive integers,
and a sequence of positive integers, return the tableau corresponding
to the word
i1 * ... * in.
Given the tableau monoid M over the positive integers,
and a sequence of sequences of non-negative integers Q,
return the tableau with
the elements of Q as its rows. Zeroes will indicate skew
entries.
The resulting tableau must have weakly increasing rows
and strictly increasing
columns.
Given a tableau monoid M, and a sequence Q of words from
its associated ordered monoid, return the
(non-skew) tableau with the words of Q as its rows.
The resulting tableau must have weakly increasing rows
and strictly increasing
columns.
We create a tableau over the positive integers in two ways.
First we input its rows explicitly, then we use a single word which
specifies the tableau.
We also create a skew tableau by using zero entries in a sequence
of sequences.
> O := OrderedIntegerMonoid();
>
> T := Tableau( [ [2,5,5,6], [5,7,9,9], [6,9] ]);
> T;
Tableau of shape: 4 4 2
2 5 5 6
5 7 9 9
6 9
> WordToTableau( O ! [6,9,5,7,9,9,2,5,5,6] );
Tableau of shape: 4 4 2
2 5 5 6
5 7 9 9
6 9
> Tableau([ [0,0,0,3,4,5], [0,1,2,4], [1,6] ]);
Skew tableau of shape: 6 4 2 / 3 1
0 0 0 3 4 5
0 1 2 4
1 6
We create a skew tableau in a tableau monoid with finitely many labels.
> O<a,b,c,d> := OrderedMonoid(4);
> T := Tableau( [3,2] , [ a*a*b*d, b*d*d, a*b]);
> T;
Skew tableau of shape: 7 5 2 / 3 2
0 0 0 a a b d
0 0 b d d
a b
We create the ordered, plactic and tableau monoids each over the
positive integers, and examine the natural maps between them.
> O := OrderedIntegerMonoid();
> P := PlacticIntegerMonoid();
> M := TableauIntegerMonoid();
> w1 := O ! [4,6,2,6,9,6,2,2,1,7];
> w2 := O ! [9,4,2,1,6,2,6,2,6,7];
> w1 eq w2;
false
> IsKnuthEquivalent(w1,w2);
true
Knuth equivalence implies equality for the image in both the plactic
and tableau monoids.
> (P!w1) eq (P!w2);
true
> P!w1;
9 4 2 6 6 1 2 2 6 7
>
> (M!w1) eq (M!w2);
true
> M!w1;
Tableau of shape: 5 3 1 1
1 2 2 6 7
2 6 6
4
9
The plactic and tableau monoids are isomorphic. We confirm that the natural
image of an equivalence class from the plactic monoid is the same
as the natural images of its member words.
> M!w1 eq M ! (P!w1);
true
Multiple tableaux may be created
corresponding to specified parameters.
StandardTableaux(M, P) : MonTbl, SeqEnum[RngIntElt] -> SetEnum
Returns the set of all standard tableau from the tableau monoid M of
shape P, which is a partition.
If a tableau monoid M is not specified then the monoid over
the positive integers is used. If M is specified then it must
contain enough labels to fill the shape P (i.e., more than Weight(P)).
StandardTableauxOfWeight(M, n) : MonTbl, RngIntElt -> SetEnum
Returns the set of all standard tableau from the tableau monoid M and
of weight n, which is a positive
integer.
If a tableau monoid M is not specified then the monoid over
the positive integers is used. If M is specified then it must
contain at least n labels.
TableauxOfShape(M, S, m) : MonTbl, SeqEnum[RngIntElt], RngIntElt -> SetEnum
Given a tableau monoid M, a sequence of positive integers S
which is a partition, and
a positive integer m, then return the set of all tableau of shape S which
use only the first m labels of the tableau monoid M.
If a tableau monoid M is not specified then the monoid over
the positive integers is used. If M is specified then it must
contain at least m labels.
TableauxOnShapeWithContent(M, S, C) : MonTbl, SeqEnum[RngIntElt], SeqEnum[RngIntElt] -> SetEnum
Given a tableau monoid M, a sequence of positive integers S
which is a partition, and
a sequence of non-negative integers C, then return the set
of all tableau from M having shape S and
content C (see section Properties for definition
of content).
If C prescribes fewer cells than would completely fill
the shape S, then the tableau
within the given shape is returned.
If a tableau monoid M is not specified then the monoid over
the positive integers is used. If M is specified then it must have
at least as many labels as C has entries.
TableauxWithContent(M, C) : MonTbl, SeqEnum[RngIntElt] -> SetEnum
Given a tableau monoid M, and a sequence of non-negative integers C,
return the set of all tableau from M with content C
(see section Properties for definition
of content).
If a tableau monoid M is not specified then the monoid over
the positive integers is used. If M is specified then it must have
at least as many labels as C has entries.
We create all tableaux of a given shape, then check that the number
of tableaux created agrees with the combinatorical result.
> P := [ 3, 2];
> S := StandardTableaux( P );
> S;
{ Tableau of shape: 3 2
1 2 3
4 5, Tableau of shape: 3 2
1 3 4
2 5, Tableau of shape: 3 2
1 3 5
2 4, Tableau of shape: 3 2
1 2 5
3 4, Tableau of shape: 3 2
1 2 4
3 5 }
>
> #S eq NumberOfStandardTableaux( P );
true
We create all tableau over the ordered generators a, b, c, d which
have shape [4, 2] and exactly two a's, one b, two c's and one d.
There is in fact four of them.
> O<a,b,c,d> := OrderedMonoid(4);
> M := TableauMonoid(O);
> TableauxOnShapeWithContent( M, [4,2], [2,1,2,1]);
{ Tableau of shape: 4 2
a a c c
b d , Tableau of shape: 4 2
a a b c
c d , Tableau of shape: 4 2
a a b d
c c , Tableau of shape: 4 2
a a c d
b c }
The functions in this section are based on ideas from [GNW84].
RandomHookWalk(t, i, j) : Tbl, RngIntElt, RngIntElt -> RngIntElt, RngIntElt
A random hook walk is an essential tool for the creation of random tableau.
The hook of a cell on a Young diagram is the cells
to the right and below its position. The Young diagram is specified
by either the sequence of positive integers P which is a partition,
or the tableau t.
Given positive integers i and j such that (i, j) lies on the shape,
the walk proceeds as follows.
Starting from the specified (i, j)-th cell,
move to another cell chosen at random from its hook.
Repeat this
process until a outside corner of the Young diagram is reached,
and return the two integers representing the coordinates of this final cell.
RandomTableau(M, S) : MonTbl, SeqEnum[RngIntElt] -> Tbl
Given a tableau monoid M, and a sequence of positive integers
S which is a partition,
return a random standard tableau from M of shape S.
If a tableau monoid M is not specified then the monoid over
the positive integers is used. If M is specified then it must
contain enough labels to fill the shape S (i.e., more than Weight(S)).
RandomTableau(M, n) : MonTbl, RngIntElt -> Tbl
Given a tableau monoid M, and a positive integer n,
return a (not completely) random standard tableau of weight n.
The probability of any specific tableau of shape S being returned is
NS/n!, where NS is the number of standard tableaux of shape S.
So tableaux on more populous
shapes are more likely to occur.
If a tableau monoid M is not specified then the monoid over
the positive integers is used. If M is specified then it must
contain at least n labels.
We numerically test the random creation of tableau of a given shape,
by calculating the average percentage difference in the number
of each tableau created. We find it to be less than one percent.
> P := [4,3,2];
> Runs := 10000;
>
> S := Setseq( StandardTableaux( P ) );
> Count := [0: i in [1..#S]];
>
> for k in [1..Runs] do
> T := RandomTableau( P );
> i := Index(S,T);
> Count[i] +:= 1;
> end for;
>
> Average := Runs/#S;
> Diff := [RealField(2) | Abs( (Count[i] - Average)/Average )
> : i in [1..#Count]];
>
> AvgDiff := (&+ Diff)/#Diff;
> AvgDiff;
0.006
OuterShape(t) : Tbl -> SeqEnum
The (outer) shape of a tableau t is the sequence of positive integers
denoting the (decreasing) row lengths of its Young Diagram, which
results in a partition.
InnerShape(t) : Tbl -> SeqEnum[RngIntElt]
The Young diagram of a skew tableau t has a smaller Young diagram
inside of it deleted. The skew, or inner, shape of a skew tableau is
the sequence of positive integers denoting the (decreasing) row lengths
of this deleted diagram, which results in a partition.
A non-skew tableau is a special case of a skew tableau, whose
skew shape is simply the null sequence.
Trailing zeroes are added to the inner shape of t to give it the same
length as the outer shape of t.
Given two sequences of integers, P1 and P2, which are partitions,
return true if the Young diagram of P1 covers the Young diagram of P2.
Given a sequence of integers P which is a partition, return the
partition corresponding to the conjugate Young diagram of P
(see section Tableaux for a full description).
Given a tableau t, return the positive integer which is
the number of (non-skew) cells in its Young Diagram.
Given a tableau t, return the positive integer which is
the number of skew cells in its Young Diagram.
Given a tableau t, return a positive integer which is its number of rows.
Given a tableau t, return a positive integer which is its
number of skewed rows.
Given a tableau t, return the non-skewed entries of the ith row
as a word of an ordered monoid.
Given a tableau t, return a sequence of words from an ordered monoid
which are the non-skewed entries of its rows.
Given a tableau t, return the non-skewed entries of the jth column
as a word of an ordered monoid.
Given a tableau t, return a sequence of words from an ordered monoid
which are the non-skewed entries of its columns.
Given a tableau t,
return the length of the skewed portion of the ith row
(zero if no
skewed portion).
Given a tableau t,
return the length of the skewed portion of the jth column
(zero if no
skewed portion).
Given a tableau t and a positive integer i,
return the index of the first non-skew entry of the ith row of t.
If the row
has no non-skew entries then the index will be one greater than the length
of the row (i.e., out of bounds).
RowLength(t, i) : Tbl,RngIntElt -> RngIntElt
Given a tableau t and a positive integer i,
return the index of the last entry of the ith row of t,
which is the length of the ith row.
Given a tableau t and a positive integer j,
return the index of the first non-skew entry of the jth column of t.
If the column
has no non-skew entries then the index will be one greater than the length
of the column (i.e., out of bounds).
ColumnLength(t, j): Tbl,RngIntElt -> RnfIntElt
Given a tableau t and a positive integer j,
return the index of the last entry in the jth column of t,
which is the length of the jth column.
Given a skew tableau, we access a number of its structural
properties.
> T := Tableau( [3,3,2] , [ [4, 6 ] ,[5, 9], [1, 8] ]);
> T;
Skew tableau of shape: 5 5 4 / 3 3 2
0 0 0 4 6
0 0 0 5 9
0 0 1 8
> Shape(T);
[ 5, 5, 4 ]
> Weight(T);
6
> SkewWeight(T);
8
> NumberOfRows(T);
3
> NumberOfSkewRows(T);
3
> RowSkewLength(T, 2);
3
> Row(T, 2);
5 9
> ColumnSkewLength(T, 3);
2
> Column(T, 3);
1
HookLength(P, i, j) : SeqEnum[RngIntElt],RngIntElt,RngIntElt -> RngIntElt
The hook of a cell on a Young diagram comprises the cells
to the right and below its position. The Young diagram is specified
by either the sequence of positive integers P which is a partition
or the tableau t.
The number of cells contained in a hook is its length.
For positive integers i and j such that (i, j) is the co-ordinates of a
cell lying on the specified Young diagram, a positive integer is returned
which is the length of the hook of that cell.
Given a tableau t, return a sequence of non-negative integers
which is its content.
The content of t is
such that its ith value denotes the number of times the
ith label occurs in t.
RowWord(t) : Tbl -> MonOrdElt
Given a tableau t, its row word is formed by
reading its entries from left to right, bottom to top.
The result is a word of an ordered monoid.
Given a tableau t, its column word is formed by
reading its labels from bottom to top, left to right.
The result is a word of an ordered monoid.
Given a tableau t of weight n, then t is standard if and only if
its entries are exactly the first n labels of its parent monoid.
So t is standard if and only if
it has a content of the form [1, 1, ..., 1].
Returns true if the tableau t is a skew tableau.
Given a tableau t, then it is a Littlewood--Richardson tableau if
the content of t forms a reverse lattice word, (see section
Words
for a definition of a reverse lattice word).
We create a tableau which is not standard. Examining its
content shows a simple to way to transform it into a standard tableau.
> O := OrderedIntegerMonoid();
> T := WordToTableau( O ! [8,1,7,3,6,2,5,9] );
> T;
Tableau of shape: 4 2 1 1
1 2 5 9
3 6
7
8
> Content(T);
[ 1, 1, 1, 0, 1, 1, 1, 1, 1 ]
> IsStandard(T);
false
>
> RowInsert(~T, 4);
> T;
Tableau of shape: 4 2 1 1 1
1 2 4 9
3 5
6
7
8
> Content(T);
[ 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
> IsStandard(T);
true
Given a tableau, check that the row and column words are Knuth
equivalent.
> T := Tableau( [2, 2], [ [1,2,3], [4,6,6], [1,5], [2,6] ]);
> T;
Skew tableau of shape: 5 5 2 2 / 2 2
0 0 1 2 3
0 0 4 6 6
1 5
2 6
>
> RW := RowWord(T);
> RW;
2 6 1 5 4 6 6 1 2 3
> CW := ColumnWord(T);
> CW;
2 1 6 5 4 1 6 2 6 3
> IsKnuthEquivalent(RW, CW);
true
Several operations exist to manipulate tableaux
and allow them to interact.
Given two tableaux t1 and t2, return true if they are equal.
Given two tableaux t1 and t2, return another tableau which is
their product. The product of two tableaux can be defined using
either row insertion or jeu de taquin.
The DiagonalSum of two tableau t1 and t2 is formed
by first building a rectangle
of empty cells, with the same number of columns as t1 and the same
number of rows as t2. Then t1 is attached below the rectangle and
t2 attached to right of it.
Given a tableau t with strictly increasing rows, the rows and columns
of t are transposed to form a new tableau on the conjugate Young diagram.
JeuDeTaquin(t, i, j) : Tbl, RngIntElt, RngIntElt -> Tbl
Given a skew tableau t, and the co-ordinates (i, j) which must be a skew cell
that is an inside corner (a corner on the skew shape of t).
The skewed (i, j)th cell is removed
using jeu de taquin.
JeuDeTaquin(t) : Tbl -> Tbl
Rectify(~t) : Tbl ->
Rectify(t) : Tbl -> Tbl
Given a tableau t, remove all skewed cells successively using
jeu de taquin.
InverseJeuDeTaquin(t, i, j) : Tbl, RngIntElt, RngIntElt -> Tbl
Given a tableau t, and co-ordinates (i, j) which must lie on the
outside of t resulting in a new and valid shape.
A new skew tableau with skew degree one higher than t is created.
This is achieved by adding a new skew cell in the (i, j)th position,
then performing jeu de taquin in reverse, which moves the new entry
to create a valid skew tableau.
RowInsert(t, w) : Tbl, MonOrdElt -> Tbl
RowInsert(~t, u) : Tbl, MonPlcElt ->
RowInsert(t, u) : Tbl, MonPlcElt -> Tbl
Given a tableau t and a word w from the same ordered monoid that
t is associated to, insert w into t using Schensted's
row insertion algorithm.
If given an element u of a plactic monoid, any word of its
Knuth equivalence class is used.
This map is invariant under Knuth equivalence and so is well defined
for elements of the plactic monoid.
RowInsert(t, x) : Tbl, RngIntElt -> Tbl
Given a tableau t over the positive integers, and a positive integer
x, insert x into t using the Schensted's
row insertion algorithm.
InverseRowInsert(t, i, j) : Tbl, RngIntElt, RngIntElt -> Tbl, MonOrdElt
Given a tableau t and positive integers i and j such that
(i, j) corresponds to an outside corner cell of the
tableau t, then the row insertion algorithm is applied in reverse
to remove the specified entry.
In the functional form, both the generated tableau and the
value of the removed entry as a word of an ordered monoid are
returned.
The order with which the skew entries of a skew tableau are removed
using jeu de taquin is irrelevant to the final tableau produced.
We give an example of this.
> T := Tableau([2,1], [ [2], [3,4] ,[3] ]);
> T1 := T;
> T;
Skew tableau of shape: 3 3 1 / 2 1
0 0 2
0 3 4
3
>
> JeuDeTaquin(~T, 1, 2); T;
Skew tableau of shape: 3 2 1 / 1 1
0 2 4
0 3
3
> JeuDeTaquin(~T, 2, 1); T;
Skew tableau of shape: 3 2 / 1
0 2 4
3 3
> JeuDeTaquin(~T, 1, 1); T;
Tableau of shape: 3 1
2 3 4
3
>
> JeuDeTaquin(~T1, 2, 1); T1;
Skew tableau of shape: 3 3 / 2
0 0 2
3 3 4
> JeuDeTaquin(~T1, 1, 2); T1;
Skew tableau of shape: 3 2 / 1
0 2 4
3 3
> JeuDeTaquin(~T1, 1, 1); T1;
Tableau of shape: 3 1
2 3 4
3
>
> T eq T1;
true
We manually compare the two different methods of multiplying
tableau.
> O<a,b,c,d,e,f,g,h> := OrderedMonoid(8);
> T1 := Tableau( [ a*c*f, d*g]);
> T2 := Tableau( [ b*b*e*f, d*g*h]);
First using row insert,
> w := Word(T2);
> w;
d g h b b e f
> Res1 := RowInsert(T1, w);
> Res1;
Tableau of shape: 5 4 2 1
a b b e f
c d g h
d f
g
and then using JeuDeTaquin.
> Res2 := DiagonalSum(T1, T2);
> Res2;
Skew tableau of shape: 7 6 3 2 / 3 3
0 0 0 b b e f
0 0 0 d g h
a c f
d g
> Rectify(~Res2);
> Res2;
Tableau of shape: 5 4 2 1
a b b e f
c d g h
d f
g
Now we check our results.
> Res1 eq Res2;
true
> Res1 eq (T1*T2);
true
While the map from the plactic monoid to tableaux is an isomorphism,
many different words from the original ordered
monoid map to the
same tableau. However a bijective map exists between
an ordered monoid and pairs of tableau of the same shape,
the second of which
being a standard tableau. This is known as the Robinson
correspondence.
By removing the restriction that the second tableau be standard,
this correspondence is extended further to
a bijective map with all matrices with non-negative integers.
This is known as the Robinson-Schensted-Knuth (RSK) correspondence.
This latter correspondence can also be made to all lexicographically
ordered pairs of words (both having the same length).
LexicographicalOrdering(w1, w2) : MonOrdElt, MonOrdElt -> MonOrdElt, MonOrdElt
Given two words w1 and w2 of the same length,
place them in increasing lexicographical order
(the functional version returns two new words).
Lexicographical ordering on the pairs (w1[i], w2[i]) is determined
primarily by the comparison w2[i] < w2[j],
but if w2[i] = w2[j] then the comparison w1[i] < w1[j]
is taken into account.
Given two words w1 and w2, return
true if the pairs (w1[i], w2[i]) are ordered according to the
ordering described in LexicographicalOrdering.
Given a word w, use the bijective map described by the
Robinson-Schensted-Knuth correspondence to return
two tableau t1 and t2.
The first tableau, t1, will be labelled by the entries of w, while t2
is a standard tableau over the positive integers.
The map described by the correspondence is as follows. Map the word w
to t1 by row inserting its entries into the empty tableau, (as is done
in WordToTableau). As t1 is being generated, the insertion
tableau t2 is built simultaneously.
As w[k] is inserted into t1, an additional cell is added to its shape.
A new cell is added to t2 in exactly the same place, and it is
labelled with
the integer k.
Given a pair of tableaux t1, t2, of the same shape,
where t2 is over the
positive integers, return the preimage of t1 and t2
using the bijective map described by
the Robinson-Schensted-Knuth correspondence.
The result is
returned as a single word of the ordered monoid of t1, as described in
the single word version of RSKCorrespondence.
Given two lexicographically ordered words w1 and w2 of the same length,
where w2 must be over the positive
integers, use the bijective map described by the
Robinson-Schensted-Knuth correspondence to return
two tableau t1 and t2.
The first tableau, t1, will be labelled by the entries of w1, while t2
will be labelled by the entries of w2.
The map described by the correspondence is as follows. Map the word w1
to t1 by row inserting its entries into the empty tableau, (as is done
in WordToTableau). As t1 is being generated, the insertion
tableau t2 is built simultaneously.
As w[k] is inserted into t1, an additional cell is added to its shape.
A new cell is added to t2 in exactly the same place, and it is labelled with
the integer w2[k].
Given a pair of tableaux t1, t2, of the same shape,
where t2 is over the
positive integers, return the preimage of t1 and t2
using the bijective map described by
the Robinson-Schensted-Knuth correspondence.
The result is
returned as words of the ordered monoids of t1 and t2 respectively,
as described in
the double word version of RSKCorrespondence.
Given a matrix M of non-negative integers,
use the bijective map described by the
Robinson-Schensted-Knuth correspondence to return
two tableau t1 and t2 over the positive integers.
The map described by the correspondence is as follows.
Initialise two words over the positive
integers, w1 and w2, as null words.
For the (i, j)th entry of M, say mij, append i to
w1 mij times, and append j to w2 mij times.
These two words are then used in the correspondence described in
the above version of RSKCorrespondence.
Given a pair of tableaux t1, t2, of the same shape,
both over the
positive integers, return the preimage of t1 and t2
using the bijective map described by
the Robinson-Schensted-Knuth correspondence.
The result is a matrix of non-negative integers,
as described in
the matrix version of RSKCorrespondence.
We take two words from the ordered monoid over the positive integers.
Although they correspond to the same tableau under the natural
mapping into the tableau monoid, we show they have
a different image under the RSK correspondence.
That is, they have different
insertion tableaux.
> O := OrderedIntegerMonoid();
> M := TableauMonoid(O);
> a := O ! [4,7,2,8,4,9,2];
> a;
4 7 2 8 4 9 2
> b := O ! [7,4,2,4,2,8,9];
> b;
7 4 2 4 2 8 9
Now we will see that a and b have the same image in the tableau monoid,
but that they are distinguished under the RSK correspondence.
> (M!a) eq (M!b);
true
> Ta1, Ta2 := RSKCorrespondence(a);
> Tb1, Tb2 := RSKCorrespondence(b);
> Ta1 eq Tb1;
true
> Ta2 eq Tb2;
false
> Ta2;
Tableau of shape: 4 2 1
1 2 4 6
3 5
7
> Tb2;
Tableau of shape: 4 2 1
1 4 6 7
2 5
3
To check that the map is indeed bijective we find a and b as
the pre-images of the created tableaux.
> InverseRSKCorrespondenceSingleWord(Ta1,Ta2 );
4 7 2 8 4 9 2
> InverseRSKCorrespondenceSingleWord(Tb1,Tb2 );
7 4 2 4 2 8 9
We apply the RSK correspondence to two arbitrary words, the
first from a finitely generated ordered monoid.
The second word must always be over the positive integers.
The first step is to put them
into lexicographical order.
> O1<a,b,c,d,e,f> := OrderedMonoid(6);
> O2 := OrderedIntegerMonoid();
>
> w1 := e*a*e*b*f*d*a;
> w2 := O2 ! [3,8,2,8,3,3,6];
> LexicographicalOrdering(~w1, ~w2);
> w1, w2;
e d e f a a b 2 3 3 3 6 8 8
Now we use the correspondence,
> T1, T2 := RSKCorrespondence(w1, w2);
> T1;
Tableau of shape: 3 3 1
a a b
d e f
e
> T2;
Tableau of shape: 3 3 1
2 3 3
3 8 8
6
and check that the inverse is correct.
> InverseRSKCorrespondenceDoubleWord(T1, T2);
e d e f a a b 2 3 3 3 6 8 8
We give an example of the bijective map provided by the RSK correspondence
between matrices of non-negative integers and pairs of tableaux
of the same shape.
> M := Matrix(2,3,[0,0,2,3,1,2]);
> M;
[0 0 2]
[3 1 2]
> T1, T2 := RSKCorrespondence(M);
> T1;
Tableau of shape: 6 2
1 1 1 2 3 3
3 3
> T2;
Tableau of shape: 6 2
1 1 2 2 2 2
2 2
> InverseRSKCorrespondenceMatrix(T1, T2);
[0 0 2]
[3 1 2]
Looking now at preimage of the tableaux in the double word format,
the (i, j) co-ordinates of entries of M can clearly be seen with the
correct multiplicities.
> wj, wi := InverseRSKCorrespondenceDoubleWord(T1, T2);
> wi;
1 1 2 2 2 2 2 2
> wj;
3 3 1 1 1 2 3 3
We illustrate the remarkable property that a permutation p (in image
notation) corresponds to the tableaux pair (T1, T2) if and only if
the inverse permutation p - 1 corresponds to the tableaux pair
(T2, T1).
> O := OrderedIntegerMonoid();
> n := Random([1..100]);
> G := SymmetricGroup(n);
> p := Random(G);
>
> T1, T2 := RSKCorrespondence( O ! Eltseq(p) );
>
> p1 := InverseRSKCorrespondenceSingleWord( T2, T1);
> p1 := G ! Eltseq(p1);
>
> p1 eq p^-1;
true
Given a sequence of positive integers P which is a partition,
return the number of standard tableaux of shape P.
This is the same as the number of
Knuth equivalent words corresponding to each standard tableaux
of shape P.
Given a positive integer n, return
the number of standard tableaux having
weight n.
Given a sequence of positive integers P which is a partition,
return the number of tableau of shape P
with entries from [1, ..., m].
Given a sequence of positive integers S forming a partition,
and a sequence of non-negative integers C,
return the number of tableau having shape S and content C.
If C prescribes fewer cells than would completely fill
the shape S, then the number of tableau
within the given shape is returned.
There is a correspondence between the number of standard
tableaux on a given shape, and the number of words associated with
each of those tableaux.
We manually count the number of words corresponding to a
specific standard tableau,
and show that this is equal to the number of standard tableaux
on that shape.
> O := OrderedIntegerMonoid();
> T := Tableau( [ [ 1, 2, 3, 4, 7],
> [ 5, 8],
> [ 6] ] );
> T;
Tableau of shape: 5 2 1
1 2 3 4 7
5 8
6
>
> n := Weight(T);
> G := SymmetricGroup(n);
> S := [1..n];
>
> Count := 0;
> for p in G do
> T1 := WordToTableau( O ! (S^p) );
> if T1 eq T then
> Count +:= 1;
> end if;
> end for;
>
> Count;
64
> NumberOfStandardTableaux( Shape(T) );
64
If a tableaux is constructed of the shape [1, 1, 1, ..., 1] then
the entries must be strictly increasing, hence non-repeating. So
for such a tableau of length n
on an alphabet of m symbols, each subset of n symbols will
correspond to one single distinct tableau. So the number of tableau will
be (m choose n).
> m := Random(1,50);
> n := Random(1,m);
>
> Shape := [ 1 : i in [1..n] ];
> Binomial(m,n) eq NumberOfTableauxOnAlphabet(Shape, m);
true
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|