[Previous] [Next] [Contents]

## `combinat::tableaux` -- Young tableaux

#### Introduction

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

#### 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 `[[9],[3,4,6],[1,2,5,7,8]]`.

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

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

- 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. Whis those two tableaux of the same shape, the Schensted algorithm is a bijection, known as the Robinson-Schensted correspondence.

#### Categories

`Cat::CombinatorialClass`

#### Related Domains

`combinat::partitions`

#### Entries

domtype

The MuPAD domainused to represent tableaux: `DOM_LIST`.

typeStandard

The MuPAD type used to represent standard tableaux.

#### Method isA: test if an object is a tableau

- `isA(tableau T <, partition p>)`

- Returns whether T is a tableau or not.
- If the optional argument is present, returns whether `T` is a tableau of shape `p` or not.

#### Method isAStandard: test if an object is a standard tableau

- `isAStandard(tableau T <, partition p>)`

- Returns whether `T` is a standard tableau or not.
- If the optional argument is present, returns whether `T` is a standard tableau of shape `p` or not.

#### Method shape: the shape of a tableau

- `shape(tableau T)`

- Returns the shape of the tableau `T`.

#### Method toWord: natural reading of a tableau

- `toWord(tableau T)`

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

#### Method fromWord: tableau from its natural reading

- `fromWord(word w)`

- Returns the list of increasing subsequences of `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.

#### Method fromShapeAndWord: tableau from its shape and natural reading

- `fromShapeAndWord(partition shape, word w)`

- Returns the filling of the shape `shape` whose natural reading is the word `w`. Be careful: the result is not necessarily a tableau.

#### Method count: number of standard tableaux

- `count(partition p)`

- Returns the number of standard tableaux of shape `p`. We make use of the hook-length formula.

#### Method list: list of the standard tableaux

- `list(partition p)`

- Returns the list of the standard tableaux of shape `p`.

#### Method generator: generator for standard tableaux

- `generator(partition p)`

- Returns a generator for the standard tableaux of shape `p`.

#### Method conjugate: conjugate of a filling

- `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.

#### Method canonical: canonical standard tableau

- `canonical(partition p)`

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

#### Method columnCanonical: column canonical standard tableau

- `columnCanonical(partition p)`

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

#### Method rowStabilizer: row stabilizer of a standard filling

- `rowStabilizer(standard filling t)`

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

#### Method columnStabilizer: column stabilizer of a standard filling

- `columnStabilizer(standard filling t)`

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

#### Method indexFilling: index filling of a standard tableau

- `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.

#### Method cocharge: cocharge of a standard tableau

- `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.

#### Method insertWord: insertion of a word in a tableau

- `insertWord(tableau t, word w)`

- Returns the result of the insertion by Schented algorithm of `w` in `t`.

#### Method schensted: Robinson-Schensted correspondence

- `schensted(word w)`

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

#### Method invSchensted: reverse Robinson-Schensted correspondence

- `invSchensted(semi-standard tableau t1, standard tableau t2)`

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

#### Example 1

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

#### Example 2

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]]

#### Example 3

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]

#### Example 4

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]]

#### Example 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]]

#### Example 6

`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]]

#### Example 7

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

#### Example 8

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]

#### Super-Domain

`Dom::BaseDomain`

#### Axioms

`Ax::systemRep`

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package