[Next] [Contents]

## The library `combinat`

The `combinat` library provides combinatorial functions, as well as tools for counting, generating, and manipulating combinatorial objects.

It consists of a subset of the algebraic combinatorics contribution package MuPAD-Combinat version 1.0. The full featured package, when installed, can be loaded with:

    >> package("Combinat")

See `http://mupad-combinat.sourceforge.net/` for details.

The library functions are called using the library name `combinat` and the name of the function. E.g., use

    >> combinat::bell(5)

to compute the 5-th Bell number. This mechanism avoids naming conflicts with other library functions.

If this is found to be inconvenient, then the routines of the `combinat` library may be exported via `export`. E.g., after calling

    >> export(combinat, bell)

the function `combinat::bell` may be called directly:

    >> bell(5)

All routines of the `combinat` library are exported simultaneously by

    >> export(combinat)

The functions and sub-libraries available in the `combinat` library can be listed using

    >> info(combinat)

### Structure of the library

The library package contains three different sorts of features: functions for computing classical sequences of numbers, domains called combinatorial classes of classical combinatorial objects including functions for counting and generating and manipulating these objects and finally libraries of handy tools including highly versatile and configurable algorithms for generating various classes of objects.

The most important part of the `combinat` library, i.e. the part devoted to combinatorial objects, is organized in separate domains with similar interfaces, one for each combinatorial class. For example, `combinat::cartesianProduct::count` is used to determine the number of elements in a cartesian product, while `combinat::subsets::count` returns the number of subsets of a set. The following domains are provided:

1. `combinat::partitions` provides functions dealing with partitions, i.e., decreasing lists of natural numbers with a fixed sum.
2. `combinat::skewPartitions` provides functions dealing with skew partitions, i.e., a pair of two partitions, where the second partition is a inner partition of the first.
3. `combinat::compositions` deals with compositions of natural numbers, i.e., with lists of natural numbers with a fixed sum.
4. `combinat::integerMatrices` deals with matrices of nonnegative integers of fixed sum for rows and columns.
5. `combinat::integerVectors` deals with vectors of nonnegative integers of fixed length and fixed sum.
6. `combinat::integerVectorsWeighted` is similar, but the sum is replaced by a weighted sum.
7. `combinat::cartesianProduct` provides functions dealing with the Cartesian product of a finite number of sets or lists.
8. `combinat::subsets` deals with subsets of a set.
9. `combinat::permutations` works on permutations of lists and also standard permutations (i.e. permutations of {1,...,n}).
10. `combinat::words` deals with words, i.e., lists of fixed length consisting of elements of a specified alphabet.
11. `combinat::subwords` deals with subwords: Starting with a given list, delete any number of entries.
12. `combinat::dyckWords` deals with Dyck words. These can be interpreted as words of well balanced parentheses.
13. `combinat::tableaux` provides utilities for tableaux. These are useful for computations on symmetric functions and polynomials, among other things.
14. `combinat::decomposableObjects` deals with objects that can be described recursively by a grammar.
15. `combinat::trees` provides functions to generate and manipulate trees.
16. `combinat::binaryTrees` provides functions to generate and manipulate binary trees.
17. `combinat::linearExtensions` provides functions to enumerate linear extensions of partially ordered sets.

Some of the previous combinatorial classes provide further sub-domains, this feature should be extensively extended in the future:

1. `combinat::binaryTrees`:
   - `combinat::binaryTrees::fromSaillance` for enumerating binaryTrees by saillance.
   - `combinat::binaryTrees::shuffle` with utilities for the shuffle product of two binary trees.
2. `combinat::compositions`:
   - `combinat::compositions::finer` to deal with compositions finer than a given one;
   - `combinat::compositions::fatter` to deal with compositions fatter than a given one;
   - `combinat::compositions::finerVectors` to deal with integer vectors finer than a given composition;
3. `combinat::words`:
   - `combinat::words::fromStandard` to enumerate words with a given standard permutations;
   - `combinat::words::shuffle` to compute the shuffle of two words.

To provide default implementations and to ensure that the interfaces are compatible, all combinatorial domains belong to the category `Cat::CombinatorialClass`. The purpose of this category is to specify the behavior of several standardized functions. Note that a specific combinatorial class does not need to implement all these functions. The category `Cat::CombinatorialClass` also provides default implementations (possibly inefficient) for some of these.

Here are the list and the meanings of these standard functions:

`isA(`object`, <size>)` | is an object an element of the class (of size `size`)
`size(`object`)` | size of the object `object`
`count( <size>)` | number of objects (of size `size`)
`generatingSeries(s, <ident>)` | generating series by size
`generator( <size>)` | generator for all the objects (of size `size`)
`list( <size>)` | list of all the objects (of size `size`)
`first( <size>)` | first object (of size `size`) or `FAIL`
`last( <size>)` | last object (of size `size`) or `FAIL`
`Next(s)` | next object after `s` or `FAIL`
`previous(s)` | previous object before `s` or `FAIL`
`rank(s)` | rank of the object `s`
`unrank(r <, size>)` | `r`-th object (of size `size`), or `FAIL`
`random( <size>)` | random object (of size `size`) or `FAIL`
`_less(s1, s2)` | comparison of the objects `s1` and `s2`

Note that `Next` is capitalized because `next` is a reserved keyword in MuPAD.

Note also that, in most packages, these functions take some other optional arguments. In this case, the functions `isA`, `count`, `list`, and `generator` accept the same arguments.

For most combinatorial classes `cl`, the call `cl(`size`)` is a shortcut for `cl::list(`size`)`; exceptions to this rule include, e.g. `combinat::partitions`; this feature is solely provided as a syntactic sugar for interactive use; please do not use it in programs!

In a near future, we plan to add functions to manipulate combinatorial classes, for example to construct subclasses of a given class. So it is very important to stick closely to these conventions.

The following methods are implemented in more than one of those libraries:

| `count` | `generator` | `list` | `first` | `last` | `Next` | `previous` | `rank` | `unrank` | `random`
`partitions` | + | + | + | + | - | + | - | - | - | -
`skewPartitions` | + | + | + | - | - | - | - | - | - | -
`compositions` | + | + | + | + | - | + | - | - | - | -
`integerMatrices` | + | + | + | - | - | - | - | - | - | -
`integerVectors` | + | + | + | + | - | + | - | - | - | -
`integerVectors` `Weighted` | + | + | + | + | - | + | - | - | - | -
`integerLists` `LexTools` | - | + | + | + | - | + | - | - | - | -
`cartesianProduct` | + | + | + | - | - | - | - | - | - | -
`subsets` | + | + | + | + | + | - | - | - | - | -
`permutations` | + | + | + | + | + | + | + | - | - | +
`words` | + | + | + | - | - | - | - | - | - | -
`subwords` | + | + | + | + | + | - | - | - | - | -
`dyckWords` | + | + | + | - | - | - | - | - | - | -
`nonCrossing` `Partitions` | - | - | - | - | - | - | - | - | - | -
`tableaux` | + | + | + | - | - | - | - | - | - | -
`decomposable` `Objects` | + | + | + | - | - | - | - | - | + | +
`trees` | + | + | + | - | - | - | - | - | + | +
`binaryTrees` | + | + | + | - | - | - | - | - | + | +

Many of the sub-libraries provide further methods, such as `combinat::permutations::inverse`. See the corresponding documentation for details.

The `combinat` library also contains the following support sub-libraries, which are used intensively by the previous ones.

1. `combinat::generators` provides utilities for creating and manipulating generators, i.e., functions which, on each call, return the next element of a (possibly infinite) sequence of values.
2. `combinat::integerListsLexTools` provides an algorithm for generating, in lexicographic order, lists of natural numbers satisfying certain constraints.

Finally some classical combinatorial sequences of numbers are provided:

1. `combinat::bell`: Bell numbers;
2. `combinat::catalan`: Catalan numbers;
3. `combinat::stirling1`: Stirling numbers of the first kind;
4. `combinat::stirling2`: Stirling numbers of the second kind;
5. `combinat::modStirling`: Modified Stirling numbers;

### Categories

The `combinat` library is articulated around three main categories:

1. `Cat::CombinatorialClass`, which is the basic category for combinatorial objects. It provides basic functions for types
   - `isA`,
   - `testtype`
   and default implementations for the standard combinatorial functions for counting, generating and listing elements in combinatorial classes:
   - `count`,
   - `generator`
   - `list`
2. `Cat::DecomposableClass` is used as a front-end category for combinatorial classes based on the domain `combinat::decomposableObjects`, and is devoted to objects that can be described by some recursive grammar. This category is a subcategory of `Cat::CombinatorialClass`, and it provides also by default these two more functions:
   - `unrank`,
   - `random`
3. `Cat::IntegerListsLexClass` is used as a front-end category for combinatorial classes based on `combinat::integerListsLexTools`, and is devoted to lexicographic enumerations of list of integers with a fixed sum and some prescribed constraints. It is a subcategory of `Cat::CombinatorialClass` and provide also by default the functions:
   - `first`,
   - `Next`,
   - `_less`

Most of the libraries are in one of those categories (except `combinat::generators` and famous numbers: Bell, Catalan, Stirling, ...).

Here is a classification:

- `Cat::CombinatorialClass`
  1. `combinat::binaryTrees::fromSaillance`
  2. `combinat::binaryTrees::shuffle`
  3. `combinat::cartesianProduct`
  4. `combinat::compositions::finer`
  5. `combinat::compositions::fatter`
  6. `combinat::compositions::finerVectors`
  7. `combinat::integerListsLexTools`
  8. `combinat::integerMatrices`
  9. `combinat::integerVectorsWeighted`
  10. `combinat::linearExtensions`
  11. `combinat::nonCrossingPartitions`
  12. `combinat::permutations`
  13. `combinat::skewPartitions`
  14. `combinat::subsets`
  15. `combinat::subwords`
  16. `combinat::tableaux`
  17. `combinat::words`
  18. `combinat::words::fromStandard`
  19. `combinat::words::shuffle`
- `Cat::DecomposableClass`
  1. `combinat::binaryTrees`
  2. `combinat::decomposableObjects`
  3. `combinat::dyckWords`
  4. `combinat::labelledBinaryTrees`
  5. `combinat::trees`
- `Cat::IntegerListsLexClass`
  1. `combinat::compositions`
  2. `combinat::integerVectors`
  3. `combinat::partitions`

### Examples

In this section, we pick a few sample applications at random. First, we export the `combinat` library to save us some typing:

    >> export(combinat):

Note that the sub-libraries such as `combinat::partitions` are not intended to be exported.

In our first examples, we use the abbreviated calls for list generation. We generate the Cartesian product of three lists, we compute all permutations of the numbers 1, 2, 3, and we ask for all sub-words of the word `[a, b, c, d]`:

    >> cartesianProduct([1,2,3],[a,b],[i,ii,iii])

          [[1, a, i], [1, a, ii], [1, a, iii], [1, b, i], [1, b, ii],

             [1, b, iii], [2, a, i], [2, a, ii], [2, a, iii], [2, b, i],

             [2, b, ii], [2, b, iii], [3, a, i], [3, a, ii],

             [3, a, iii], [3, b, i], [3, b, ii], [3, b, iii]]

    >> permutations(3)

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

             [3, 2, 1]]

    >> subwords([a,b,c,d])

          [[], [a], [b], [c], [d], [a, b], [a, c], [a, d], [b, c],

             [b, d], [c, d], [a, b, c], [a, b, d], [a, c, d], [b, c, d],

             [a, b, c, d]]

Dyck words, as stated above, can be interpreted as balanced sequences of parentheses:

    >> map(dyckWords(4), dyckWords::toString)

          ["(((())))", "((()()))", "((())())", "((()))()", "(()(()))",

             "(()()())", "(()())()", "(())(())", "(())()()", "()((()))",

             "()(()())", "()(())()", "()()(())", "()()()()"]

[Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package