combinat::tableaux – Young tableaux

The library combinat::tableaux provides functions for counting, generating, and manipulating Young tableaux.

→ Examples

Creating Elements

combinat::tableaux(filling)

Parameters:

Superdomain

Dom::BaseDomain

Categories

Cat::CombinatorialClassWith2DBoxedRepresentation, Cat::GradedCombinatorialClass

See Also:

combinat::partitions, combinat::words

Details:

• Let 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.

• A tableau is encoded by the list of its rows, from top to bottom. For example, the above tableau is encoded by its filling, that is: [[9],[3,4,6],[1,2,5,7,8]].

• The word related to a tableau is the left-to-right reading of its encoding, that is: [4,2,3,3,1,1,2,2,3] and [9,3,4,6,1,2,5,7,8] in the previous examples.

• The evaluation of a tableau is the evaluation of its associated word, that is: [2,3,3,1] and [1,1,1,1,1,1,1,1,1] for the examples above. Sometimes the evaluation is given in its partition form, see combinat::words::evaluationPartition.

• The coordinate system related to a tableau applies from top to bottom and from left to right, so the corners of the tableaux above are are [[1,1], [2,3], [3,5]] and the heights are [1,2,2,3,3]. Its height is obviously 3.

• There exists a formula to enumerate the number of standard tableaux of a given shape. It is the so-called hook-length formula, first discovered by Frame, Robinson, and Thrall in 1954.

• When it makes sense, most of the functions also work when the filling does not satisfy the monotonicity conditions of standard tableaux.

Entries

isA – test if an object is a tableau

combinat::tableaux::isA(tableau t)

combinat::tableaux::isA(tableau t, partition shp)

combinat::tableaux::isA(tableau t, nonnegative integer siz)

Returns whether t is a tableau or not.

If the optional argument is present, returns whether t is a tableau of shape shape or of size siz.

isAStandardTableau – test if an object is a standard tableau

combinat::tableaux::isAStandardTableau(tableau t)

combinat::tableaux::isAStandardTableau(tableau t, partition shp)

combinat::tableaux::isAStandardTableau(tableau t, nonnegative integer siz)

Returns whether t is a standard tableau or not.

If the optional argument is present, returns whether t is a standard tableau of shape shape or of size siz.

shape – the shape of a tableau

combinat::tableaux::shape(tableau t)

Returns the shape of the tableau t.

size – the size of a tableau

combinat::tableaux::size(tableau t)

Returns the size of the tableau t.

height – the height of a tableau

combinat::tableaux::height(tableau t)

Returns the height of tableau t.

corners – the corners of a tableau

combinat::tableaux::corners(tableau t)

Returns the list of the corners of tableau t.

heights – the heights of a tableau

combinat::tableaux::heights(tableau t)

Returns the list of the heights of tableau t.

toWord – natural reading of a tableau

combinat::tableaux::toWord(tableau t)

Returns the natural row reading of the tableau t, from top to bottom, and from left to right.

fromWord – tableau from its natural reading

combinat::tableaux::fromWord(word w)

Returns the list of increasing subsequences of w. Beware, 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 – tableau from its shape and natural reading

combinat::tableaux::fromShapeAndWord(partition shape, word w)

Returns the filling of the shape shape whose natural reading is the word w. Beware, the result is not necessarily a tableau.

fromEvaluation – tableau from its given evaluation

combinat::tableaux::fromEvaluation(compositions eva)

combinat::tableaux::fromEvaluation(nonnegative integer size)

Returns the tableau of evaluation eva and natural reading [length(eva),...,length(eva),...,2,..,2,1,..,1].

If the size of the tableau is given, this function returns the tableau of natural reading [size,...,2,1].

count – number of tableaux

combinat::tableaux::count(partition shape)

combinat::tableaux::count(nonnegative integer siz)

combinat::tableaux::count(partition shape, integer vector eva)

combinat::tableaux::count(nonnegative integer siz, integer vector eva)

Returns the number of standard tableaux of shape shape or of size siz. When the second argument eva is given, the function returns the number of tableaux with evaluation eva. This method uses the hook-length formula for the case of standard tableaux and counting the list of tableaux otherwise.

list – list of tableaux

combinat::tableaux::list(partition shape)

combinat::tableaux::list(nonnegative integer siz)

combinat::tableaux::list(partition shape, integer vector eva)

combinat::tableaux::list(nonnegative integer siz, integer vector eva)

Returns the list of the standard tableaux of shape shape or of size siz. When the second argument eva is given, the function returns the list of tableaux with evaluation eva.

generator – generator for tableaux

combinat::tableaux::generator(partition shape)

combinat::tableaux::generator(nonnegative integer siz)

combinat::tableaux::generator(partition shape, integer vector eva)

combinat::tableaux::generator(nonnegative integer siz, integer vector eva)

Returns a generator for the standard tableaux of shape shape or of size siz. When the second argument eva is given, the function returns a generator for the tableaux with evaluation eva.

printPretty – graphic representation of a filling

combinat::tableaux::printPretty(filling p)

Returns a graphic representation of the filling. This is the default way of printing tableaux. This method is inherited from the category Cat::CombinatorialClassWith2DBoxedRepresentation and returns a MuPAD objects of the domains output::asciiArt.

printCompact – graphic representation of a filling

combinat::tableaux::printCompact(filling p)

Same as above, but in a more compact way.

conjugate – conjugate of a filling

combinat::tableaux::conjugate(filling f)

Returns the conjugate (or transposed) of the filling f. Geometrically, this operation amounts to a reflection of the diagram with respect to the main diagonal.

canonical – canonical standard tableau

combinat::tableaux::canonical(partition shape)

Returns the row-canonical tableau of shape shape obtained by filling consecutive rows starting from the bottom.

columnCanonical – column canonical standard tableau

combinat::tableaux::columnCanonical(partition shape)

Returns the column-canonical tableau of shape shape obtained by filling consecutive columns starting from the left.

rowStabilizer – row stabilizer of a standard filling

combinat::tableaux::rowStabilizer(standard filling t)

Returns the list of permutations of values of t that stabilize the rows of t.

columnStabilizer – column stabilizer of a standard filling

combinat::tableaux::columnStabilizer(standard filling t)

Returns the list of permutations of values of t that stabilize the columns of t.

indexFilling – index filling of a standard tableau

combinat::tableaux::indexFilling(standard tableau t)

Returns the index filling of the tableau t, during the computation of the cocharge.

References: Lascoux. A and Schutzenberger M. P., (1978), "Sur une conjecture de H. O. Foulkes.", C.R. Acad. Sci. Paris (Série 1) 286A, 323-4.

See also : Macdonald I.-G., (1995), "Symmetric Functions and Hall Polynomials", Oxford Science Publication.

charge – charge of a standard tableau

combinat::tableaux::charge(standard tableau t)

Returns the charge of the tableau t.

See references for combinat::tableaux::cocharge for references.

cocharge – cocharge of a standard tableau

combinat::tableaux::cocharge(standard tableau t)

Returns the cocharge of the tableau t.

References: Lascoux. A and Schutzenberger M. P., (1978), "Sur une conjecture de H. O. Foulkes.", C.R. Acad. Sci. Paris (Série 1) 286A, 323-4.

See also : Macdonald I.-G., (1995), "Symmetric Functions and Hall Polynomials", Oxford Science Publication.

kostka – Kostka number

combinat::tableaux::kostka(partition lambda, partition mu)

Returns the Kostka number , that is the number of semi-standard tableaux of shape lambda and evaluation mu.

Coplactic operations

The coplactic operations are basically the same as the ones in combinat::words. They consist mainly in to apply the operator at the word related to the tableau.

symmetricGroupActionOnValues – action of the symmetric group over a tableau

combinat::tableaux::symmetricGroupActionOnValues(tableau t, permutation p)

Returns the result of the action of the reduced words of p over t.

crystalE – crystal operator e

combinat::tableaux::crystalE(tableau t, any type i)

Returns the result of the action of the crystal operator over t.

crystalF – crystal operator f

combinat::tableaux::crystalF(tableau t, any type i)

Returns the result of the action of the crystal operator over t.

Jeu de taquin and Schensted algorithm. Robinson-Schensted correspondence

The jeu de taquin is the name given to a graphical representation of the plactic, or Knuth, congruences by M.-P. Schützenberger, see for example M.-P. Schützenberger, "La correspondance de Robinson", Combinatoire et Représentations du Groupe Symétrique, Strasbourg (1976), Lecture Notes in Mathematics, 579, Springer (1977) pp. 59135.

C. Schensted has defined a very beautiful algorithm that inserts a word inside a Young tableau. The insertion is a recursive bumping process that inserts one letter at a time in a tableau. If this letter is greater than the last letter of the first row, then it glues itself at the end of the first row. If it is smaller than it, it replaces the left-most letter of the first row, greater than itself. This replaced letter inserts itself in the next rows of the tableau, recursively. Reference: Schensted. C., (1961), "Longest increasing and decreasing subsequences", Canad. J. Math., 13, 178–191.

The basic step of this bumping algorithm corresponds to the jeu de taquin. One can insert one letter on the right (following rows) or on the left (following colums) of the tableau. It is also possibe to extract a letter by this operation (to the left or to the right). In this case the main interest is when the letter comes from a corner of the tableau.

Following Schensted, one can get more information by memorizing in a second tableau (that will be standard) when each box of the final tableau has been created. With those two tableaux of the same shape, the Schensted algorithm is a bijection, known as the Robinson-Schensted correspondence.

schenstedInsert – insertion of a letter in a tableau

combinat::tableaux::schenstedInsert(tableau t, letter l, direction dir)

Returns the result of the insertion by Schented algorithm of a letter l in t on the direction dir.

insertWord – insertion of a word in a tableau

combinat::tableaux::insertWord(tableau t, word w)

combinat::tableaux::insertWord(tableau t, word w, direction dir)

Returns the result of the insertion by Schented algorithm of w in t, this can be done on the Left or on the Right. The Right direction is the default.

schenstedExtract – extraction of a letter in a tableau

combinat::tableaux::schenstedExtract(tableau t, nonnegative integer row, direction dir)

Returns the result of the extraction by Schented algorithm of a letter in the corner of the row row of t on the direction dir.

Error if the row has no corner.

schensted – Robinson-Schensted correspondence

combinat::tableaux::schensted(word w)

Returns the result of the insertion by the Robinson-Schensted correspondence of w. The result is a pair composed of a semi-standard tableau and a standard tableau.

invSchensted – reverse Robinson-Schensted correspondence

combinat::tableaux::invSchensted(semi-standard tableau t1, standard tableau t2)

Returns the word obtained by the reverse bijection of Robinson-Schented.

Cyclage and cocyclage

The basic cycling operation in a word is to take its first letter and to put it at the end of the word. In tableaux, we cycle letters extract from its corners and insert them in the other direction, both operations use the Schensted algorithm. This provides an order for the tableaux of a fixed evaluation, and we have then the cyclage successors of a tableau. If the directions of extraction and insertion are inverted, we have the cocyclage successors of a tableau.

This operation has restrictions such as "not to cycle the first letter of the alphabet" or "ignore the corner in the last row". See Lascoux A., Leclerc B. and Thibon J-Y., "The Plactic Monoid", in Lothaire (2002) Algebraic Combinatorics on Words. Cambridge University Press for more information.

The iteration of the successor operation provides the cyclage graph, or the cocyclage graph. The functions to generate these graphs have as result a file for the dot program, see http://www.graphviz.org/ for details, and the examples below for more information.

cyclageSucc – successors of a tableau by cyclage

combinat::tableaux::cyclageSucc(tableau t)

combinat::tableaux::cyclageSucc(compositions eva)

combinat::tableaux::cyclageSucc(tableau t, enumeration(NoLastRow, NoFirstLetter) restriction)

combinat::tableaux::cyclageSucc(compositions eva, enumeration(NoLastRow, NoFirstLetter) restriction)

Returns the succesors of the tableau t by the cyclage operation.

If the tableau is given by its evaluation, this function constructs the associated tableau (see combinat::tableaux::fromEvaluation) and then computes its successors.

The restriction argument tells not to cycle the first letter of the alphabet or to ignore the corner in the last row for the cycling operation (which is the default restriction).

cocyclageSucc – successors of a tableau by cocyclage

combinat::tableaux::cocyclageSucc(tableau t)

combinat::tableaux::cocyclageSucc(compositions eva)

combinat::tableaux::cocyclageSucc(tableau t, enumeration(NoLastRow, NoFirstLetter) restriction)

combinat::tableaux::cocyclageSucc(compositions eva, enumeration(NoLastRow, NoFirstLetter) restriction)

Returns the succesors of the tableau t by the cocyclage operation.

If the tableau is given by its evaluation, this function constructs the associated tableau (see combinat::tableaux::fromEvaluation) and then computes its successors.

The restriction argument tells not to cycle the first letter of the alphabet or to ignore the corner in the last row for the cycling operation (which is the default restriction).

cyclageGraph – cyclage graph

combinat::tableaux::cyclageGraph(tableau t)

combinat::tableaux::cyclageGraph(compositions eva)

combinat::tableaux::cyclageGraph(nonnegative integer size)

Writes the dot file of the cyclage graph of the tableau t.

If the tableau is given by its evaluation, this function constructs the graph of the cyclage of evaluation eva.

If the tableau is given by its size, this function constructs the cyclage of tableaux of size size. This graph contains all the standard tableaux of size size.

cocyclageGraph – cocyclage graph

combinat::tableaux::cocyclageGraph(tableau t)

combinat::tableaux::cocyclageGraph(compositions eva)

combinat::tableaux::cocyclageGraph(nonnegative integer size)

Writes the dot file of the cocyclage graph of the tableau t.

If the tableau is given by its evaluation, this function constructs the graph of the cocyclage of evaluation eva. This graph contains all the tableaux with this evaluation.

If the tableau is given by its size, this function constructs the cyclage of tableaux of size size. This graph contains all the standard tableaux of size size. This graph almost coincides with the cyclage graph: it has the same nodes, but inverted links.

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

Example 6:

Example 7:

Example 8:

Example 9:

Example 10: