[Previous] [Next] [Contents]

combinat::tableaux -- Young tableaux

Introduction

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

Details

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

Method isAStandard: test if an object is a standard tableau

Method shape: the shape of a tableau

Method toWord: natural reading of a tableau

Method fromWord: tableau from its natural reading

Method fromShapeAndWord: tableau from its shape and natural reading

Method count: number of standard tableaux

Method list: list of the standard tableaux

Method generator: generator for standard tableaux

Method conjugate: conjugate of a filling

Method canonical: canonical standard tableau

Method columnCanonical: column canonical standard tableau

Method rowStabilizer: row stabilizer of a standard filling

Method columnStabilizer: column stabilizer of a standard filling

Method indexFilling: index filling of a standard tableau

Method cocharge: cocharge of a standard tableau

Method insertWord: insertion of a word in a tableau

Method schensted: Robinson-Schensted correspondence

Method invSchensted: reverse Robinson-Schensted correspondence

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