combinat – Combinatorics (package Combinat)

1. 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.3.2. The full featured package, when installed, can be loaded with:


See for details.

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


to compute the math-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:


All routines of the combinat library are exported simultaneously by



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



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:


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


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 of the object object  


number of objects (of size size)

generatingSeries(s, ident)  

generating series by size


generator for all the objects (of size size)


list of all the objects (of size size)


first object (of size size) or FAIL  


last object (of size size) or FAIL  


next object after s or FAIL  


previous object before s or FAIL  


rank of the object s  


r-th object (of size size), or FAIL  


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:

  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;



The combinat library is articulated around four main categories:

  1. Cat::CombinatorialClass, which is the basic category for combinatorial classes. It defines basic type-checking functions:

    and provides some default implementations for the standard combinatorial functions for counting, generating and listing elements in combinatorial classes:


  2. Cat::GradedCombinatorialClass, which is the category of combinatorial objects whose size is a nonnegative integer. In particular the calls count(n), generator(n), list(n) are meaningful for any integer n. It is a subcategory of the category Cat::CombinatorialClass.

  3. Cat::DecomposableClass, which is a front-end category for combinatorial classes based on the domain combinat::decomposableObjects. As such, it is devoted to objects that can be described by some recursive grammar. This category is a subcategory of Cat::GradedCombinatorialClass and provides default implementations for the functions: unrank, and random

  4. Cat::TreesClass, which is a specialization of Cat::DecomposableClass for tree-like objects.

  5. Cat::IntegerListsLexClass, which is a front-end category for combinatorial classes based on combinat::integerListsLexTools. As such, it is devoted to lexicographic enumerations of list of integers with a fixed sum and some prescribed constraints. It is a subcategory of Cat::GradedCombinatorialClass and provides default implementations for the functions: first, Next, and _less.


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


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 math, and we ask for all sub-words of the word [a, b, c, d]:







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

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


2. Help files

combinat::alternatingSignMatrices – alternating sign matrices

combinat::bell – Bell numbers

combinat::binaryTrees – binary trees

combinat::cartanMatrix – Cartan Matrices

combinat::cartanType – Cartan types, for classification of simple groups, Lie algebras, ...

combinat::cartesianProduct – cartesian products

combinat::catalan – Catalan numbers

combinat::chooseNK – Low level combinatorial class for the choices of k elements out of n without repetitions

combinat::compositions – compositions of an integer

combinat::compositionsSigned – The combinatorial class of signed compositions

combinat::countingFunctions – counting functions

combinat::coxeterMatrix – Coxeter matrices

combinat::crystalOperators – a library for crystal operators

combinat::crystals – domain with specific crystal implementations

combinat::decomposableObjects – decomposable combinatorial objects

combinat::dyckWords – Dyck words

combinat::dynkinDiagram – Dynkin Diagrams

combinat::freeTreesLabelled – labelled free trees

combinat::finiteClass – Finite combinatorial classes.

combinat::generators – generators

combinat::graphPaths – paths in a directed graph with labelled arrows

combinat::graphs – unlabelled graphs, an interface with Nauty

combinat::guess – guessing sequences

combinat::independentSetsOfVectorSpace – independent sets of a vector space

combinat::integerListsLexTools – lexicographic generation of lists of integers

combinat::integerMatrices – integer matrices

combinat::integerVectorsWeighted – weighted integer vectors

combinat::integerVectors – integer vectors

combinat::integerVectorsOfLength – integer vectors of fixed length

combinat::integerVectorsModPermutationGroup – integer vectors modulo a permutation group

combinat::labelledBinaryTrees – labelled binary trees

combinat::permutationsSigned – The combinatorial class of signed permutations

combinat::rootLattice – Root lattices

combinat::rootSystem – Root systems

combinat::triangulationsOfRegularPolygon – The combinatorial class of the triangulations of a regular polygon

combinat::weightLattice – Weight lattices

combinat::LattE – an interface with LattE (Lattice Point Enumeration)

combinat::linearExtensions – linear extensions (topological sortings) of DAGs or posets

combinat::lrcalc – Interface with lrcalc

combinat::lyndonWords – Lyndon words

combinat::lyndonWords::fromEvaluation – Lyndon words with prescribed evaluation

combinat::lyndonWords::fromContent – Lyndon words with prescribed content

combinat::modStirling – modified Stirling numbers

combinat::multisetsNK – Low level combinatorial class for the multisets of k elements out of n

combinat::necklaces – necklaces

combinat::necklaces::fromEvaluation – necklaces with prescribed evaluation

combinat::necklaces::fromContent – necklaces with prescribed content

combinat::nonCrossingPartitions – non crossing set partitions

combinat::parkingFunctions – parking functions

combinat::partitions – partitions of an integer

combinat::permutations – permutations

combinat::permutationsNK – Low level combinatorial class for permutations of k elements out of n

combinat::ribbons – ribbons and tableaux of ribbon shape

combinat::ribbonsTableaux – ribbon tableaux

combinat::setPartitions – set partitions of a set

combinat::setPartitionsOrdered – ordered set partitions of a set

combinat::skewPartitions – skew partitions

combinat::skewTableaux – Young skew tableaux

combinat::splitNK – Low level combinatorial class for knk-ordered set partitions.

combinat::stirling1 – Stirling numbers of the first kind

combinat::stirling2 – Stirling numbers of the second kind

combinat::subClass – Subclass of a combinatorial classes.

combinat::subsets – subsets of a set

combinat::subwords – subwords of a word

combinat::tableaux – Young tableaux

combinat::trees – ordered trees

combinat::treesGeneric – all sorts of trees

combinat::warnDeprecated – issue of warnings when deprecated features are used

combinat::words – words

combinat::yamanouchi – Yamanouchi words