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)
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.
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;
The combinat library is articulated around four main categories:
Cat::CombinatorialClass, which is the basic category for combinatorial classes. It defines basic type-checking functions:
isA,
testtype
and provides some default implementations for the standard combinatorial functions for counting, generating and listing elements in combinatorial classes:
count,
generator
list
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.
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
Cat::TreesClass, which is a specialization of Cat::DecomposableClass for tree-like objects.
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:
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 , and we ask for all sub-words of the word [a, b, c, d]:
cartesianProduct([1,2,3],[a,b],[i,ii,iii])
permutations(3)
subwords([a,b,c,d])
Dyck words, as stated above, can be interpreted as balanced sequences of parentheses:
map(dyckWords(4), dyckWords::toString)
combinat::alternatingSignMatrices – alternating sign matrices
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::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::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