% $Id: tableaux.tex,v 1.1.1.7 2004/10/21 15:52:51 nthiery Exp $
\begin{Mhelppage}{tableaux}{F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{novelli}{10/2003}{proofread}

\begin{MInfo}
  \eng{Young tableaux}
\end{MInfo}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting,
    generating, and manipulating Young tableaux.}
\end{MIntro}

\MKeywords{combinatorics,partition,tableau}

\begin{MDetails}
  
  \eng{Let \Mex{p} be a partition of \Mex{n}. Recall that a partition
    can be depicted by a diagram of boxes (see
    \Mup{combinat::partitions}).  Fill now the boxes with numbers.
    Such a \emph{filling} is a \emph{Young tableau}, or, shorter,
    a \emph{tableau} if the numbers in the
    boxes are non-decreasing along rows and (strictly) increasing from
    bottom to top along columns. The partition \Mex{p} is called the
    \emph{shape} of the tableau. Here is an example of tableau of
    shape \Mex{[5,3,1]}:
    \Mdmath{%
      +---+
      | 4 |
      +---+---+---+
      | 2 | 3 | 3 |
      +---+---+---+---+---+
      | 1 | 1 | 2 | 2 | 3 |
      +---+---+---+---+---+}%
    {\begin{array}{l}
        \fbox{4}\\[-1pt]
        \fbox{2}\fbox{3}\fbox{3}\\[-1pt]
        \fbox{1}\fbox{1}\fbox{2}\fbox{2}\fbox{3}\\
      \end{array}}
    Moreover, if every positive integer up to \Mpar{n} appears exactly
    once, the tableau is \emph{standard}. Here is an example of
    standard tableau of shape \Mex{[5,3,1]}:
    \Mdmath{%
      +---+
      | 9 |
      +---+---+---+
      | 3 | 4 | 6 |
      +---+---+---+---+---+
      | 1 | 2 | 5 | 7 | 8 |
      +---+---+---+---+---+}%
    {\begin{array}{l}
        \fbox{9}\\[-1pt]
        \fbox{3}\fbox{4}\fbox{6}\\[-1pt]
        \fbox{1}\fbox{2}\fbox{5}\fbox{7}\fbox{8}
      \end{array}}
    Currently, \Mup{combinat::tableaux} deals mainly with standard
    tableaux.}

    \eng{A tableau is encoded by the list of its rows, from top to
    bottom. For example, the above tableau is encoded by
    \Mex{[[9],[3,4,6],[1,2,5,7,8]]}. }

    \eng{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.}

    \eng{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.}

    \eng{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.}
\end{MDetails}

\begin{MCategories}
\Mup{Cat::CombinatorialClass}
\end{MCategories}

\MRelatedDomains{combinat::partitions}

\begin{MDomEntries}
  \MDomEntry{domtype}
     \eng{The \mupad\ domainused to represent tableaux: \Mex{DOM_LIST}.}
  \MDomEntry{typeStandard}
     \eng{The \mupad\ type used to represent standard tableaux.}
\end{MDomEntries}

\begin{MMethodDetails}{isA}
  \infoEng{test if an object is a tableau}
  \call{\Mtype{tableau} T\Mopt{, \Mtype{partition} shape}}
  \eng{Returns whether $T$ is a tableau or not.}
  \eng{If the optional argument is present, returns whether \Mpar{T} is a
   tableau of shape \Mpar{shape} or not.}
\end{MMethodDetails}

\begin{MMethodDetails}{isAStandardTableau}
  \infoEng{test if an object is a standard tableau}
  \call{\Mtype{tableau} T\Mopt{, \Mtype{partition} shape}}
  \eng{Returns whether \Mpar{T} is a standard tableau or not.}
  \eng{If the optional argument is present, returns whether \Mpar{T} is a
   standard tableau of shape \Mpar{shape} or not.}
\end{MMethodDetails}

\begin{MMethodDetails}{shape}
  \infoEng{the shape of a tableau}
  \call{\Mtype{tableau} T}
  \eng{Returns the shape of the tableau \Mpar{T}.}
\end{MMethodDetails}

\begin{MMethodDetails}{toWord}
  \infoEng{natural reading of a tableau} \call{\Mtype{tableau} T}
  \eng{Returns the natural row reading of the tableau \Mpar{T},
    from top to bottom, and from left to right.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromWord}
  \infoEng{tableau from its natural reading}
  \call{\Mtype{word} w}
  \eng{Returns the list of increasing subsequences of \Mpar{w}. Be careful:
    if \Mpar{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.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromShapeAndWord}
  \infoEng{tableau from its shape and natural reading}
  \call{\Mtype{partition} shape, \Mtype{word} w}%
  \eng{Returns the filling of the shape \Mpar{shape} whose natural reading
    is the word \Mpar{w}. Be careful: the result is not necessarily a
    tableau.}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of standard tableaux}
  \call{\Mtype{partition} shape}
  \eng{Returns the number of standard tableaux of shape \Mpar{shape}.
    We make use of the hook-length formula.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the standard tableaux}
  \call{\Mtype{partition} shape}
  \eng{Returns the list of the standard tableaux of shape \Mpar{shape}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for standard tableaux}
  \call{\Mtype{partition} shape}
  \eng{Returns a generator for the standard tableaux of shape \Mpar{shape}.}
\end{MMethodDetails}

\begin{MMethodDetails}{conjugate}
  \infoEng{conjugate of a filling}
  \call{\Mtype{filling} f}
  \eng{Returns the conjugate (or transposed) of the filling \Mpar{f}.
    Geometrically, this operation amounts to a reflection of
    the diagram with respect to the main diagonal.}
\end{MMethodDetails}

\begin{MMethodDetails}{canonical}
  \infoEng{canonical standard tableau}
  \call{\Mtype{partition} shape}
  \eng{Returns the row-canonical tableau of shape \Mpar{shape} obtained by
  filling consecutive rows starting from the bottom.}
\end{MMethodDetails}

\begin{MMethodDetails}{columnCanonical}
  \infoEng{column canonical standard tableau}
  \call{\Mtype{partition} shape}
  \eng{Returns the column-canonical tableau of shape \Mpar{shape} obtained by
  filling consecutive columns starting from the left.}
\end{MMethodDetails}

\begin{MMethodDetails}{rowStabilizer}
  \infoEng{row stabilizer of a standard filling}
  \call{\Mtype{standard filling} t}%
  \eng{Returns the list of permutations of values of \Mpar{t}
    that stabilize the rows of \Mpar{t}.}
\end{MMethodDetails}

\begin{MMethodDetails}{columnStabilizer}
  \infoEng{column stabilizer of a standard filling}
  \call{\Mtype{standard filling} t}%
  \eng{Returns the list of permutations of values of \Mpar{t}
    that stabilize the columns of \Mpar{t}.}
\end{MMethodDetails}

\begin{MMethodDetails}{indexFilling}
  \infoEng{index filling of a standard tableau}
  \call{\Mtype{standard tableau} t}
  \eng{Returns the index filling of the tableau \Mpar{t}, during the
  computation of the cocharge.}
  \eng{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.}
  \eng{See also : Macdonald I.-G., (1995), "Symmetric Functions and Hall
  Polynomials", Oxford Science Publication.}
\end{MMethodDetails}

\begin{MMethodDetails}{cocharge}
  \infoEng{cocharge of a standard tableau}
  \call{\Mtype{standard tableau} t}
  \eng{Returns the cocharge of the tableau \Mpar{t}.}
  \eng{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.}
  \eng{See also : Macdonald I.-G., (1995), "Symmetric Functions and Hall
  Polynomials", Oxford Science Publication.}
\end{MMethodDetails}

\begin{MMethodDetails}{insertWord}
  \infoEng{insertion of a word in a tableau}
  \call{\Mtype{tableau} t, \Mtype{word} w}
  \eng{Returns the result of the insertion by Schented algorithm of \Mpar{w}
    in \Mpar{t}.}
\end{MMethodDetails}

\begin{MMethodDetails}{schensted}
  \infoEng{Robinson-Schensted correspondence}
  \call{\Mtype{word} w}
  \eng{Returns the result of the insertion by the Robinson-Schensted
    correspondence of \Mpar{w}. Generally, the result is a pair composed
    of a semi-standard tableau and a standard tableau.}
\end{MMethodDetails}

\begin{MMethodDetails}{invSchensted}
  \infoEng{reverse Robinson-Schensted correspondence}
  \call{\Mtype{semi-standard tableau} t1, \Mtype{standard tableau} t2}
  \eng{Returns the word obtained by the reverse bijection of
    Robinson-Schented.}
\end{MMethodDetails}

\begin{MMethodDetails}{kostka}
  \infoEng{Kostka number}
  \call{\Mtype{partition} lambda, \Mtype{partition} mu}
  
  \eng{Returns the Kostka number $K_\lambda^\mu$, that is the number
    of semi-standard tableaux of shape \Mpar{lambda} and evaluation
    \Mpar{mu}.}

  \eng{Maybe should be called \Mex{fromShapeAndEvaluation::count}?}
\end{MMethodDetails}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Examples of tableaux
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{MExample}{ex-isA}
  \eng{The following list of lists of integers is a tableau but not a
    standard tableau:}
  \begin{Mexin}
combinat::tableaux::isA([[4, 4], [1, 2, 4]]);
combinat::tableaux::isAStandardTableau([[4, 4], [1, 2, 4]]);
  \end{Mexin}
  \begin{Mexout}
                             TRUE

                             FALSE
  \end{Mexout}
  \eng{Moreover, the shape of this tableau is confirmed to be $[3,2]$, and
    not of shape $[3,1,1]$.}
  \begin{Mexin}
combinat::tableaux::isA([[4, 4], [1, 2, 4]],[3,2]);
combinat::tableaux::isA([[4, 4], [1, 2, 4]],[3,1,1]);
  \end{Mexin}
  \begin{Mexout}
                             TRUE

                             FALSE
  \end{Mexout}
\end{MExample}
%
\begin{MExample}{ex-tab}
  \eng{There are $5$ tableaux of shape $(3,2)$:}
  \begin{Mexin}
combinat::tableaux::count([3,2])
  \end{Mexin}
  \begin{Mexout}
                               5
  \end{Mexout}
  \eng{Here is the list:}
  \begin{Mexin}
combinat::tableaux::list([3,2])
  \end{Mexin}
  \begin{Mexout}
-- +---+---+      +---+---+      +---+---+      +---+---+
|  | 4 | 5 |      | 3 | 5 |      | 2 | 5 |      | 3 | 4 |
|  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
|  | 1 | 2 | 3 |, | 1 | 2 | 4 |, | 1 | 3 | 4 |, | 1 | 2 | 5 |,
-- +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

   +---+---+     --
   | 2 | 4 |      |
   +---+---+---+  |
   | 1 | 3 | 5 |  |
   +---+---+---+ --
  \end{Mexout}
  \eng{If you want to run through the tableaux of a shape, you
    can generate them one by one to save memory:}
  \begin{Mexin}
g := combinat::tableaux::generator([3,2]):
g(); g(); g(); g(); g(); g()
  \end{Mexin}
  \begin{Mexout}
                         +---+---+
                         | 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
  \end{Mexout}
  \eng{Typically, this would be used as follows:}
  \begin{Mexin}
g := combinat::tableaux::generator([3,2]):
while (p := g()) <> FAIL do print(p): end:
  \end{Mexin}
  \begin{Mexout}
                         +---+---+
                         | 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 |
                         +---+---+---+
  \end{Mexout}
\end{MExample}
%
\begin{MExample}{tab-shape-and-word}
  \eng{The tableau \Mex{[[3, 4], [1, 2, 5]]} is of shape:}
  \begin{Mexin}
combinat::tableaux::shape([[3, 4], [1, 2, 5]])
  \end{Mexin}
  \begin{Mexout}
                            [3, 2]
  \end{Mexout}
  \eng{Its conjugate is the tableau:}
  \begin{Mexin}
combinat::tableaux::conjugate([[3, 4], [1, 2, 5]])
  \end{Mexin}
  \begin{Mexout}
                     [[5], [2, 4], [1, 3]]
  \end{Mexout}
  \eng{The shape of the conjugate is the conjugate of the shape:}
  \begin{Mexin}
t:=[[7], [3, 4], [1, 2, 5, 6]];
combinat::tableaux::shape(combinat::tableaux::conjugate(t));
combinat::partitions::conjugate(combinat::tableaux::shape(t))
  \end{Mexin}
  \begin{Mexout}
                  [[7], [3, 4], [1, 2, 5, 6]]

                         [3, 2, 1, 1]

                         [3, 2, 1, 1]
  \end{Mexout}
\end{MExample}
\begin{MExample}{tab-word}
  \eng{The tableau \Mex{[[3, 4], [1, 2, 5]]} corresponds to the word:}
  \begin{Mexin}
combinat::tableaux::toWord([[3, 4], [1, 2, 5]])
  \end{Mexin}
  \begin{Mexout}
                        [3, 4, 1, 2, 5]
  \end{Mexout}
  \eng{The tableau can be reconstructed back from the word:}
  \begin{Mexin}
combinat::tableaux::fromWord([3, 4, 1, 2, 5])
  \end{Mexin}
  \begin{Mexout}
                         +---+---+
                         | 3 | 4 |
                         +---+---+---+
                         | 1 | 2 | 5 |
                         +---+---+---+
  \end{Mexout}
\end{MExample}

\begin{MExample}{tab-canonical}
  \eng{The row-canonical and column-canonical tableaux of shape
  $(3,2)$ are:}
  \begin{Mexin}
combinat::tableaux::canonical([3,2]);
combinat::tableaux::columnCanonical([3,2]);
  \end{Mexin}
  \begin{Mexout}
                         +---+---+
                         | 4 | 5 |
                         +---+---+---+
                         | 1 | 2 | 3 |
                         +---+---+---+

                         +---+---+
                         | 2 | 4 |
                         +---+---+---+
                         | 1 | 3 | 5 |
                         +---+---+---+
  \end{Mexout}
\end{MExample}

\begin{MExample}{tab-stabilizer}
  \Mex{\begin{sloppypar}
    Exchanging the values $2$ and $5$ in the filling
    \Mex{T:=[[2,5], [1,3,4]]} yields \Mex{T:=[[5,2], [1,3,4]]}: this
    operation stabilize the rows of \Mex{T}.  In general, all the
    following $12$ permutations stabilize the rows of \Mex{T}:
    \end{sloppypar}}
  \begin{Mexin}
combinat::tableaux::rowStabilizer([[2, 5], [1, 3, 4]])
  \end{Mexin}
  \begin{Mexout}
[[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]]
  \end{Mexout}
  \eng{Similarily, there are \Mex{4} permutations which stabilize the
    columns of \Mex{T}:}
  \begin{Mexin}
combinat::tableaux::columnStabilizer([[2, 5], [1, 3, 4]])
  \end{Mexin}
  \begin{Mexout}
[[1, 2, 3, 4, 5], [2, 1, 3, 4, 5], [1, 2, 5, 4, 3],

   [2, 1, 5, 4, 3]]
  \end{Mexout}
  
\end{MExample}

\begin{MExample}{tab-charge}
  \eng{To compute the cocharge of the tableau \Mex{[[3, 5], [1, 2, 4]]},
  we compute the indexes:}
  \begin{Mexin}
combinat::tableaux::indexFilling([[3, 5], [1, 2, 4]])
  \end{Mexin}
  \begin{Mexout}
                      [[1, 2], [0, 0, 1]]
  \end{Mexout}
  \eng{The cocharge is their sum:}
  \begin{Mexin}
combinat::tableaux::cocharge([[3, 5], [1, 2, 4]])
  \end{Mexin}
  \begin{Mexout}
                               4
  \end{Mexout}
\end{MExample}

\begin{MExample}{tab-Schensted}
  \eng{To insert a word in a tableau, we compute:}
  \begin{Mexin}
combinat::tableaux::insertWord([[3],[1,2,4]],[5,1]);
  \end{Mexin}
  \begin{Mexout}
                       +---+
                       | 3 |
                       +---+
                       | 2 |
                       +---+---+---+---+
                       | 1 | 1 | 4 | 5 |
                       +---+---+---+---+
  \end{Mexout}
  \eng{To get the two tableaux arising from the insertion of a word in the
    Robinson-Schensted correspondence, we compute:}
  \begin{Mexin}
combinat::tableaux::schensted([1, 3, 5, 2, 4]);
  \end{Mexin}
  \begin{Mexout}
              -- +---+---+      +---+---+     --
              |  | 3 | 5 |      | 4 | 5 |      |
              |  +---+---+---+  +---+---+---+  |
              |  | 1 | 2 | 4 |, | 1 | 2 | 3 |  |
              -- +---+---+---+  +---+---+---+ --
  \end{Mexout}
  \eng{Conversely, starting from two tableaux, one recovers the word they
    correspond to, by using:}
  \begin{Mexin}
combinat::tableaux::invSchensted([[3, 5], [1, 2, 4]], [[4, 5], [1, 2, 3]]);
  \end{Mexin}
  \begin{Mexout}
                        [1, 3, 5, 2, 4]
  \end{Mexout}
\end{MExample}

\MSuperDomain{Dom::BaseDomain}

\begin{MAxioms}
  \Mup{Ax::systemRep}
\end{MAxioms}

\begin{MChanges}
  \version{2.5}%
  \eng[New library]{\Mthis{} is a new library}%
\end{MChanges}

\end{Mhelppage}

