[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:
  2. combinat::compositions:
  3. combinat::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 + + + + - + - - - -
integerVectorsWeighted + + + + - + - - - -
integerListsLexTools - + + + - + - - - -
cartesianProduct + + + - - - - - - -
subsets + + + + + - - - - -
permutations + + + + + + + - - +
words + + + - - - - - - -
subwords + + + + + - - - - -
dyckWords + + + - - - - - - -
nonCrossingPartitions - - - - - - - - - -
tableaux + + + - - - - - - -
decomposableObjects + + + - - - - - + +
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 and default implementations for the standard combinatorial functions for counting, generating and listing elements in combinatorial classes:
  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:
  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:

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

Here is a classification:

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