% $Id: skewTableaux.tex,v 1.1.1.2 2005/01/26 13:42:24 nthiery Exp $
\begin{Mhelppage}{skewTableaux}{T.~Gómez-Díaz, N.~Thiéry and F.~Descouens}
  [ImplState=beta,TestState=stable,DocState=beta]
%\Mproofread{...}{...}{...}

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

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

\MKeywords{combinatorics,skewPartition,skewTableau}

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

    \eng{A skew tableau is encoded by the list of its shape's inner partition and the list of its rows, from top to bottom. For example, the above skew tableau is encoded by \\
    \Mex{[[2, 1], [[1], [2, 4], [3, 5, 6]]]}. }

\end{MDetails}

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

\MRelatedDomains{combinat::skewPartitions}

\begin{MDomEntries}
  \MDomEntry{domtype}
     \eng{The \mupad\ domainused to represent tableaux: \\
\Mex{ Type::ListOf(Type::Union(Type::ListOf(Type::NonNegInt), DOM_LIST))}.}
\end{MDomEntries}

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

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

\begin{MMethodDetails}{toChain}
  \infoEng{return a given skew tableau as a chain of partitions}
  \call{\Mtype{skew tableau} skt} \eng{this function returns the chain
  of partitions corresponding to a given skew tableau standard or semi
  standard}
\end{MMethodDetails}

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

\begin{MMethodDetails}{count}
  \infoEng{number of standard skew tableaux}
  \call{\Mtype{skew partition} skp}
  \eng{Returns the number of standard skew tableaux of shape \Mpar{skp}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of standard skew tableaux}
  \call{\Mtype{skew partition} skp}	
  \eng{Returns the list of the standard skew tableaux of shape \Mpar{skp}.
  We use linear extension of the graph which represents the partial order between skew tableau cases. }
\end{MMethodDetails}

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



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

\begin{MExample}{ex-isA}
  
  \eng{These are two examples of skew tableau test:}
  \begin{Mexin}
    combinat::skewTableaux::isASkewTableau([[3, 2] , [[4, 4], [1, 2, 4]] ]);
    combinat::skewTableaux::isASkewTableau([[3, 1, 1] , [[4, 4], [1, 2, 4]] ]);
  \end{Mexin}
  \begin{Mexout}
                             TRUE

                             FALSE
  \end{Mexout}
 
  \eng{These are two exemples of standard skew tableau test:}
  \begin{Mexin}
    combinat::skewTableaux::isAStandardSkewTableau([[2, 1], [[1], [2, 4], [3, 5, 6]]]);
    combinat::skewTableaux::isAStandardSkewTableau([[2, 1], [[1], [2, 4], [3, 5, 7]]]);
  \end{Mexin}
  \begin{Mexout}
                             TRUE

                             FALSE
  \end{Mexout}


\end{MExample}

\begin{MExample}{ex-chain}
The chain corresponding to the following skew tableau is $[[1, 1], [1, 1, 1], [2, 1, 1], [2, 2, 1], [3, 2, 1]]$.
  \Mdmath{%
      +---+
      | 1 |
      +---+---+
          | 3 |
          +---+---+---+
              | 2 | 4 |
              +---+---+}%
    {\begin{array}{l}
        \fbox{1}\\[-1pt]
        \phantom{\fbox{1}}\fbox{3}\\[-1pt]
        \phantom{\fbox{1}}\phantom{\fbox{1}}\fbox{2}\fbox{4}
      \end{array}}

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

   +---+          +---+          +---+          +---+
   | 3 |          | 4 |          | 3 |          | 4 |
   +---+---+      +---+---+      +---+---+      +---+---+
       | 2 |    ,     | 2 |    ,     | 4 |    ,     | 3 |
       +---+---+      +---+---+      +---+---+      +---+---+
       | 1 | 4 |      | 1 | 3 |      | 1 | 2 |      | 1 | 2 |
       +---+---+      +---+---+      +---+---+      +---+---+

   --
    |
    |
    |
    |
    |
   --
  \end{Mexout}
  \eng{If you want to run through the skew tableaux of a shape, you
    can generate them one by one to save memory:}
  \begin{Mexin}
g := combinat::skewTableaux::generator([[3, 2, 1], [1, 1]]);
g(); g(); g(); g(); g(); g(); g(); g(); g();
  \end{Mexin}
  \begin{Mexout}
                  proc mapGenerator() ... end

                         +---+
                         | 1 |
                         +---+---+
                             | 3 |
                             +---+---+
                             | 2 | 4 |
                             +---+---+

                         +---+
                         | 1 |
                         +---+---+
                             | 4 |
                             +---+---+
                             | 2 | 3 |
                             +---+---+

                         +---+
                         | 2 |
                         +---+---+
                             | 3 |
                             +---+---+
                             | 1 | 4 |
                             +---+---+

                         +---+
                         | 2 |
                         +---+---+
                             | 4 |
                             +---+---+
                             | 1 | 3 |
                             +---+---+

                         +---+
                         | 3 |
                         +---+---+
                             | 2 |
                             +---+---+
                             | 1 | 4 |
                             +---+---+

                         +---+
                         | 4 |
                         +---+---+
                             | 2 |
                             +---+---+
                             | 1 | 3 |
                             +---+---+

                         +---+
                         | 3 |
                         +---+---+
                             | 4 |
                             +---+---+
                             | 1 | 2 |
                             +---+---+

                         +---+
                         | 4 |
                         +---+---+
                             | 3 |
                             +---+---+
                             | 1 | 2 |
                             +---+---+

                             FAIL
  \end{Mexout}
  \eng{Typically, this would be used as follows:}
  \begin{Mexin}
g := combinat::skewTableaux::generator([[3, 2, 1], [1, 1]]):
while (p := g()) <> FAIL do print(p): end:
  \end{Mexin}
  \begin{Mexout}
                         +---+
                         | 1 |
                         +---+---+
                             | 3 |
                             +---+---+
                             | 2 | 4 |
                             +---+---+

                         +---+
                         | 1 |
                         +---+---+
                             | 4 |
                             +---+---+
                             | 2 | 3 |
                             +---+---+

                         +---+
                         | 2 |
                         +---+---+
                             | 3 |
                             +---+---+
                             | 1 | 4 |
                             +---+---+

                         +---+
                         | 2 |
                         +---+---+
                             | 4 |
                             +---+---+
                             | 1 | 3 |
                             +---+---+

                         +---+
                         | 3 |
                         +---+---+
                             | 2 |
                             +---+---+
                             | 1 | 4 |
                             +---+---+

                         +---+
                         | 4 |
                         +---+---+
                             | 2 |
                             +---+---+
                             | 1 | 3 |
                             +---+---+

                         +---+
                         | 3 |
                         +---+---+
                             | 4 |
                             +---+---+
                             | 1 | 2 |
                             +---+---+

                         +---+
                         | 4 |
                         +---+---+
                             | 3 |
                             +---+---+
                             | 1 | 2 |
                             +---+---+
\end{Mexout}
\end{MExample}
%
\begin{MExample}{tab-word}
  \eng{The skew tableau can be reconstructed back from the shape and the word:\\
 the result is not necessary a standard skew tableau, it depends on the word}
  \begin{Mexin}
 combinat::skewTableaux::fromShapeAndWord([[3, 2, 1], [1, 1]], [1, 3, 4, 6]);
  \end{Mexin}
  \begin{Mexout}
                         +---+
                         | 1 |
                         +---+---+
                             | 3 |
                             +---+---+
                             | 4 | 6 |
                             +---+---+
  \end{Mexout}
\end{MExample}

%
\begin{MExample}{print-pretty}
\eng{The skew tableau can be printed on screen with pretty form}
 \begin{Mexin}
  combinat::skewTableaux::printPretty([[1, 1], [[1], [3], [4, 6]]]);
 \end{Mexin}
\begin{Mexout}
                         +---+
                         | 1 |
                         +---+---+
                             | 3 |
                             +---+---+
                             | 4 | 6 |
                             +---+---+
\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}


















