1. Using predefined combinatorial functions and classes

For shortening the notations, we export the library combinat:

We start by some sample applications at random. We compute the first terms of the famous Catalan sequence, we generate the Cartesian product of three lists, we compute all permutations of the numbers , and we ask for all sub-words of the word [a, b, c, d]:

We turn now to various combinatorial classes. In short, a combinatorial class is a set of related combinatorial objects, like the set of all integer partitions. For every such classes, there is a sub-library of combinat. We can use the library combinat::partitions to list all the integer partitions of :

Let us draw the partition [3,2] using boxes (French or Cartesian notation):

We can fill those boxes with the numbers 1,2,3,4,5 so that the numbers are increasing along rows and columns to obtain so-called standard tableaux. Here are all the standard tableaux of shape [3,2]:

Ordered trees are another typical combinatorial class. Here are all the trees on four nodes:

and here are some more trees:

All the sub-libraries of combinat share a standardized interface. Let us look in more detail at the library combinat::partitions. We can count partitions:

list them under some extra conditions (here we list the partitions of whose length is between and ):

or compare them (lexicographically):

1.1. Generators

An important feature of MuPAD-Combinat are the so-called generators, which allow programs to run through huge lists of combinatorial objects without expanding the full lists into memory (in other programming languages, this paradigm is also often implemented via iterators or streams). Technically, a generator is a function g such that each call g() returns either a new object, or FAIL if no more objects are available. Let us build a generator for the partitions of :

Here is the first partition of :

Here is the second partition of :

And here are the remaining ones:

Generators come in handy when you want to work with the partitions of :

Most of the sub-libraries of combinat provide such generators.

See also the tutorial on generators.

1.2. Generic tools

Whenever possible (i.e. when it does not harm the computational complexity), we focus on providing the user with generic tools that cover many kinds of applications. For example, the libraries for partitions, integer vectors, and compositions share a very similar interface:

(Note: Inner = [2, 4, 2] means that the three parts should be respectively at least 2, 4, and 2).

Those libraries actually use internally the same computational engine combinat::integerListsLexTools:

In fact, the algorithm of combinat::integerListsLexTools could also be used to generate Motzkin and Dyck words, etc.

In the same spirit, instead of implementing a specific generator for standard tableaux, we implemented a generator for the linear extensions of a poset. We already reused this generator internally for generating standard binary search trees, and it could be reused as well for generating standard skew tableaux, standard ribbons, and so on(any volunteers?).

We also incorporated and extended the former CS library by S. Corteel, A. Denise, I. Dutour, and P. Zimmermann. This library allows one to manipulate combinatorial classes that can be defined by a deterministic grammar. Here we consider words of A's and B's without two consecutive B's. Such a word is

• either void,

• or the word "B",

• or a word ending by a "A",

• or finally a word ending by a "B".

In the two later cases, the beginning of the word is of the same type. This can be used to build a recursion process for generating recursively all such words. Such a recursion process is called a grammar. Note that this process leads to an unambiguous grammar: each word appears once and only once in the generation process; otherwise said the previous four cases are mutually exclusive. This is translated in MuPAD by

(Note: an Epsilon is an object of size 0 while an Atom is an object of size 1).

The result is not very readable, but this can be fixed by a quick substitution:

Alternatively, we could have provided some extra rewriting rules within the grammar. Notice that the preceding grammar generates the words in an order that is not so obvious. With some small reordering of the grammar, it is possible to ensure that the words are generated in the lexicographic order:

This seems to work nicely. Let us count those words:

You will certainly recognize the Fibonacci sequence. Not quite a surprise, the recurrence relation can be seen right away from the grammar. Actually, this recurrence relation is automatically determined by the library, and used for counting efficiently:

This also applies for several libraries which are based on combinat::decomposableObjects. For example, here is the recurrence relation for binary trees: