"Laplace discovered the remarkable correspondence between set theoretic operations and operations on formal power series, and put it to great use to solve a variety of combinatorial problems". - Gian-Carlo Rota [Rota.FOC]
The intervention of algebra in combinatorics came very early. For example, the basic tools of formal power series allow to easily compute using the complicated recurrence relations that appear when counting combinatorial objects. In the same spirit, a classical approach to count objects with symmetries is to break those symmetries by putting labels on the parts of the object; then there is a group acting on the labels, and the problem is reduced to compute the number of orbits under the action of this group. This is the classical method of Plya enumeration, which is treated extensively in A. Kerber's book Älgebraic combinatorics via finite group actions-[Kerber.ACF].
Conversely, in modern algebra, classification problems in group theory or representation theory, have given rise to many constructions (should we say algorithms ?) of algebraic objects from combinatorial inputs such as partitions, Young diagrams, Dynkin diagrams, finite oriented graphs (also known as quivers).
In both cases, there is a strong need to compute within combinatorial algebras (that is algebraic structures, such as vectors spaces or algebras, whose bases are indexed by combinatorial objects).
One of the first and most fundamental object in algebraic combinatorics is the algebra of symmetric functions. This was first understood by Mac-Mahon, who can be seen as the father of modern algebraic combinatoric. The interest of the algebra of symmetric functions comes from its extremely rich algebraic structure, starting from the fact that it is not only an algebra but also a Hopf algebra. Recall that a Hopf algebra is an algebra whose linear dual is also an algebra, with some compatibility between these two structures; essentially, there is an extra "decomposition law". The importance of Hopf algebras in combinatorics was perhaps first stressed by G.-C. Rota who pointed out how many combinatorial objects naturally possess a Hopf structure, because they can be composed and decomposed [Joni_Rota.1979]. In fact, under this combinatorial Hopf structure, many things that we would like to count transform naturally, yielding new tools in combinatorics. The study of symmetric functions was the starting point of a domain of combinatorics which is devoted to the study of combinatorial Hopf algebras. This is a rapidly growing field [Reutenaueur.1993,Hoffman.2002,Duchamp_Hivert_Thibon.2002], and it has applications in many different areas, such as representation theory of quantum groups in mathematics [Chari_Pressley.1995,Majid.2002], and renormalization of quantum fields in physics [Connes_Kreimer.1998,Kreimer.1998,Broadhurst_Kreimer.1999].
We (F. Hivert and N. M. Thiéry) had both written relatively large pieces of code for our own computations and discovered, a posteriori, that the core tools of our libraries were essentially the same. Furthermore, several excellent packages we used, like ACE, mu-EC or CS, were slowly dying out by lack of proper maintenance and distribution.
So, we decided to put our work in common and, in order to avoid as much as possible the Yet Another Combinatorial Package (tm) effect, we tried to analyze the situation. Basically, here are some of the problems we face:
Some time ago, N. M. Thiéry had made contacts with the MuPAD group, in order to integrate his library PerMuVAR, or parts of it, to the official release of MuPAD. This library contained several combinatorial routines, and he suggested some reorganization of the (rather minimal) combinat package of MuPAD, in order to ensure a better integration. His offer was warmly welcome, and the MuPAD group actually decided to make him the official maintainer of the combinat library, with full freedom for reorganizing and expanding it.
Is MuPAD the best platform for our needs? Technically, it has proved so far to be reasonably adapted to our requirements. The language is quite clean, and seems to scale properly as the package is growing. Most important, the collaboration with the MuPAD team is working smoothly; in particular they have been open-minded with respect to our (numerous) suggestions of improvements, including some sensitive kernel changes to polish the semantic of domains.
On the other hand, MuPAD is not open-source. We are not happy with this situation, and actively negotiate with them about this; for example, the recent release of the MuPAD library under an open source license was a precondition we had set for the inclusion of MuPAD-Combinat in this library. Our impression is that they are, in theory, very favorable to open-source principles; however, in practice, they judge that they could not currently release the MuPAD kernel under an open-source license without putting their very survival at great risks.
Our bet is that what is needed above all is a good development model. Ideally, such a package ought to be developed by a community, not just by one person or by one lab. We want to see how well the open-source development model can apply to the Algebraic Combinatorics community. The choice of open-source itself is obvious; however it is not clear whether the principles that made the success of general interest community-developed open-source software will apply because the targeted audience is relatively small. The main challenge is to reach quickly the critical mass above which the package will attract users and developers, and will grow on its own by the users contributions. To this end,
Anyway, the plan is to quickly extend the features of MuPAD-Combinat, while keeping it clean, organized, stable, and well documented. To this end, the core developers concentrate on the following:
http://mupad-combinat.sf.net
for how
you can contribute.
Note that there are many features that are not yet completely documented, or that would be trivial to add in a very short amount of time. So, if you miss a specific feature to get started, please feel free to ask for it. We are ready to invest some time in helping out new users: hopefully they will become future contributers. In general, we really are looking for feedback.
MuPAD Combinat, an open source algebraic combinatorics package