% $Id: ribbons.tex,v 1.1.1.2 2004/10/16 15:22:22 nthiery Exp $
\begin{Mhelppage}{ribbons}{F.~Descouens}
  [ImplState=stable,TestState=stable,DocState=beta]
%\Mproofread{...}{...}{...}

\begin{MInfo}
  \eng{Ribbons and tableaux of ribbon shape}
\end{MInfo}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting,
    generating, and manipulating ribbons and tableaux of ribbon shape. These objects are typed objects (as \Mup{combinat::trees}, \Mup{combinat::skewTableaux} and \Mup{combinat::ribbonsTableaux}).}
\end{MIntro}

\MKeywords{combinatorics,ribbons,descents of a permutation}

\begin{MDetails}
  
  \eng{First, a ribbon \Mex{rib} is a particular case of skew partition with a connection condition: the last box of a row is over the first one of the next row. (for details on skew partitions see \Mup{combinat::skewPartitions}).
Due to this connection condition, a ribbon is completely defined by the lenght of each row.\\ This is an example of a ribbon of shape \Mex{[3, 2, 1]}:
    \Mdmath{%
      +---+
      |   |
      +---+---+
      |   |   |
      +---+---+---+---+
          |   |   |   |
          +---+---+---+}%
	   {\begin{array}{l}
               \fbox{\phantom{1}}\\[-1pt]
               \fbox{\phantom{1}}\fbox{\phantom{1}}\\[-1pt]
               \phantom{\fbox{\phantom{1}}}\fbox{\phantom{1}}\fbox{\phantom{1}}\fbox{\phantom{1}}\\
	   \end{array}}
 If we fill the boxes with numbers we get a special case of skew tableaux (see \Mup{combinat::skewTableaux}). Such kind of \emph{filling} is a \emph{Young tableau of ribbon shape}, or for shorter,
    a \emph{tableau of ribbon shape}, if the numbers in the
    boxes verify some order constraints: they are non-decreasing along rows and (strictly) increasing from
    bottom to top along columns. As a ribbon is completely defined by the lenght of each line, a tableau of ribbon shape is entirely defined by the filling of each line given from top to bottom. This is the reason why the expression representation of a tableau of ribbon shape is the list of rows.  
    \\Here is an example of tableau of ribbon shape \Mex{[[4], [3, 3], [2, 2, 3]]}:

     \Mdmath{%
      +---+
      | 4 |
      +---+---+
      | 3 | 3 |
      +---+---+---+---+
          | 2 | 2 | 3 |
          +---+---+---+}%
	   {\begin{array}{l}
               \fbox{4}\\[-1pt]
               \fbox{3}\fbox{3}\\[-1pt]
               \phantom{\fbox{1}}\fbox{2}\fbox{2}\fbox{3}\\
	   \end{array}}

    Moreover, if every positive integer from 1 up to the number of cases appears exactly
    once, the tableau of ribbon shape is called \emph{standard}. Here is an example of a 
    standard tableau of ribbon shape \Mex{[[3], [2, 4], [1, 5, 6]]}:
    \Mdmath{%
      +---+
      | 3 |
      +---+---+
      | 2 | 4 |
      +---+---+---+---+
          | 1 | 5 | 6 |
          +---+---+---+}%
    {\begin{array}{l}
        \fbox{3}\\[-1pt]
        \fbox{2}\fbox{4}\\[-1pt]
        \phantom{\fbox{1}}\fbox{1}\fbox{5}\fbox{6}
      \end{array}}}

    \eng{A tableau of ribbon shape (as a typed object) has for expression the list of its rows, from top to bottom. For example, the above tableau of ribbon shape has for expression: \\
    \Mex{[[3], [2, 4], [1, 5, 6]].}}

    \eng{There is a 1:1 application between compositions and tableaux of ribbon shape, in particular there is a bijection between permutations and standard tableaux of ribbon shape. In the second case, given a permutation we construct its corresponding tableau of ribbon shape in this way: lengths of each row are lengths between the descents in the corresponding permutation (see \Mup{combinat::permutations}). \\
For example to the permutation \Mex{[2, 4, 1, 3, 6, 5]} corresponds the following tableau of ribbon shape \Mex{[1, 3, 2]}:
\Mdmath{%
  +---+---+
  | 2 | 4 |
  +---+---+---+---+
      | 1 | 3 | 6 |
      +---+---+---+
              | 5 |
              +---+     }%
       {\begin{array}{l}
           \fbox{2} \fbox{4}\\[-1pt]
           \phantom{\fbox{1}}\fbox{1}\fbox{3}\fbox{6}\\[-1pt]
	   \phantom{\fbox{1}}\phantom{\fbox{1}}\phantom{\fbox{1}}\fbox{5}
    \end{array}}}


\end{MDetails}

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

\MRelatedDomains{combinat::skewTableaux, combinat::ribbonsTableaux}

\begin{MDomEntries}
  \MDomEntry{typeFilling}
     \eng{type for a filling without increasing conditions between cells. \\
\Mex{ Type::ListOf(Type::ListOf(Type::NonNegInt))} .}

 \MDomEntry{typeRibbon}
     \eng{type for a filling with semi-standard conditions (checked with \\the isA function).\\
\Mex{Type::Predicate("Ribbon", dom::isA) } .}

 \MDomEntry{typeStandardRibbon}
     \eng{type for a filling with standard conditions (checked with \\the isAStandard function).\\
\Mex{Type::Predicate("StandardRibbon", dom::isAStandard) } .}

\end{MDomEntries}

\begin{MMethodDetails}{new}
  \infoEng{creating a new ribbon as a typed object or listing all the standard ribbons of a given shape}
  \call{\Mtype{Type::Union(combinat::compositions, dom::typeFilling )} x}
  \eng{If the type is a TypeFilling, creates the typed object for
the corresponding ribbon \Mpar{x} and returns its external representation.}
  \eng{If the argument is a shape, returns the list of all standard ribbons of shape \Mpar{x}.}
\end{MMethodDetails}

\begin{MMethodDetails}{isA}
  \infoEng{test if an object is a tableau of ribbon shape}
  \call{\Mtype{tableau of ribbon shape} ribShapeTab, \Mopt{\Mtype{composition} shp}}
  \eng{Returns whether \Mpar{ribShapeTab} is a tableau of ribbon shape or not.}
  \eng{If the optional argument is present, it returns whether \Mpar{ribShapeTab} is a tableau of shape the given ribbon \Mpar{shp} or not.}
\end{MMethodDetails}

\begin{MMethodDetails}{isAStandard}
  \infoEng{test if an object is a standard tableau of ribbon shape}
  \call{\Mtype{tableau of ribbon shape} ribShapeTab,\Mopt{\Mtype{composition} shp}}
  \eng{Returns whether \Mpar{ribShapeTab} is a standard tableau of ribbon shape or not.}
  \eng{If the optional argument is present, it returns whether \Mpar{ribShapeTab} is a
   standard tableau of shape the ribbon \Mpar{shp} or not.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromShapeAndWord}
  \infoEng{tableau from its ribbon shape and natural reading}
  \call{\Mtype{composition} shape, \Mtype{word} w}%
  \eng{Returns the filling of the \Mpar{shape} whose natural reading
    is the word \Mpar{w}. Please note that the result is not necessarily a
    tableau of ribbon shape.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of standard tableaux of a given ribbon shape}
  \call{\Mtype{composition} shp}	
  \eng{Returns the list of the standard tableaux of shape the ribbon \Mpar{shp}. \\We use the list function of permutation from descents
(see \Mup{combinat::permutations})}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of standard tableaux of ribbon shape}
  \call{\Mtype{composition} shp}
  \eng{Returns the number of standard tableaux of ribbon shape \Mpar{shp}.}
\end{MMethodDetails}

\begin{MMethodDetails}{toWord}
  \infoEng{composition from a given tableau of ribbon shape}
  \call{\Mtype{tableau of ribbon shape} ribTab}
  \eng{Returns the composition corresponding to a given tableau of ribbon shape.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromWord}
  \infoEng{tableau of ribbon shape from a composition}
  \call{\Mtype{composition} comp}
  \eng{Returns the tableau of ribbon shape corresponding to a given composition. This function is the inverse of the previous function.}
\end{MMethodDetails}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Examples of tableaux
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{MExample}{creation}
\eng{Ribbons are typed objects, which can be constructed as follows:}
\begin{Mexin}
   combinat::ribbons([[2, 3], [1, 4]])
\end{Mexin}
\begin{Mexout}
                         +---+---+
                         | 2 | 3 |
                         +---+---+---+
                             | 1 | 4 |
                             +---+---+
\end{Mexout}

\end{MExample}
\begin{MExample}{ex-isA}
  
  \eng{These are two examples of testing whether an object is a tableau of ribbon shape. In the second one we provide the optional argument shape}
  \begin{Mexin}
    combinat::ribbons::isA([[2, 3], [1, 4]],[2,2]);
    combinat::ribbons::isA([[5, 6], [2, 3], [1,4]], [2, 2])
  \end{Mexin}
  \begin{Mexout}
                             TRUE

                             FALSE
  \end{Mexout}
 
  \eng{These are two examples of standard tableaux of ribbon shape:}
  \begin{Mexin}
    combinat::ribbons::isAStandard([[3,4],[1,2]]);
    combinat::ribbons::isAStandard([[2,4],[2,3]])
  \end{Mexin}
  \begin{Mexout}
                             TRUE

                             FALSE
  \end{Mexout}


\end{MExample}
%

\begin{MExample}{ex-tab}
 
  \eng{Here is the list of standard tableaux of ribbon shape $[2,2]$:}
  \begin{Mexin}
combinat::ribbons::list([2,2])
  \end{Mexin}
  \begin{Mexout}
-- +---+---+      +---+---+      +---+---+      +---+---+
|  | 1 | 3 |      | 1 | 4 |      | 2 | 3 |      | 2 | 4 |
|  +---+---+---+, +---+---+---+, +---+---+---+, +---+---+---+,
|      | 2 | 4 |      | 2 | 3 |      | 1 | 4 |      | 1 | 3 |
--     +---+---+      +---+---+      +---+---+      +---+---+

   +---+---+     --
   | 3 | 4 |      |
   +---+---+---+  |
       | 1 | 2 |  |
       +---+---+ --
  \end{Mexout}
  \eng{There are $155$ standard tableaux of shape the ribbon  $[3, 2, 2]$:}
  \begin{Mexin}
combinat::ribbons::count([3,2,2])
  \end{Mexin}
  \begin{Mexout}
                              155
  \end{Mexout}
\end{MExample}
%
\begin{MExample}{tab-word}
  \eng{Given a word, we can build the corresponding tableau of ribbon shape:
 the result is not necessary a standard tableau of ribbon shape, it depends on the provided word.}
  \begin{Mexin}
combinat::ribbons::fromShapeAndWord([2, 3], [2, 5, 6, 1, 67])
  \end{Mexin}
   \begin{Mexout}
                      +---+---+
                      | 2 | 5 |
                      +---+---+---+----+
                          | 6 | 1 | 67 |
                          +---+---+----+
  \end{Mexout}
\end{MExample}
%


%
\begin{MExample}{from composition and to composition}
\eng{These two functions permit to create a tableau of ribbon shape from a composition and vice versa.}
 \begin{Mexin}
combinat::ribbons::fromWord([1, 3, 2, 4])
 \end{Mexin}
 \begin{Mexout}
                         +---+---+
                         | 1 | 3 |
                         +---+---+---+
                             | 2 | 4 |
                             +---+---+
 \end{Mexout}
\begin{Mexin}
combinat::ribbons::toWord(combinat::ribbons([[4, 5, 6], [2, 3], [1]]));
\end{Mexin}
\begin{Mexout}
                      [4, 5, 6, 2, 3, 1]
\end{Mexout}
\end{MExample}

\MSuperDomain{Dom::BaseDomain}

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

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

\end{Mhelppage}

