Combinatorics (package Combinat)

combinat – Combinatorics (package 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.3.2. 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 -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)

1.1. Structure of the library

The library package contains three different sorts of features: functions for computing classical integer sequences, combinatorial classes of classical combinatorial objects, and libraries of low-level utilities including 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:

combinat::chooseNK provides functions for choosing k elements out of n without repetitions.
combinat::multisetsNK provides functions for choosing k elements out of n with repetitions.
combinat::permutationsNK provides functions dealing with permutations of k elements out of n.
combinat::splitNK provides functions for splitting a set of n elements into two complementary sets of k and n-k elements.
combinat::setPartitions provides functions dealing with set partitions, i.e., with partitions of a set into unordered subsets.
combinat::setPartitionsOrdered provides functions dealing with ordered set partitions, i.e., with partitions of a set into ordered subsets.
combinat::skewPartitions provides functions dealing with skew partitions, i.e., pairs of two partitions, where the second partition is a inner partition of the first.
combinat::compositions deals with compositions of natural numbers, i.e., with lists of natural numbers with a fixed sum.
combinat::integerVectors deals with vectors of nonnegative integers of fixed length and fixed sum.
combinat::integerVectorsWeighted is similar, but the sum is replaced by a weighted sum.
combinat::cartesianProduct provides functions dealing with the Cartesian product of a finite number of sets or lists.
combinat::subsets deals with subsets of a set.
combinat::words deals with words, i.e., lists of fixed length consisting of elements of a specified alphabet.
combinat::subwords deals with subwords: Starting with a given list, delete any number of entries.
combinat::permutations works on permutations of lists and also standard permutations (i.e. permutations of ).
combinat::dyckWords deals with Dyck words. These can be interpreted as words of well balanced parentheses.
combinat::necklaces and combinat::lyndonWords allow for generating (aperiodic) words up to cyclic rotations.
combinat::integerMatrices deals with matrices of nonnegative integers of fixed sum for rows and columns.
combinat::tableaux, combinat::skewTableaux, combinat::ribbons provides utilities for tableaux, skew tableaux, and tableaux of ribbon shape respectively. Those objects are fundamental, among other things, in the representation theory of the symmetric group and for computing with symmetric functions and polynomials.
combinat::ribbonsTableaux deals with ribbon tableaux, which appear when studying -analogues of symmetric functions.
combinat::decomposableObjects deals with objects that can be described recursively by a grammar.
combinat::trees provides a basic data structure for rooted trees, as well as functions to generate and manipulate ordered unlabelled ones.
combinat::binaryTrees provides a basic data structure for rooted binary trees as well as functions to generate and manipulate ordered unlabelled ones.
combinat::treesGeneric and combinat::labelledBinaryTrees provides functions to generate all sorts of trees (ordered or not, labelled or not, ...).
combinat::labelledBinaryTrees provides functions to generated an manipulate labelled binary trees.
combinat::graphs provides an interface with the C++ library Nauty for generating unlabelled simple graphs.
combinat::linearExtensions provides functions to enumerate linear extensions of partially ordered sets.

Some of the previous combinatorial classes provide further sub-domains, and this feature will be extensively extended in the future. For example:

combinat::words::shuffle: utilities for the shuffle product of two words.
combinat::compositions::finer: the combinatorial class of compositions finer than a given one;

Many of the combinatorial classes are facade domains: their objects are represented using elements of basic MuPAD domains. For example, partitions or permutations are represented using plain lists of integers (of the domain DOM_LIST). In particular, no constructor needs to be called to create such objects.

Objects of the other non-facade combinatorial classes are constructed with the standard MuPAD idiom: cl(objdesc) constructs the object of the class cl whose description is objdesc. For example combinat::labelledBinaryTrees([a,[b],[c]]) constructs a labelled binary tree with three nodes labelled a,b,c.

Standard interface

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(rsize)	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 combinatorial classes, 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); this feature is solely provided as a syntactic sugar for interactive use; please do not use it in programs! In particular for the non-facade domains this shortcut may be ambiguous with the creation of the objects of the domain and thus may be disabled.

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.

Most combinatorial classes provide further methods, such as combinat::permutations::inverse. See the corresponding documentation for details.

The combinat library also contains some support sub-libraries, which are used intensively by the previous ones, like:

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.
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:

combinat::bell: Bell numbers;
combinat::catalan: Catalan numbers;
combinat::stirling1: Stirling numbers of the first kind;
combinat::stirling2: Stirling numbers of the second kind;
combinat::modStirling: Modified Stirling numbers;