Computing The Molecular Expansion Of Species With The Maple Package Devmol

Pierre Auger   ; Gilbert Labelle   ; Pierre Leroux

Séminaire lotharingien de combinatoire, Tome 49 (2002-2004)

Résumé

Intuitively, the molecular expansion of a species F is a classification of its structures according to their size and symmetries. It can be seen as a refinement of the (ordinary) generating function for the number of unlabelled F-structures of size n. The goal of the Maple package Devmol is to compute such molecular expansions, up to a specified degree, for species of the so-called cyclo-set type (in French: espèces cyclo-ensemblistes). These are species which have either an explicit or a recursive definition in terms of the species L, of lists, E, of sets, and C, of oriented cycles.

In this paper, we first recall some basic results about molecular expansions. In particular, we give some examples of molecular expansions, namely for the species of "Rooted trees" and of "Husimi graphs", weighted by their block-size distribution. We also describe briefly the addition formulas for the basic species which are essential for the recursive computation of molecular expansions.

Subsequently, we give a detailed description of the package Devmol, and we conclude with two examples of applications, to rooted trees weighted by a leaf counter and to connected graphs, all of whose blocks are in a given family B of species of cyclo-set type.