1. A guided tour through MuPAD-Combinat

The main purpose of this package is to provide tools for manipulating combinatorial (Hopf) algebras (although there is a large body of combinatorial features that can be used by themselves). To setup the stage, we start this guided tour by presenting a few sample computations with two examples of such algebras. Then, we proceed by illustrating with many examples the predefined combinatorial objects and how to define new ones and the predefined combinatorial algebras and how to define new ones. We conclude this tour by a summary of the current features.

1.1. Two examples of combinatorial algebras

In this tour we assume that the up-to-date Combinat package has been loaded into MuPAD. Depending on your installation you may have to enter a command such as package("Combinat"): or package("."): depending on your installation.

We define a shortcut for the algebra of symmetric functions MacDonald.SF.1995:

We consider the three first elementary symmetric polynomials in the variables {x1,...,x6}:

As one can see, the system distinguishes between abstract (or “symbolic”) symmetric functions such as S::e([3]), and the expansion of them as symmetric polynomials on the alphabet, stored here in variables such as e3. The call expand(f(alphabet)) for an abstract symmetric function f actually expands the corresponding symmetric polynomial over the alphabet.

Computing the product of two such symmetric polynomials yields a huge polynomial which is not quite practical to manipulate:

Instead, if we use the symmetries, the previous product can be expressed as compactly as:

Here, m[2, 1, 1, 1] denotes the monomial symmetric function obtained by summing all the monomials with one variable elevated to the power and three variables to the power . The product has been calculated at the level of abstract symmetric functions without expanding the polynomials, which is much faster and requires substantially less memory.

Hence, symmetric functions provide a typical example of combinatorial algebra whose bases are indexed by combinatorial objects (partitions), and where we want to compute efficiently.

As another typical example, we are currently working Hivert_Novelli_Thibon.PBT.2002,Hivert_Novelli_Thibon.PBT.2003 on the so-called Loday-Ronco algebra Loday_Ronco.1998, which is in particular of interest for theoretical physicists Brouder_Frabetti.2001,Foissy.2001.Thesis. It is implemented as a combinatorial algebra having binary trees as basis. Here we use computation in the fundamental basis denoted by p

.

For example, take the two following trees:

Technically, combinat::binaryTrees::unrank(k,n) returns the -th tree with nodes, while LRA::p(t) returns the basis element of LRA::p indexed by .

You can make a formal linear combination of t1 and t2:

or take their product:

Here is a more complicated product in this algebra:

*4 

1.2. MuPAD-Combinat, step by step

We now describe in more detail how all of this works. In the following, we assume that the package MuPAD-Combinat has been loaded into MuPAD. We also assume that the reader is somewhat familiar with the MuPAD syntax, and some of the exercises requires acquaintance with more advanced features of MuPAD like domain programming. We refer to the MuPADtutorial for details. Technicalities can be safely ignored in a first reading; they will be better understood after the explanations in the design notes.

1. Using predefined combinatorial functions and classes

1. Using generators

1. Defining new combinatorial classes

1. Using predefined combinatorial algebras

1. Defining new combinatorial algebras

1.2.1. Sample applications

We present here some typical applications that involve simultaneously the combinatorial and the algebraic tools of MuPAD-Combinat together with the general computer algebra tools of MuPAD.

First, we find the minimal polynomial of an element of the group algebra of the symmetric group of order :

Second, we use Pólya enumeration theory to count unlabelled non oriented graphs on nodes without loops. To this end, we build the symmetric group seen as the group of the permutations of the nodes of the graphs, and the induced permutation group on the set of the TODO: Math "import_TeX("\binom n 2")" possible edges between those nodes:

We compute next the cycle indicator of . This is a symmetric function which encodes the statistic of the cycle types of the permutations in :

This is to be interpreted as follows: in , there are permutations with one cycle of length and one cycle of length . The interesting fact about this symmetric function is that, when evaluated on an alphabet , it returns the generating series by weight for the functions from to a set of size whose elements are weighted by . For example, a graph can be seen as a function from to a set with elements. Hence, the total number of unlabelled graphs is given by:

whereas the generating series of unlabelled graphs on nodes by number of edges is:

Such computations are carried out in a rather efficient way, so that e.g. counting the number of graphs with 20 nodes takes just a few seconds:

If one is instead interested in counting multigraphs (graphs with multiple edges) by number of edges, the cycle indicator polynomial can be evaluated on the infinite alphabet . Infinite alphabets are not yet directly supported by MuPAD-Combinat; however this can easily be done by hand since the evaluation of the symmetric powersum on the alphabet is obtained by encoding as TODO: Math "1+q+q^2+Symbol::hellip=import_TeX("\frac1{1-q}")" and substituting by in this formula:

Now, the number of multigraphs with 0 to 4 edges can be obtained by Taylor expansion:

In fact, this method is used to implement counting in the combinatorial class combinat::integerVectorsModPermutationGroup:

1.2.2. Advanced algebraic structures

The current development aims to provide a framework for advanced algebraic structures, such as modules with several bases, Hopf algebras, operads, with plans for Lie algebras in the long run. In this section, we demonstrate how to implement such structures. At the time of writing, the user interface is not fully stabilized, so please check the latest available documentation before trying out the examples.

1. Algebras with several bases

1. Combinatorial Hopf Algebras

1.2.3. Current features

We conclude this guided tour by a summary of the current features. A first part of the package consists of predefined libraries to count, enumerate, and manipulate standard combinatorial objects (partitions, compositions, sets, words, permutations, tableaux, trees, Symbol::hellip), together with generic tools to help define new combinatorial classes:

• A computational engine for dealing with integer vectors with prescribed constraints (monomials, compositions, partitions, Dyck paths, Symbol::hellip)

• A computational engine for generating linear extensions of posets (standard young tableaux, standard ribbons, Symbol::hellip)

• A refactored and extended version of the former CS library by S. Corteel, A. Denise, I. Dutour, and P. Zimmermann to deal with objects defined by a recursive grammar.

Most predefined libraries actually make use of these engines.

A second part consists of tools to build combinatorial algebras. The typical usage is to take a vector space with basis indexed by some combinatorial objects, to define a product for two basis elements and to extend the product by bilinearity. The system automatically takes care of the data structure of algebraic elements, of extensions of functions by linearity, bi-linearity, or associativity, of conversions between different bases, etc. Similarly, one may define coproducts, antipodes, and similar operators, to implement more involved structures such as Hopf algebras. Some preliminary work has been done to manipulate Lie algebras and operads as well. In short, the system takes care of the algebraic bookkeeping, so that one can concentrate on the underlying combinatorics rather than on the programming.

As examples of usage and applications, we provide a library for the algebra of symmetric functions, and we have (currently undocumented) libraries for the algebra of non commutative symmetric functions, the algebra of (free) quasi-symmetric functions, the Loday-Ronco algebra, the Weyl algebra, the rational Steenrod algebra, the type-A Hecke and Hecke-Clifford algebras, as well as invariant rings of permutation groups, and group algebras.

In the future (or near future if you help us!)we plan to provide predefined libraries for the free symmetric algebra, the algebra of matrix quasi symmetric functions, the descents and peaks algebras, general Ore-algebras, the symmetric Weyl algebra, the algebra of multi-symmetric functions, the divided power algebra, free Lie algebras, etc.

Finally, we provide libraries for manipulating weighted automatons and related (tropical) semi-rings.