% $Id: combinat.tex,v 1.1.1.2 2005/01/26 13:42:23 nthiery Exp $
% Quick demonstration of the combinatorial part

\section{Manipulating combinatorial objects}

\begin{Mexin}
  export(combinat):
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}

  \begin{Mexin}
trees::list(5)
  \end{Mexin}
  \begin{Mexout}
--   o  ,  o ,  o ,  o  ,  o ,  o ,  o ,   o ,  o ,  o ,  o ,
|  // \\  /|\  /|\  / \   / \  /|\  / \   / \  / \   |    |
|           |   |     /\    |  |    | |  /\    |    /|\  / \
|                           |                  |           |
--

    o ,  o , o --
    |    |   |  |
   / \   |   |  |
   |    / \  |  |
             | --
  \end{Mexout}


\eng{A typical standard skew tableaux:}
\begin{Mexin}
skewTableaux::printPretty([[3, 1],
                           [[5],
                            [3, 6, 8],
                               [1, 2, 9],
                                     [4, 7]]])
\end{Mexin}
\begin{Mexout}
                     +---+
                     | 5 |
                     +---+---+---+
                     | 3 | 6 | 8 |
                     +---+---+---+---+
                         | 1 | 2 | 9 |
                         +---+---+---+---+
                                 | 4 | 7 |
                                 +---+---+
\end{Mexout}
\eng{There are quite a few standard skew tableaux of this shape:}
\begin{Mexin}
skewTableaux::count([[5, 4, 3, 1], [3, 1]])
\end{Mexin}
\begin{Mexout}
                             2205
\end{Mexout}
\eng{So, we use a generator to get them one by one:}
\begin{Mexin}
g := generators::map(skewTableaux::generator([[5, 4, 3, 1], [3, 1]]),
                     skewTableaux::printPretty):
\end{Mexin}
\begin{Mexout}
\end{Mexout}

  \begin{Mexin}
g()
  \end{Mexin}
  \begin{Mexout}
                     +---+
                     | 2 |
                     +---+---+---+
                     | 1 | 4 | 6 |
                     +---+---+---+---+
                         | 3 | 5 | 8 |
                         +---+---+---+---+
                                 | 7 | 9 |
                                 +---+---+
  \end{Mexout}
  \begin{Mexin}
g()
  \end{Mexin}
  \begin{Mexout}
                     +---+
                     | 2 |
                     +---+---+---+
                     | 1 | 4 | 6 |
                     +---+---+---+---+
                         | 3 | 5 | 9 |
                         +---+---+---+---+
                                 | 7 | 8 |
                                 +---+---+
  \end{Mexout}
  \begin{Mexin}
g()
  \end{Mexin}
  \begin{Mexout}
                     +---+
                     | 2 |
                     +---+---+---+
                     | 1 | 4 | 7 |
                     +---+---+---+---+
                         | 3 | 5 | 8 |
                         +---+---+---+---+
                                 | 6 | 9 |
                                 +---+---+
  \end{Mexout}
  \begin{Mexin}
g()
  \end{Mexin}
  \begin{Mexout}
                     +---+
                     | 2 |
                     +---+---+---+
                     | 1 | 4 | 7 |
                     +---+---+---+---+
                         | 3 | 5 | 9 |
                         +---+---+---+---+
                                 | 6 | 8 |
                                 +---+---+
  \end{Mexout}


\newpage
\section{Defining new combinatorial classes}

\begin{Mexin}
domain oddIntegers
    // This is a graded combinatorial class:
    category Cat::GradedCombinatorialClass;
    // This is a domain (not a library):
    inherits Dom::BaseDomain;
    // This is a facade domain:
    axiom Ax::systemRep;
    info_str := "The class of non negative odd integers";
    isA := n -> bool(testtype(n, Type::PosInt) and
                     n mod 2 <> 0);
    // The size of an odd integer is itself
    size  := n -> n;
    count := n -> if n mod 2 = 1 then 1 else 0 end_if;
    list  := n -> if n mod 2 = 1 then [n] else [] end_if;
    // No need to define generator;
    // it is defined via list by default
end_domain:
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}

\eng{What's the point? It can be used as building block for
  constructing new combinatorial classes like, say, integer partitions
  with odd parts:}
\begin{Mexin}
oddPartsPartitions := combinat::decomposableObjects
                         ([Part = Multiset(oddIntegers)]):
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
\begin{Mexin}
oddPartsPartitions::list(5)
\end{Mexin}
\begin{Mexout}
   [Multiset(5), Multiset(1, 1, 3), Multiset(1, 1, 1, 1, 1)]
\end{Mexout}


\section{Unlabelled graphs, Pólya enumeration, link with Nauty}

\eng{We use Pólya enumeration theory to count unlabelled non oriented
  graphs on $n$ nodes without loops. To this end, we build the
  symmetric group $S_n$ seen as the group of the permutations of the
  $n$ nodes $\{i\}$ of the graphs, and the induced permutation group
  $G_n$ on the set $E$ of the $\binom n 2$ possible edges $\{i,j\}$
  between those nodes:}
\begin{Mexin}
S4 := Dom::SymmetricGroup(4):
G4 := Dom::PermutationGroupOnSets(S4, 2):
\end{Mexin}
\begin{Mvout}{hide=true}
\end{Mvout}
\eng{We compute next the cycle indicator of $G_4$. This is a symmetric
  function which encodes the statistic of the cycle types of the
  permutations in $G_4$:}
\begin{Mexin}
Z4 := G4::cycleIndicator()
\end{Mexin}
\begin{Mexout}
1/24 p[1, 1, 1, 1, 1, 1] + 3/8 p[2, 2, 1, 1] + 1/3 p[3, 3] +

   1/4 p[4, 2]
\end{Mexout}
\eng{This is to be interpreted as follows: in $G_4$, there are
  $6=|G_4|\cdot\frac{1}{4}$ permutations with one cycle of length $4$
  and one cycle of length $2$.  The interesting fact about this
  symmetric function is that, when evaluated on an alphabet
  $A=(a_1,\dots,a_n)$, it returns the generating series by weight for
  the functions from $E$ to a set of size $n$ whose elements are
  weighted by $A$. For example, a graph can be seen as a function from
  $E$ to a set with $2$ elements. Hence, the total number of
  unlabelled graphs is given by:}
\begin{Mexin}
Z4([1, 1])
\end{Mexin}
\begin{Mexout}
                              11
\end{Mexout}
\eng{Here they are:}

\begin{Mexin}
combinat::graphs::list(4)
\end{Mexin}
\begin{Mexout}
[[[], [], [], []], [[], [], [4], [3]], [[], [4], [4], [2, 3]],

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

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

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

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

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

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

\begin{Mexin}
nops(last(1))
\end{Mexin}
\begin{Mexout}
                              11
\end{Mexout}


We can refine the counting to get the generating series of unlabelled
graphs on $4$ nodes by number of edges:
\begin{Mexin}
expand(Z4([1, q]))
\end{Mexin}
\begin{Mexout}
                    2      3      4    5    6
             q + 2 q  + 3 q  + 2 q  + q  + q  + 1
\end{Mexout}
Double check:
\begin{Mexin}
map(combinat::graphs::list(4), g -> combinat::graphs::getEdgeNumber(g)/2)
\end{Mexin}
\begin{Mexout}
               [0, 1, 2, 3, 2, 3, 3, 4, 4, 5, 6]
\end{Mexout}

Such computations are carried out in a rather efficient way, so that
e.g. counting the number of graphs with 20 nodes takes just a few
seconds:
\begin{Mexin}
(Dom::PermutationGroupOnSets(Dom::SymmetricGroup(20),
                             2))::cycleIndicator()([1, 1])
\end{Mexin}
\begin{Mexout}
            645490122795799841856164638490742749440
\end{Mexout}

\eng{Those last computations highlights an important feature MuPAD-Combinat:

  integration of third-party software (Nauty)

  integration of combinatorial and algebra tools
  }


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