\begin{Mhelppage}{skewPartitions}{T.~Gómez-Díaz, F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{hivert}{23.09.2003}{proofread}

\begin{MInfo}
  \eng{skew partitions}
\end{MInfo}

\MDeclareOption{\Connected}{Connected}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting,
    generating, and manipulating skew partitions of fixed
    size.}
\end{MIntro}

\MKeywords{combinatorics, skew partitions, partitions}

\begin{MDetails}
  \eng{A \emph{skew partition} $skp$ of size $n$ is a pair of two
       partitions $[p1, p2]$ where $p1$ is a partition of
       the integer $n1$, $p2$ is a partition of the integer $n2$,
       $p2$ is an inner partition of $p1$ and $n=n1-n2$.
       We say that $p1$ and $p2$ are respectively the 
       \emph{outer and inner} partitions of $skp$.}

  \eng{A skew partition is so represented in \mupad\ 
       by a list of two partitions:

       \Mex{[\Mpar{outer}, \Mpar{inner}]}.} 

  \eng{A skew partition can be depicted by a diagram made of rows of boxes,
    in the same way as a partition. Only the boxes of the outer partition $p1$
    which are not in the inner partition $p2$ appear in the picture.
    For example, this is the diagram of the skew partition
    \Mex{[[5,4,3,1],[3,3,1]]}:%
    \Mdmath{%
+---+
|   |
+---+---+---+
    |   |   |   
    +---+---+---+
            |   |
            +---+---+
            |   |   |   
            +---+---+
     }
     {\begin{array}{l}
        \fbox{\phantom{1}}\\[-1pt]
        \phantom{\fbox{1}}\fbox{\phantom{1}}\fbox{\phantom{1}}\\[-1pt]
        \phantom{\fbox{1}}\phantom{\fbox{1}}\phantom{\fbox{1}}\fbox{\phantom{1}}\\[-1pt]
        \phantom{\fbox{1}}\phantom{\fbox{1}}\phantom{\fbox{1}}
            \fbox{\phantom{1}}\fbox{\phantom{1}}\\[-1pt]
      \end{array}}
     And this is not a skew partition:
    \Mdmath{%
+---+
|   |
+---+---+---+
    |   |   |
    +---+---+
            
            +---+---+
            |   |   |
            +---+---+
     }
     {\begin{array}{l}
        \fbox{\phantom{1}}\\[-1pt]
        \phantom{\fbox{1}}\fbox{\phantom{1}}\fbox{\phantom{1}}\\[-1pt]
        \phantom{\fbox{1}}\phantom{\fbox{1}}\phantom{\fbox{1}}\phantom{\fbox{1}}\\[-1pt]
        \phantom{\fbox{1}}\phantom{\fbox{1}}\phantom{\fbox{1}}
            \fbox{\phantom{1}}\fbox{\phantom{1}}\\[-1pt]
      \end{array}}}

  \eng{A skew partition can be \emph{connected}, which
       can be easily described in graphic terms: for each pair of 
       consecutive rows, there are at least two boxes (one in
       each row) which have a common edge.
      This is the the diagram of the connected skew partition
      \Mex{[[5,4,3,1],[3,1]]}:%
      \Mdmath{%
+---+
|   |
+---+---+---+
|   |   |   |   
+---+---+---+---+
    |   |   |   |   
    +---+---+---+---+
            |   |   |   
            +---+---+
      }
      {\begin{array}{l}
        \fbox{\phantom{1}}\\[-1pt]
        \fbox{\phantom{1}}\fbox{\phantom{1}}\fbox{\phantom{1}}\\[-1pt]
        \phantom{\fbox{1}}\fbox{\phantom{1}}\fbox{\phantom{1}}\fbox{\phantom{1}}\\[-1pt]
        \phantom{\fbox{1}}\phantom{\fbox{1}}\phantom{\fbox{1}}
            \fbox{\phantom{1}}\fbox{\phantom{1}}\\[-1pt]
      \end{array}}
      And our first example of skew partition is not a connected one.}

  \eng{To apply a reflection w.r.t. the main diagonal to the diagram
    yields the diagram of the \emph{conjugate skew partition}, here
    \Mex{[[4,3,3,2,1],[3,2,2]]}:
    \Mdmath{%
+---+
|   |
+---+---+
|   |   |
+---+---+---+
        |   |
        +---+
        |   |
        +---+---+
            |   |
            +---+
        }
      {\begin{array}{l}
        \fbox{\phantom{1}}\\[-1pt]
        \fbox{\phantom{1}}\fbox{\phantom{1}}\\[-1pt]
        \phantom{\fbox{1}}\phantom{\fbox{1}}\fbox{\phantom{1}}\\[-1pt]
        \phantom{\fbox{1}}\phantom{\fbox{1}}\fbox{\phantom{1}}\\[-1pt]
        \phantom{\fbox{1}}\phantom{\fbox{1}}\phantom{\fbox{1}}\fbox{\phantom{1}}\\[-1pt]
      \end{array}}
    See \Mup{combinat::skewPartitions::conjugate}.}

  \eng{The \emph{outer corners} of a skew partition are the corners
       of its outer partition. The \emph{inner corners} are the
       internal corners of the outer partition when the inner partition
       is taken off. See the examples below.}
 
\end{MDetails}

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

\MRelatedDomains{combinat::partitions}
      
\begin{MDomEntries}
  \MDomEntry{domtype}
     \eng{The \mupad\ domain of skew partitions: \Mup{DOM_LIST}}
  \MDomEntry{typeConnected}
     \eng{The \mupad\ type of connected skew partitions.}
\end{MDomEntries}

\begin{MMethodDetails}{isA}
 \infoEng{test if a object is a skew partition}%
  \call{\Mtype{any type} skp 
        \Mopt{, \Mtype{nonnegative integer} n}
        \Mopt{, \Connected}}%
  \eng{Tests whether \Mpar{skp} is a skew partition.
       The second argument is either \Connected or 
       a non negative integer. In the case it is a non negative 
       integer, it indicates the size of the skew partition
       and the function tests if \Mpar{skp} is a 
       skew partition of size \Mpar{n},
       and if it is \Connected the function tests whether
       \Mpar{skp} is a connected skew partition.
       With three arguments it is possible to tests if 
       \Mpar{skp} is a connected skew partition of size \Mpar{n}.}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of skew partitions}%
  \call{\Mtype{nonnegative integer} n \Mopt{, \Connected}}%
  \eng{Returns the number of skew partitions of size \Mpar{n}.
       The result counts only the connected skew partitions
       if it is said so.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for skew partitions}%
  \call{\Mtype{nonnegative integer} n \Mopt{, \Connected}}%
  \eng{Returns a generator for the skew partitions of size \Mpar{n}.
       The result gives access only to connected skew partitions
       if it is said so.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the skew partitions}%
  \call{\Mtype{nonnegative integer} n \Mopt{, \Connected}}%
  \eng{Returns the list of the skew partitions of size \Mpar{n}.
       The result is a list of connected skew partitions
       if it is said so.}
\end{MMethodDetails}

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

\begin{MMethodDetails}{jacobiTrudy}
  \infoEng{Jacoby-Trudi formula}%
  \call{\Mtype{skew partition} skp \Mopt{, function}}%
  \eng{This function compute the \emph{Jacobi-Trudy} matrix associated to the
    skew partition \Mpar{skp}. Its determinant express the skew Schur
    polynomial associated to \Mpar{skp} on the basis of homogenous complete
    symmetric polynomial (see Macdonald I.-G., (1995), "Symmetric Functions
    and Hall Polynomials", Oxford Science Publication). The default value of
    the \Mpar{function} argument is \Mpar{i -> h[i]}.}
\end{MMethodDetails}

\begin{MMethodDetails}{innerCorners}
  \infoEng{inner corners of a skew partition}
  \call{\Mtype{skew partition} skp}%
  \eng{Returns the list of coordinates of the inner corner boxes 
    in the diagram of the skew partition.}
\end{MMethodDetails}

\begin{MMethodDetails}{outerCorners}
  \infoEng{outer corners of a skew partition}
  \call{\Mtype{skew partition} skp}%
  \eng{Returns the list of coordinates of the outer corner boxes 
    in the diagram of the skew partition, i.e. the corners of the 
    outer partition of \Mpar{skp}.}
\end{MMethodDetails}

\begin{MMethodDetails}{printPretty}
  \infoEng{graphic representation of a skew partition}
  \call{\Mtype{skew partition} skp}%
  \eng{Returns a graphic representation of the skew partition
       as rows of boxes.}
\end{MMethodDetails}

\begin{MMethodDetails}{printCompact}
  \infoEng{graphic representation of a skew partition}
  \call{\Mtype{skew partition} skp}%
  \eng{Same as above, but in a more compact way, where each box
       is represented by \Mpar{\#}.}
\end{MMethodDetails}

\begin{MMethodDetails}{printPrettyCorners}
  \infoEng{graphic representation of inner and outer corners 
           of a skew partition}
  \call{\Mtype{skew partition} skp}%
  \eng{Returns a graphic representation of the skew partition
       as rows of boxes where inner corners are marked with \Mpar{x}
       and outer corners are marked with \Mpar{*}. A \Mpar{\%}
       marks a corner which is inner and outer at the same time.}
\end{MMethodDetails}

\begin{MMethodDetails}{printCompactCorners}
  \infoEng{graphic representation of inner and outer corners
           of a skew partition}
  \call{\Mtype{skew partition} skp}%
  \eng{Same as above, but in a more compact way, where each box
       is represented by \Mpar{\#}, and \Mpar{x}, \Mpar{*},
       \Mpar{\%} mark the corners.}
\end{MMethodDetails}


\begin{MExample}{ex-basic}
  \eng{There are $9$ skew partitions of size $3$:}
  \begin{Mexin}
combinat::skewPartitions::count(3)
  \end{Mexin}
  \begin{Mexout}
                               9
  \end{Mexout}
  \eng{Here is the list:}
  \begin{Mexin}
combinat::skewPartitions::list(3)
  \end{Mexin}
  \begin{Mexout}
[[[3], []], [[2, 1], []], [[3, 1], [1]], [[2, 2], [1]],

   [[3, 2], [2]], [[1, 1, 1], []], [[2, 2, 1], [1, 1]],

   [[2, 1, 1], [1]], [[3, 2, 1], [2, 1]]]
  \end{Mexout}
  \eng{Here is a graphic representation of the list:}
  \begin{Mexin}
map(combinat::skewPartitions::list(3),
combinat::skewPartitions::printCompact)
  \end{Mexin}
  \begin{Mexout}
          --      #   #    ##  ##   #  #   #   #   --
          |  ###, ##,  ##,  #,   #, #,  #, # ,  #   |
          --                        #   #   #    # --
  \end{Mexout}

  \eng{There are $4$ connected skew partitions of size $3$:}
  \begin{Mexin}
combinat::skewPartitions::count(3, Connected)
  \end{Mexin}
  \begin{Mexout}
                               4
  \end{Mexout}

  \eng{Here is the list:}
  \begin{Mexin}
combinat::skewPartitions::list(3, Connected)
  \end{Mexin}
  \begin{Mexout}
   [[[3], []], [[2, 1], []], [[2, 2], [1]], [[1, 1, 1], []]]
  \end{Mexout}
  \eng{Here is a graphic representation of the list:}
  \begin{Mexin}
map(combinat::skewPartitions::list(3, Connected),
combinat::skewPartitions::printPretty)
  \end{Mexin}
  \begin{Mexout}
       --                                      +---+ --
       |                                       |   |  |
       |                 +---+      +---+---+  +---+  |
       |                 |   |      |   |   |  |   |  |
       |  +---+---+---+  +---+---+  +---+---+  +---+  |
       |  |   |   |   |, |   |   |,     |   |, |   |  |
       -- +---+---+---+  +---+---+      +---+  +---+ --
  \end{Mexout}


  \eng{When you want to run through the skew partitions of a given size, you
    can generate them one by one to save memory:}
  \begin{Mexin}
g := combinat::skewPartitions::generator(3):
g(); g(); g(); g(); g(); g(); g(); g(); g(); g()
  \end{Mexin}
  \begin{Mexout}
                           [[3], []]

                         [[2, 1], []]

                         [[3, 1], [1]]

                         [[2, 2], [1]]

                         [[3, 2], [2]]

                        [[1, 1, 1], []]

                      [[2, 2, 1], [1, 1]]

                       [[2, 1, 1], [1]]

                      [[3, 2, 1], [2, 1]]

                             FAIL
  \end{Mexout}

  \eng{It is also possible to generate connected skew partitions of a 
    given size:}
  \begin{Mexin}
g := combinat::skewPartitions::generator(3, Connected):
g(); g(); g(); g(); g()
  \end{Mexin}
  \begin{Mexout}
                           [[3], []]

                         [[2, 1], []]

                         [[2, 2], [1]]

                        [[1, 1, 1], []]

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

\end{MExample}

\begin{MExample}{ex-conjugate}
  \eng{This is the conjugate of the skew partition \Mex{[[4, 3, 1], [2]]}:}
  \begin{Mexin}
combinat::skewPartitions::conjugate([[4, 3, 1], [2]])
  \end{Mexin}
  \begin{Mexout}
                    [[3, 2, 2, 1], [1, 1]]
  \end{Mexout}
  \eng{Geometrically, we just applied a reflection with respect to the
    main diagonal on the diagram of the partition. Of course, this
    operation is an involution:}
  \begin{Mexin}
combinat::skewPartitions::conjugate([[3, 2, 2, 1], [1, 1]])
  \end{Mexin}
  \begin{Mexout}
                       [[4, 3, 1], [2]]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-jacobiTrudy}
  \eng{The \Mslot{jacobiTrudy} function compute the \emph{Jacobi-Trudy} matrix,
       see Macdonald I.-G., (1995), "Symmetric Functions and Hall
       Polynomials", Oxford Science Publication.} 
  \begin{Mexin}
combinat::skewPartitions::jacobiTrudy([[4, 3, 1], [2]])
  \end{Mexin}
  \begin{Mexout}
                    +-                  -+
                    |  h[2], h[0],   0   |
                    |                    |
                    |  h[5], h[3], h[0]  |
                    |                    |
                    |  h[6], h[4], h[1]  |
                    +-                  -+
  \end{Mexout}

  \begin{Mexin}
combinat::skewPartitions::jacobiTrudy([[4, 3, 1], [2]], T)
  \end{Mexin}
  \begin{Mexout}
                    +-                  -+
                    |  T(2), T(0),   0   |
                    |                    |
                    |  T(5), T(3), T(0)  |
                    |                    |
                    |  T(6), T(4), T(1)  |
                    +-                  -+
  \end{Mexout}

\end{MExample}

\begin{MExample}{ex-corners}
  \eng{This example shows how to compute the corners of a
       skew partition.}
  \begin{Mexin}
combinat::skewPartitions::innerCorners([[4, 3, 1], [2]])
  \end{Mexin}
  \begin{Mexout}
                       [[1, 3], [2, 1]]
  \end{Mexout}
  \begin{Mexin}
combinat::skewPartitions::outerCorners([[4, 3, 1], [2]])
  \end{Mexin}
  \begin{Mexout}
                   [[1, 4], [2, 3], [3, 1]]
  \end{Mexout}
  \eng{The inner and outer corners can be represented graphically:}
  \begin{Mexin}
combinat::skewPartitions::printPrettyCorners([[4, 3, 1], [2]])
  \end{Mexin}
  \begin{Mexout}
                       +---+
                       | * |
                       +---+---+---+
                       | x |   | * |
                       +---+---+---+---+
                               | x | * |
                               +---+---+
  \end{Mexout}
  \eng{Sometimes inner and outer corners coincide:}
  \begin{Mexin}
combinat::skewPartitions::printPrettyCorners([[4, 3, 1], [3]])
  \end{Mexin}
  \begin{Mexout}
                       +---+
                       | * |
                       +---+---+---+
                       | x |   | * |
                       +---+---+---+---+
                                   | % |
                                   +---+
  \end{Mexout}
  \eng{Or we can prefer a more compact representation:}
  \begin{Mexin}
combinat::skewPartitions::printPrettyCorners(
[[9, 8, 4, 3, 1], [6, 4, 3, 1]])
  \end{Mexin}
  \begin{Mexout}
             +---+
             | % |
             +---+---+---+
                 | x | * |
                 +---+---+---+
                         | % |
                         +---+---+---+---+---+
                             | x |   |   | * |
                             +---+---+---+---+---+
                                     | x |   | * |
                                     +---+---+---+
  \end{Mexout}
  \begin{Mexin}
combinat::skewPartitions::printCompactCorners(
[[9, 8, 4, 3, 1], [6, 4, 3, 1]])
  \end{Mexin}
  \begin{Mexout}
                           %
                            x*
                              %
                               x##*
                                 x#*
  \end{Mexout}
\end{MExample}

\MSuperDomain{Dom::BaseDomain}

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

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


\end{Mhelppage}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: main
%%% End: 
