\documentclass[12pt]{article}
%
\usepackage[dvips]{graphicx}
\usepackage[dvips]{epsfig}
\usepackage{color}
%\usepackage{maple2e}
%\usepackage{mapletab}
%
%%Macros d'Andre Lauzon pour imiter le style maple worksheet
\input{lacimmaple}
%
%%Pour avoir le style maple en couleur.
%%Remplacer par \no pour le noir et blanc
\UseMapleColor{\yes}  %cf lacimmaple
%
%%Pour avoir des paragraphes plus lisibles
\parindent=3ex
\parskip=2ex plus .5ex minus .5ex
%
\font\retct = msbm10 at 12pt
\font\retci = msbm7
\font\retcii = msbm5
\font\gmin = cmti12 at 17pt
%
%\newcounter{feve}
\newcommand{\rond}{\> \mbox{\raise.25ex\hbox{{\scriptsize $\circ$}}} \>}
\newcommand{\Phit}{{\mit \Phi}}
\newcommand{\Q}{\mbox{\retct Q}}
\newcommand{\Examples}{\noindent \textbf{Examples.}}
\newcommand{\Psit}{{\mit \Psi}}
\newcommand{\N}{\mathchoice{\mbox{\retct N}}{\mbox{\retct N}}{\mbox{\retci N}}{\mbox{\retcii N}}}
\newcommand{\C}{\mbox{\retct C}}
\newcommand{\rr}{\kern-0,12em}
\newcommand{\Gcon}{\mathcal{C}} 
\newcommand{\arbres}{\mbox{\gmin a}}
\newcommand{\molexp}{molecular expansion}
\newcommand{\Hu}{\mathop{\rm Hu}\nolimits} 
\newcommand{\Ca}{\mathop{\rm Ca}\nolimits}  % pour faire l'esp\`ece des cactus (libres)
\newcommand{\Oc}{\mathop{\rm Oc}\nolimits}  % pour faire l'esp\`ece des cactus orientes
\newcommand{\B}{\mathcal{B}}    %pour faire le B caligraphique
\newcommand{\Bprime}{\mathcal{B}^{\prime}}    %pour faire le B caligraphique prime
\newcommand{\Bpoint}{\mathcal{B}^{\bullet}}    %pour faire le B caligraphique pointe
\newcommand{\CB}{C_{\mathcal{B}}}       % pour faire C_B
\newcommand{\CBprime}{C_{\mathcal{B}}^{\prime}}       % pour faire C_B prime
\newcommand{\CBpoint}{C_{\mathcal{B}}^{\bullet}}       % pour faire C_B pointe
\newcommand{\CBB}{C_{\mathcal{B}}^{\diamondsuit}}  % pour faire C_B pointe en un bloc
\newcommand{\CBSB}{C_{\mathcal{B}}^{\bullet\negthinspace\diamondsuit}}

%\newcommand{\cat}{\mathrm{Cat}}
\font\EUFMx=eufm10 at 10pt 
\font\EUFMvii=eufm10 at 7pt 
\font\EUFMv=eufm10 at 5pt 
\newfam\EUFMfam 
\def\EUFM{\fam\EUFMfam\EUFMx} 
\textfont\EUFMfam=\EUFMx 
\scriptfont\EUFMfam=\EUFMvii 
\scriptscriptfont\EUFMfam=\EUFMv 
%
%
\title{Computing the molecular expansion of species with the Maple package
\emph{Devmol}}
%
\author{Pierre Auger, Gilbert Labelle and Pierre Leroux\\
        LaCIM, Universit\'e du Qu\'ebec \`a Montr\'eal}
%
\date{}
%
\begin{document}
%
\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 49 \rms (2003), Article~B49z\hfill}
\def\thepage{}
%
%
%
% Introduction
\section*{Introduction}
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 \emph{tilde} generating function
%
\begin{equation}
\widetilde{F}(x) = \sum_{n\geq0}\widetilde{f}_nx^n \label{eq:ftilde}
\end{equation}
%
of the number $\widetilde{f}_n$ of unlabelled $F$-structures of size $n$.

For example, the tilde generating function $\widetilde{A}(x)$ of the species
$A$ of (free) rooted trees, up to size $6$, is
%
\begin{equation}
\widetilde{A}(x) = x+x^2+2x^3+4x^4+9x^5+20x^6+\cdots. \label{eq:atildex}
\end{equation}
%
It is refined by the molecular expansion of $A$ given in Section 1.1
(see (\ref{eq:expandrootedtrees})) where each unlabelled rooted tree is represented by
a term (a molecular species) describing its symmetries. 
For example, for degree 3, the term $X^3$ represents the rooted chain
\ \raisebox{-2pt}{\includegraphics[width=1.5cm]{chain}}
\ while \(XE_2(X)\) represents the rooted star
\ \raisebox{-5pt}{\includegraphics[width=1cm]{star}} \ .
%

The goal of the Maple package \emph{Devmol} is to compute such molecular expansions,
up to a specified degree, for species of the so-called \emph{cyclo-set type} 
(in French: esp\`eces 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. More precisely, since we are dealing
with species of bounded degrees, the specifications will be in terms of the
species $L_n$, $E_n$, and $C_n$, for $n\geq0$, where the index $n$ denotes the
restriction to degree $n$.  Note that $L_0 = E_0 = 1$, $C_0=0$, $L_1(X)=E_1(X)=C_1(X)=X$,
 $C_2=E_2$ and $L_n(X)=X^n$.

Moreover, \emph{Devmol} has the capacity to handle weighted multisort species with scalar
coefficients in the complex field $\C$. The sort variables have to be declared, except $X,Y,Z$ which
are sort variables by default, and the weights have to be monomials (commutative words) in some
indeterminates which must be declared as weight variables, except $t$ which is a weight
variable, by default.  All other unspecified
variables or ``names" are considered as complex scalars.

The reader is refered to \cite{Jo81} and \cite{BLL98} for a basic presentation
of species theory and also to \cite{Ch92} where some molecular expansions are computed
using Maple.  We review here some of the notions related to molecular
species.
Two structures of a species $F$ are \emph{isomorphic} if one can be obtained
from the other by a relabelling along a bijection. \emph{Unlabelled} $F$-structures
can be seen as isomorphism classes of $F$-structures. 
A species $M$ is called \emph{molecular} if it has only one isomorphism class.
It is completely determined by the stabilizer $H=\rm{Stab}(s)$ of one of its structures,
say $s\in M[n]$, where $n$ is the degree of $M$ and $[n]=\{1,2,\ldots,n\}$.
We write $M(X)={X^n/H}$. In particular, we have 
%
\begin{equation}
L_n = {X^n/\{1\}}, \ \ \ E_n = {X^n/S_n}, \ \ \ C_n = {X^n/\langle\rho\rangle},
\end{equation}
where $S_n$ denotes the symmetric group on $[n]$ 
and $\rho$ generates a cyclic subgroup of order $n$ of $S_n$.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
%\markboth{\SMALL ROLAND BACHER AND LAURENT MANIVEL}{\SMALL HOOKS AND POWERS OF\ PARTS IN PARTITIONS}
%
%

For a general molecular species 
$$M(X)={X^n/H},$$ 
the cycle index series $Z_M(x_1,x_2,\ldots)$ coincides with the cycle index polynomial 
$Z_H(x_1,x_2,\ldots)$ of $H\leq S_n$.
Molecular species are closed under the basic operations of product
and (partitional) composition of species, corresponding to the operations
of product and of wreath product of their stabilizers, respectively.
See \cite{BLL98}, Section 4.6, for more details. 

Two $F$-structures are called \emph{similar} if they have conjugate stabilizers.
It is equivalent to say that one structure can be relabelled in such a way that
they have exactly the same stabilizer. This corresponds to isomorphic molecular 
species.  Hence similar (but non-isomorphic) 
$F$-structures give rise to multiplicities
in the molecular expansion of $F$. For example, the three rooted trees shown in
the first row of Figure \ref{fig:arbo5} are not isomorphic but they are similar
since they are of the type $X^{3}{E_{2}}(X)$, having only a two-element group
generated by a transposition as stabilizers. This explains the multiplicity $3$
in the term $3X^{3}{E_{2}}(X)$. Similarly, the three rooted trees in the second
row are similar since they are asymmetric, giving rise to the term $3X^5$
in the molecular expansion of the species $A$ of rooted trees.

   The \emph{molecular expansion} of a species $F$ is defined as the equality
(natural isomorphism)
\begin{equation}
F = \sum_{M\in\cal{M}} f_M M, \label{eq:molexpf}
\end{equation}
where $f_M$ is the multiplicity of the molecular species $M$ in $F$ and $\cal M$
is an appropriate set of molecular species.


   In the following section, we present two examples of molecular expansions:
for rooted trees, and for Husimi graphs weighted by monomials describing their
block-size distributions. In Section 2, we describe briefly the addition formulas
for the basic molecular species $X^n$, $E_n$, and $C_n$, which are essential
for the computation of molecular expansions. In Section 3, we show how these
formulas can be used to compute recursively the molecular expansion of the
species of $R$-enriched rooted trees, when $R$ itself is of cyclo-set type,
and also of $R$-enriched trees, using the Dissymmetry Theorem for trees.

The Maple package Devmol was developped by Pierre Auger at LaCIM
for the purpose of computing molecular expansions. 
We give a detailed description of the package in 
Section 4, and conclude with two examples of applications, in Section 5,
to rooted trees weighted by a leaf counter and to connected graphs,
all of whose blocks are in a given family $\cal{B}$ of species of cyclo-set type.

% Section 1 Some examples
%
\section{Some examples of molecular expansions}

The \emph{Devmol} package is well adapted to compute the molecular expansion of
tree-like species. Two examples are given in this section: rooted trees and Husimi
graphs. 

\subsection{Rooted trees}

%\the\textwidth
%
First, consider the well-known species $A$ of rooted trees,
defined by the functional equation
%
\begin{equation}
A=XE(A), \label{eq:arbo}
\end{equation}
%
where $E$ denotes the species of ``sets" ($E$ for French ``ensembles"). Its
molecular expansion can be seen as an explicit description of the species. 
Up to degree (size) 6, we have 
%%
\begin{equation}
\begin{array}{c}
A  =  X + X^{2} + X{E_{2}}(X) + X^{3} + X{E_{3}}(X) + 2X^{4}  + X^{2}{E_{2}}(X) \\ 
   + X{E_{4}}(X) + 3X^{3}{E_{2}}(X) + X{E_{2}}(X^{2}) + 3X^{5} + X^{2}{E_{3}}(X) \\
   + X^{2}{E_{4}}(X) + 6X^{4}{E_{2}}(X) + 2X^{2}{E_{2}}(X^{2}) + 3X^{3}{E_{3}}(X) \\
   + X^{2}{E_{2}}(X)^{2} + X{E_{5}}(X) + 6X^{6} + \cdots. \label{eq:expandrootedtrees}
\end{array} \end{equation}
%
The homogeneous component of degree 5 of this \molexp\ is
%
$$
X{E_{4}}(X) + 3X^{3}{E_{2}}(X) + X{E_{2}}(X^{2}) + 3X^{5} + X^{2}{E_{3}}(X)
$$
%
These terms are illustrated in Figure \ref{fig:arbo5}.
%
\begin{figure}[h]
\centerline{\input{fig-arbo5.pstex_t}}
  \caption{Rooted trees of size $5$}
  \label{fig:arbo5}
\end{figure}
%
\subsection{Weighted Husimi graphs}
%Weigthed : weighted Husimi graphs
%
We illustrate now the more general context, in which 
weighted species occur. The weight of a structure is assumed to be a unitary monomial
(a commutative word) in some given indeterminates, called \emph{weight variables}.
For example, let the weight variables be $y_2,y_3,\ldots$. Define a 
\emph{Husimi graph} as a connected graph all of whose blocks 
(2-connected components) are complete graphs (see \cite{Le03}). 
The weight $w(g)$ of a Husimi graph $g$ is defined by $w(g) = y_2^{n_2} y_3^{n_3} \cdots$, 
where $n_i$ is the number of blocks of $g$ of size $i$ for $i = 2,3,\ldots$. 
An example is given in Figure \ref{fig:Husimi}.
%
\begin{figure}
\begin{center}
\includegraphics[width=0.9\textwidth]{fig-husimi.eps}
\end{center}
\caption{A Husimi graph of weight $y_2^4 y_3 y_4^2 y_5$}
\label{fig:Husimi}
\end{figure}
%
The weighted species of Husimi graphs is denoted by $\Hu_w$. Its \molexp\ up to degree 6 is
computed by \emph{Devmol} as: 
%

\vspace{.5\baselineskip}
\noindent
Degree $1$:
\[X\]
%
Degree $2$:
\[{y_{2}}\,{E_{2}}(X)\]
%
Degree $3$:
\[
{y_{2}}^{2}\,X\,{E_{2}}(X) + {y_{3}}\,{E_{3}}(X)
\]
%
Degree $4$:
%
\[
{y_{2}}\,{y_{3}}\,X^{2}\,{E_{2}}(X) + {y_{2}}^{3}\,X\,{E_{3}}(X)
 + {y_{2}}^{3}\,{E_{2}}(X^{2}) + {y_{4}}\,{E_{4}}(X)
\]
%
Degree $5$:
%
$$
\begin{array}{c}
 ({y_{3}}\,{y_{2}}^{2} + {y_{2}}^{4})\,X^{3}\,{E_{2}}(X) 
 + {y_{2}}^{2}\,{y_{3}}\,X\,{E_{2}}(X)^{2} + ({y_{3}}\,{y_{2}}^{2} 
 + {y_{2}}^{4})\,X\,{E_{2}}(X^{2}) \\
            + {y_{2}}^{4}\,X\,{E_{4}}(X) %\mbox{} 
 + {y_{3}}^{2}\,X\,{E_{2}}({E_{2}}(X)) + {y_{5}}\,{E_{5}}(X) + {y_{2}}\,{y_{4}}\,X^{2}\,{E_{3}}(X)
\end{array} $$
%
Degree $6$:
$$
\begin{array}{c}
  {y_{2}}^{5}\,X^{2}\,{E_{2}}(X^{2}) + ({y_{2}}^{2}\,{y_{4}} 
           + {y_{3}}\,{y_{4}} + {y_{3}}\,{y_{2}}^{3})\,X\,{E_{2}}(X)\,{E_{3}}(X)
                + {y_{2}}^{2}\,{y_{4}}\,{E_{2}}(X)\,{E_{2}}(X^{2}) \\
  \mbox{} + ({y_{3}}^{2}\,{y_{2}} + {y_{2}}^{5} + 3\,{y_{3}}\,{y_{2
}}^{3})\,X^{4}\,{E_{2}}(X) + {y_{2}}^{5}\,{E_{2}}(X^{3}) + ({y_{3}}^{2}\,{y_{2}} + {y_{2}}^{5})\,{E_{2}}(X\,{E_{2}}(X)) \\
  \mbox{} + {y_{2}}\,{y_{3}}^{2}\,X^{2}\,{E_{2}}({E_{2}}(X)) 
     + {y_{3}}\,{y_{2}}^{3}\,{E_{3}}(X^{2}) + {y_{2}}\,{y_{5}}\,X^{2}\,{E_{4}}(X) 
     + {y_{6}}\,{E_{6}}(X)  \\
  \mbox{} + {y_{3}}\,{y_{2}}^{3}\,X^{2}\,{E_{2}}(X)^{2} + {y_{3}}\,{y_{2}}^{3}\,X^{6} + ({y_{2}}^{5} + {y_{2}}^{2}\,{y_{4}})\,X^{3}\,{E_{3}}(X)  + {y_{2}}^{5}\,X\,{E_{5}}(X).
\end{array} $$


As an illustration, the nine terms of size $5$ are shown in Figure \ref{fig:husimi5}.
Note that in terms of simple graphs, the species $E_n$ can be interpreted both as
that of discrete graphs or of complete graphs, on $n$ vertices.

\begin{figure}[th]
\centerline{\input{fig-husimi5.pstex_t}}
  \caption{Husimi graphs of size $5$}
  \label{fig:husimi5}
\end{figure}


% Section 2 \input{sect2}  Addition formulas 

\section{Addition formulas}

The main feature of \emph{Devmol} is its capacity to implement 
the addition formulas relative to the species
of sets and of cycles.  Molecular expansions are then computed by applying
recursively these formulas. 
In what follows, the subscript $n$ in $E_n$
and $C_n$ denotes the restriction to degree (cardinality) $n$.
Observe that Maple already knows the addition formulas for the species
$L_n=X^n$, using the ``expand" function: for a given $n\geq0$,
we have, for example,
%
\begin{equation}
(X+Y)^n = \sum_{i=0}^n {n \choose i}X^iY^{n-i}. \label{eq:binome}
\end{equation}

  Note that for any molecular species $M$ of degree $n$, we have $M(1)=1$ and,
more generally, for any scalar $k$,
%
\begin{equation}
M(k)=Z_M(k,k,\ldots). \label{eq:mk}
\end{equation}
Formula (\ref{eq:mk}) holds for any non-negative integer $k$ in virtue of P\'olya
theory and the extension to a general scalar is valid by polynomiality.
Also, for any weight variable $t$, we have
%
\begin{equation}
M(tX)=t^nM(X). \label{eq:mtx}
\end{equation}
This applies, in particular, to the molecular species $M=L_n, E_n$ and $C_n$.

The additions formulas given in the following subsections are taken from \cite{AuLaLe02}.
They are implemented in Devmol.

%\subsection{Addition formulas related to the species of sets}
\subsection{Addition formulas related to the species of sets}

Recall that $E_0(X)=1$, the ``empty set" species, and that $E_1(X)=X$.
For $n,\ k\geq0$, we have 
\begin{equation}
E_n(X_1+\cdots+X_k) = \sum\limits_{n_1+\cdots+n_k=n \atop n_i \ge 0} E_{n_1}(X_1)
                      \cdots E_{n_k}(X_k). \label{eq:enx1plus}
\end{equation}     

It follows that 
%
\begin{equation}         
 E_n(kX)  =  \sum_{i = 1}^{n} {k \choose i} \sum_{\lambda \vdash_i n} 
{n \choose \lambda_1, \ldots, \lambda_i} \, E_{\lambda_1}(X) \cdots E_{\lambda_i}(X),
\label{eq:enkx}
\end{equation}
the expression $\lambda \vdash_i n$ meaning that the summation index $\lambda$
is a partition of $n$ into $i$ parts, and that
%
\begin{equation}
E_n(k + X) = {k^{\langle n \rangle} \over n!} + {k^{\langle n - 1 \rangle} \over (n - 1)!} X +
\ldots + E_n(X),
\label{eq:enkplusx}
\end{equation}
where $k^{\langle n \rangle} = k (k + 1) \cdots (k + n - 1)$.

%\subsection{Addition formulas related to the species of cycles}
\subsection{Addition formulas related to the species of cycles}

For the species $C$ of oriented cycles, we have
%\begin{theorem}
\begin{equation} 
\label{eq:cnx1plus} 
C_n(X_1+\cdots+X_k)=\sum\limits_{d \mid n}\sum\limits_{\psi_1+\cdots+\psi_k=d \atop \psi_i \ge 0} \lambda_\psi C_{n/d}\left({X_1^{\psi_1}\cdots 
X_k^{\psi_k}}\right),
\end{equation} 
where, for $\psi=(\psi_1,\ldots,\psi_k),\lambda_\psi$ denotes the 
number of Lyndon words on 
${\EUFM X}=\{x_1<\ldots<x_k\}$ having distribution $\psi$,
i.\ e.\ $\psi_\nu$  occurrences of the letter
$x_\nu$, $\nu=1,\ldots,k$. 
%\end{theorem} 
Recall that a {\it Lyndon word} is a 
primitive (not a power of another word) lexicographically minimal word in 
its cyclic conjugacy class. Using M\"obius inversion, it can be 
shown that  
\begin{equation} 
\label{eq:lambdapsi} 
\lambda_\psi=\frac{1}{\psi_1+\cdots+\psi_k} \sum
\limits_{d \mid {\rm gcd}(\psi_1,\cdots,\psi_k)} \mu(d)
\left(\begin{array}{c} \frac{\psi_1+\cdots+\psi_k}{d}\\ 
\frac{\psi_1}{d},\cdots,\frac{\psi_k}{d} 
\end{array} \right).
\end{equation} 

Moreover, one has
\begin{equation}
C_n(kX) = \sum_{d \mid n} \lambda_d(k) C_{n/d}(X^d), \label{eq:cnkx}
\end{equation}
where $\lambda_d(k)= {1\over d} \sum_{\delta \mid d} \mu(\delta) k^{d/\delta}$ 
is the number of Lyndon words of length $d$ in a $k$-element alphabet, and
%
\begin{equation} 
C_n(k + X) = \frac{1}{n} \sum_{d \mid n}\phi(d)k^{n/d} + 
\sum_{d \mid n} \sum_{{i + j = d}\atop{i>0}} \lambda_{i,j}(k) \, C_{n/d}(X^i),
\label{eq:cnkplusx}
\end{equation}
the coefficients $\lambda_{i,j}(k)$ being given by the formula
\begin{equation}
\lambda_{i,j}(k) = {1 \over i + j} \sum_{\delta \mid (i,j)} 
\mu(\delta) {(i + j) / \delta \choose i/\delta} k^{j/\delta}.  \label{eq:lambdaij}
\end{equation}
%
Note that by polynomiality, equations (\ref{eq:enkx}), (\ref{eq:enkplusx}), 
  (\ref{eq:cnkx}) and (\ref{eq:cnkplusx}) are also valid for any scalar $k=\xi\in\C$.
%

% Section 3 \input{sect3} Species implicitly defined by functional equations
%
\section{Species implicitly defined by functional\break equations}

%\subsection{$R$-enriched rooted trees}
\subsection{$R$-enriched rooted trees}
Let $R$ be a species such that $R(0) \ne 0$. The species $A_R$ of 
\emph{$R$-enriched rooted trees} is the unique species satisfying the combinatorial 
equation 
\begin{equation}
A_R = X \, R(A_R).\label{eq:arborenrich}
\end{equation}
% 
\begin{figure}[th]
\begin{center}
\includegraphics[scale=.4]{fig312.eps} %width=0.9\textwidth]
\caption{Typical $R$-enriched rooted tree}
\label{fig:arborenrich}
\end{center}
\end{figure}
%

Figure \ref{fig:arborenrich} shows a typical $R$-enriched rooted tree on the set 
$U=\{a,b,\ldots,k\}$, where all edges have been oriented towards the root, the vertex $e$.
Hence, an $A_R$-structure is a rooted tree where the \emph{fiber} of each vertex
(that is the set of immediate predecessors) is endowed with an $R$-structure.
Familiar examples include 
\begin{enumerate}
\item
Ordered (or plane) rooted trees, where $R=L$,
\item
Ordinary rooted trees, where $R=E$,
\item
Mobiles, where $R=1+C$.
\end{enumerate}

Let us illustrate the iterative method for computing the 
\molexp\ truncated to degree $n$, first in the case
of the species $A$ of $E$-enriched (i.e. ordinary) rooted trees. 
For any species $F$, we write 
%
\begin{equation}
F_{\leq n}=F\bigr|_{\le n}=F_0+F_1+\ldots+F_n \label{eq:fleqn}
\end{equation}
%
to denote the restriction of $F$ to sets of size at most $n$.

We start with
$$
A_{\le 0} = 0,
$$
since there is no rooted tree on the empty set. Next, we have
$$
A_{\le 1} = \left(X \cdot E_0(A) \right)|_{\le 1} = X.
$$

The general iteration formula is given by
\begin{eqnarray}
A_{\le n} & = & \left( X \cdot E_{\le n-1} (A_{\le n-1})  \right)|_{\le n} \nonumber\\
          & = & X \cdot E_{\le n-1} (A_{\le n-1})|_{\le n-1}. \label{eq:iteran}
\end{eqnarray}

Hence, one has successively
\begin{eqnarray*}
A_{\le 2} & = &  \bigl. X \cdot E_{\le 1}(A_1) \bigr|_{\le 1}\phantom{blablablablablabla} \\
& = & \bigl. X \cdot ((1 + X) \rond X) \bigr|_{\le 1} \\
& = & X \cdot (1 + X) \\
& = & X + X^2,
\end{eqnarray*}
\begin{eqnarray*}
\phantom{blablabla} A_{\le 3} & = &  \bigl. X \cdot E_{\le 2}(A_{\le 2}) \bigr|_{\le 2} \\
& = & \bigl. X \cdot ((1 + X + E_2(X)) \rond (X + X^2)) \bigr|_{\le 2} \\
& = & \bigl. X \cdot (1 + X + X^2 + E_2(X + X^2)) \bigr|_{\le 2} \\
& = & \bigl. X \cdot (1 + X + X^2 + E_2(X) + X^3 + E_2(X^2)) \bigr|_{\le 2} \\
& = & X + X^2 + X^3 + X E_2(X),
\end{eqnarray*}
and so on.

Consider now the general case of the species $A = A_R$ of $R$-enriched rooted trees, 
solution of the combinatorial equation $A = X R(A)$. 
We start with $A_0=0$ or $A_1 = X R_0$. 
Furthermore, the general recurrence relation can be written as
%
\begin{equation}
\label{eq:iterarn}
A_{\le n} = \bigl. X \cdot R_{\le n-1}(A_{\le n-1}) \bigr|_{\le n-1}.
\end{equation}
% 

The \molexp\ of $A$ can then be computed recursively, using (\ref{eq:iterarn}). Hence, the Maple package \emph{Devmol} can compute the \molexp\ of the species $A_R$ for any $R$ of cyclo-set type. 
For example, the \molexp\ of the species $A_{1 + C}$ of ``mobiles" is, up to degree 6,
\begin{eqnarray}
A_{1 + C}\bigr|_{\le6} & = & X + X^{2} + X E_{2}(X) + X^{3} + 
                               X C_{3}(X) + 2X^{4} + X^{2}E_{2}(X) \nonumber \\
     &  & + X C_{4}(X) + 4 X^{5} + XE_{2}(X^{2}) + 2X^{3}E_{2}(X) + X^{2}C_{3}(X) \nonumber \\
     &  & + XC_{5}(X) + 5 X^{4}E_{2}(X) + 2X^{3}C_{3}(X) + X^{2}C_{4}(X) \\
     &  &  + X^{2}E_{2}(X^{2}) + 10X^{6}. \nonumber \label{eq:mobiles6}
\end{eqnarray}  
%

%Arbres R-enrichis
\subsection{$R$-enriched trees.}
$R$-enriched trees are defined as (unrooted) trees where the set of neighbors of any vertex
is endowed with an $R$-structure. See Figure \ref{fig:arbrerenrich} for an illustration.
For example, plane trees can be seen as $1+C$-enriched trees.

The species of $R$-enriched trees is denoted by $\arbres_R$. It can be expressed in terms
of the species $A_{R^\prime}$ of $R^\prime$-enriched rooted trees, where $R^\prime$
denotes the derivative of the species $R$, using the Dissymmetry Theorem for $R$-enriched
trees (see \cite{BLL98}, Theorem 4.1.2). Indeed, we have
%
\begin{equation}
\label{eq:ar}
\arbres_R = X R(A_{R'}) + E_2(A_{R'}) - A_{R'}^2.
\end{equation}
% 
\begin{figure}[th]
\begin{center}
\includegraphics[scale=.4]{fig3113.eps} %width=0.9\textwidth]
\caption{Typical $R$-enriched tree}
\label{fig:arbrerenrich}
\end{center}
\end{figure}
%

%sous-section arborescences G-additives
\subsection{$G$-additive rooted trees.}
Another important family of species defined by functional equations is that of
\emph{$G$-additive rooted trees}, where $G$ is a given species such that ${\cal O}(G)\geq 2$,
that is $G(0)=G'(0)=0$.
It is defined as the species $B=B(X)$ which satisfies the additive functional equation
%
\begin{equation}
\label{eq:ga}
B =  X + G(B). 
\end{equation}
% 
\begin{figure}[t]
\begin{center}
\includegraphics[scale=.4]{fig327.eps} %width=0.9\textwidth]
\caption{Typical $G$-additive rooted tree}
\label{fig:ga}
\end{center}
\end{figure}
%
This species is often denoted by $B= {}_GA$. See Figure \ref{fig:ga} for an illustration 
of a typical ${}_GA$-structure.  

An example is also given by the species
$P=P(X)$ of parenthesizations, which can be defined by the functional equation
\begin{equation}
\label{eq:parenth}
P =  X + P^2. 
\end{equation}

It is clear that the \molexp\ of the species ${}_GA$ of $G$-additive rooted trees can also
be computed recursively, whenever effective addition formulas are known for $G$.
%

% Section 4 \input{sect4} \section{Presentation of the Maple package \emph{Devmol}}
%
\section{Presentation of the Maple package \emph{Devmol}}
%

%\subsection{Basic purpose}
\subsection{Basic purpose}

The basic purpose of the Maple package \emph{Devmol} is to compute %(fig.\ \ref{purpose})
the \molexp\ of any given recognized species expression,
extending the expansion of classical algebraic expressions. For instance, the molecular
expansion of the expression $(X + Y)^2$ is simply $X^2 + 2 X Y + Y^2$. 

Let ${\cal A}$ denote the alphabet of sort variables  
and ${\cal V}$ the alphabet of weight variables. 
The language
${\cal L}_{\cal A}$ of recognized expressions is then defined by the following grammar :
%\setcounter{feve}{-1}
\begin{enumerate}
\item $1 \in {\cal L}_{\cal A}$,
\item $X \in \cal A$\hspace{1em}$\Rightarrow$\hspace{1em}$X \in {\cal L}_{\cal A}$,
\item $p \in \C[\cal V]$, $\Phit \in {\cal L}_{\cal A}$\hspace{1em}
       $\Rightarrow$\hspace{1em}$p \, * \, \Phit \in {\cal L}_{\cal A}$,
\item $\Phit, \Psit \in {\cal L}_{\cal A}$\hspace{1em}$\Rightarrow$\hspace{1em}$\Phit + \Psit 
      \in {\cal L}_{\cal A}\ \mbox{and}\ \Phit \, * \,\Psit \in {\cal L}_{\cal A}$,
\item $n \in \N$, $\Phit \in {\cal L}_{\cal A}$\hspace{1em}$\Rightarrow$\hspace{1em}
       $E_n(\Phit) \in {\cal L}_{\cal A}\ \mbox{and}\ C_n(\Phit) \in {\cal L}_{\cal A}$.
\end{enumerate}

The package Devmol, or , more precisely, its main procedure \texttt{dev}, can then be seen as 
an operator of the form
$$
%\mbox{Devmol} : 
{\cal L}_{\cal A} \longrightarrow \C[\cal V][\rr[{\cal M}_{\cal A}]\rr]
$$
which computes the \molexp\ of a recognized expression. The result is a formal power
series with coefficients in the ring $\C[\cal V]$ %and with indeterminates in 
over the set ${\cal M}_{\cal A}$, of (unweighted) 
molecular species of cyclo-set type in the sorts $\cal A$.
This set is defined recursively as follows:
%
\begin{enumerate}
\item $1 \in {\cal M}_{\cal A}$
\item $X \in \cal A$ $\Rightarrow$  $X \in {\cal M}_{\cal A}$,
\item $M, N \in {\cal M}_{\cal A}$ %\setminus \{1\} 
\ $\Rightarrow$ $M \cdot N \in {\cal M}_{\cal A}$,
\item $n \in \N$, $n \ge 2$, $M \in {\cal M}_{\cal A}$%\setminus \{1\}
\ $\Rightarrow$ $E_n(M) \in {\cal M}_{\cal A}$,
\item $n \in \N$, $n \ge 3$, $M \in {\cal M}_{\cal A}$%\setminus \{1\}
\ $\Rightarrow$ $C_n(M) \in {\cal M}_{\cal A}$.
\end{enumerate}

%Note that the product of species is commutative: $M \cdot N = N \cdot M$.

The Maple package \emph{Devmol} comprises basically two main (internal) procedures,
\texttt{expand}/$\mathrm{E}_{\_}$ and \texttt{expand}/$\mathrm{C}_{\_}$
which extend the Maple procedure \texttt{expand}.
When the \texttt{expand} procedure is applied to a recognized expression, it recursively calls
the relevant procedure each time a sub-expression of the form $E_n(\cdot)$ or $C_n(\cdot)$ is met.
Each of these procedures ``executes'' the corresponding addition formula.

As mentioned in the introduction, the default set of sort variables is ${\cal A} = \{X, Y, Z\}$.
To include new sort variables, one uses the procedure \texttt{ajoutvs}, which is short for 
French ``ajouter variables de sortes" (English alias: \texttt{addsv}). 
More precisely, the command 
% 
%
\begin{maplelike}
\mwsin{ajoutvs(YY);}
\end{maplelike}%
%
\noindent
adds the name $YY$ to the set $\cal A$ of sort variables. 
Maple also answers by printing the current set of sort variables.
Note that the sort variables are global.
In the same manner, one uses the procedure \texttt{ajoutvv} (English alias: \texttt{addwv}) 
to add new elements to the set $\cal V$ of weight variables. 
Once added to this set, a weight variable becomes global too. 
The initial set of weight variables is ${\cal V} = \{t\}$.

\subsection{The procedure \texttt{dev}}
The most fundamental procedure of \emph{Devmol} is \texttt{dev}. 
The purpose of\break \texttt{dev(Phi,d)} is to compute the \molexp\ of the recognized
expression \texttt{Phi}, up to the given truncation degree $d$.

\vspace{2mm}
\noindent {\bf Examples.}
%\vspace{.5\baselineskip}
\begin{maplelike}
\mwsin{ajoutvv(u);}
\mwsout{% 
\[
%\begin{array}{c}
\{t,u\}
%\end{array} 
\]
}
%
\mwsin{Phi := E[5](E[2](X) + u*X);}
\mwsout{%
\[
%\begin{array}{c}
\Phi  := {E_{5}}({E_{2}}(X) + u\,X)
%\end{array} 
\]
}
%
\mwsin{dev(Phi,10);}
\mwsout{%
$$\begin{array}{c}
u^{5}\,{E_{5}}(X) + {E_{5}}({E_{2}}(X)) + u^{4}\,{E_{4}}(X)\,{E_{2}}(X) + u\,X\,{E_{4}}({E_{2}}(X)) \\
\mbox{} + u^{3}\,{E_{3}}(X)\,{E_{2}}({E_{2}}(X)) + u^{2}\,{E_{2}}(X)\,{E_{3}}(E_{2}(X))
\end{array} $$
}
%
\mwsin{dev((X\^{}2 + t*E[3](Y))\^{}5, infinity);}
\mwsout{%
$$\begin{array}{c}
X^{10} + 5\,t\,{E_{3}}(Y)\,X^{8} + 10\,t^{2}\,{E_{3}}(Y)^{2}\,X^{
6} + 10\,t^{3}\,{E_{3}}(Y)^{3}\,X^{4} \\
\mbox{} + 5\,t^{4}\,{E_{3}}(Y)^{4}\,X^{2} + t^{5}\,{E_{3}}(Y)^{5}
\end{array} $$
 }
%
%}
%
\mwsin{dev((1 - Z - Z\^{}2)\^{}(-1), 10);}
\mwsout{%
$$\begin{array}{c}
1 + Z + 2\,Z^{2} + 3\,Z^{3} + 5\,Z^{4} + 8\,Z^{5} + 13\,Z^{6} + 
21\,Z^{7} + 34\,Z^{8} + 55\,Z^{9} \\
\mbox{} + 89\,Z^{10} 
\end{array} $$
}
%
\mwsin{dev(E[5](1 + t * X), 5);}
\mwsout{%
$$\begin{array}{c}
1 + t\,X + t^{2}\,{E_{2}}(X) + t^{3}\,{E_{3}}(X) + t^{4}\,{E_{4}}
(X) + t^{5}\,{E_{5}}(X)
\end{array} $$
}
%
\mwsin{dev(E[5](3 + t*X), 5);}
\mwsout{%
$$\begin{array}{c}
21 + 15\,t\,X + 10\,t^{2}\,{E_{2}}(X) + 6\,t^{3}\,{E_{3}}(X) + 3
\,t^{4}\,{E_{4}}(X) + t^{5}\,{E_{5}}(X)
\end{array} $$
}
\mwsin{dev(E[5](a + t*X), 5);}
\mwsout{%
$$\begin{array}{c}
{\displaystyle \frac {a\,(a + 1)\,(a + 2)\,(a + 3)\,(a + 4)}{120}
}  + {\displaystyle \frac {a\,(a + 1)\,(a + 2)\,(a + 3)\,t\,X}{24
}}  \\
\mbox{} + {\displaystyle \frac {1}{6}} \,a\,(a + 1)\,(a + 2)\,t^{
2}\,{E_{2}}(X) + {\displaystyle \frac {1}{2}} \,a\,(a + 1)\,t^{3}
\,{E_{3}}(X) \\
\mbox{} + a\,t^{4}\,{E_{4}}(X) + t^{5}\,{E_{5}}(X) 
\end{array} $$
}
%
\mwsin{dev(E[5](u + t*X), 5);}
\mwsout{%
$$\begin{array}{c}
u^{5} + u^{4}\,t\,X + u^{3}\,t^{2}\,{E_{2}}(X) + u^{2}\,t^{3}\,{E
_{3}}(X) + u\,t^{4}\,{E_{4}}(X) + t^{5}\,{E_{5}}(X)
\end{array} $$
}
%
\end{maplelike}


%\subsection{Procedures for computing generating series}
\subsection{Procedures for computing generating series}

The next family of procedures is used for computing various generating series. 
There are three such procedures, namely \texttt{sge(F,d)} (English alias: \texttt{egs}),
which computes the exponential generating series of the species $F$, truncated at degree $d$,
\texttt{sgef} (English: \texttt{fegs}), where the counting coefficients can be directly
read off,
and \texttt{sgt} (English: \texttt{tgs}), which computes the (isomorphism) type generating series,
i.e. the tilde generating series, for unlabelled enumeration.

\vspace{.5\baselineskip}
\noindent 
{\bf Examples 1.} We compute these series up to degree 10 for the species of oriented cycles. 
%
\begin{maplelike}
\mwsin{FF := sum(C[k](X), k = 1..10);}
\mwsout{%
$$\begin{array}{c}
\mathit{FF} := {C_{1}}(X) + {C_{2}}(X) + {C_{3}}(X) + {C_{4}}(X)
 + {C_{5}}(X) + {C_{6}}(X) + {C_{7}}(X) \\
\mbox{} + {C_{8}}(X) + {C_{9}}(X) + {C_{10}}(X) 
\end{array} $$
}
%
\mwsin{GG := dev(FF,10);}
\mwsout{%
$$\begin{array}{c}
\mathit{GG} := X + {E_{2}}(X) + {C_{3}}(X) + {C_{4}}(X) + {C_{5}}
(X) + {C_{6}}(X) + {C_{7}}(X) + {C_{8}}(X) \\
\mbox{} + {C_{9}}(X) + {C_{10}}(X) 
\end{array} $$
}
%
\mwsin{sge(GG,10);}
\mwsout{%
$$\begin{array}{c}
x + {\displaystyle \frac {1}{2}} \,x^{2} + {\displaystyle \frac {1}{3}} \,x^{3} 
+ {\displaystyle \frac {1}{4}} \,x^{4} + 
{\displaystyle \frac {1}{5}} \,x^{5} + {\displaystyle \frac {1}{6}} \,x^{6} 
+ {\displaystyle \frac {1}{7}} \,x^{7} + 
{\displaystyle \frac {1}{8}} \,x^{8} + {\displaystyle \frac {1}{9}} \,x^{9} 
+ {\displaystyle \frac {1}{10}} \,x^{10}
\end{array} $$
}
%
\mwsin{sgef(GG,10);}
\mwsout{%
$$\begin{array}{c}
{\displaystyle \frac {x}{1\mathrm{!}}}  + {\displaystyle \frac {x
^{2}}{2\mathrm{!}}}  + {\displaystyle \frac {2\,x^{3}}{3\mathrm{!
}}}  + {\displaystyle \frac {6\,x^{4}}{4\mathrm{!}}}  + 
{\displaystyle \frac {24\,x^{5}}{5\mathrm{!}}}  + {\displaystyle 
\frac {120\,x^{6}}{6\mathrm{!}}}  + {\displaystyle \frac {720\,x
^{7}}{7\mathrm{!}}}  + {\displaystyle \frac {5040\,x^{8}}{8
\mathrm{!}}}  \\
\mbox{} + {\displaystyle \frac {40320\,x^{9}}{9\mathrm{!}}}  + 
{\displaystyle \frac {362880\,x^{10}}{10\mathrm{!}}} 
\end{array} $$
}

%
\mwsin{sgt(GG,10);}
\mwsout{%
\[
x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6} + x^{7} + x^{8} + x^{9}
 + x^{10}
\]
}
\end{maplelike}
%

{\bf 2.} Here is an example involving a two-sort species:
%
\begin{maplelike}
%
\mwsin{Phi := (1 + X + E[2](X) + E[3](X)) * (1 + C[3](Y));}
\mwsout{%
$$\begin{array}{c}
\Phi  := (1 + X + {E_{2}}(X) + {E_{3}}(X))\,(1 + {C_{3}}(Y))
\end{array} $$
}
%
\mwsin{dev(Phi,9);}
\mwsout{%
$$\begin{array}{c}
1 + {C_{3}}(Y) + X + X\,{C_{3}}(Y) + {E_{2}}(X) + {E_{2}}(X)\,{C
_{3}}(Y) + {E_{3}}(X) \\
\mbox{} + {E_{3}}(X)\,{C_{3}}(Y) 
\end{array} $$
}
%
\mwsin{sge(Phi,9);}
\mwsout{%
$$\begin{array}{c}1
 + {\displaystyle \frac {1}{3}} \,y^{3} + x + {\displaystyle 
\frac {1}{3}} \,x\,y^{3} + {\displaystyle \frac {1}{2}} \,x^{2}
 + {\displaystyle \frac {1}{6}} \,x^{2}\,y^{3} + {\displaystyle 
\frac {1}{6}} \,x^{3} + {\displaystyle \frac {1}{18}} \,x^{3}\,y
^{3}
\end{array} $$
}
%
\mwsin{sgef(Phi,9);}
\mwsout{%
$$\begin{array}{c}
{\displaystyle \frac {1}{1\mathrm{!}}}  + {\displaystyle \frac {2
\,y^{3}}{3\mathrm{!}}}  + {\displaystyle \frac {x}{1\mathrm{!}}} 
 + {\displaystyle \frac {2\,x\,y^{3}}{1\mathrm{!}\,3\mathrm{!}}} 
 + {\displaystyle \frac {x^{2}}{2\mathrm{!}}}  + {\displaystyle 
\frac {2\,x^{2}\,y^{3}}{2\mathrm{!}\,3\mathrm{!}}}  + 
{\displaystyle \frac {x^{3}}{3\mathrm{!}}}  + {\displaystyle 
\frac {2\,x^{3}\,y^{3}}{(3\mathrm{!})^{2}}} 
\end{array} $$
}
%
\mwsin{sgt(Phi,9);}
\mwsout{%
\[
1 + y^{3} + x + x\,y^{3} + x^{2} + x^{2}\,y^{3} + x^{3} + x^{3}\,
y^{3}
\]
%
}
\end{maplelike}
%%
%Procedures for computing the \molexp\ of tree-like species
%
\subsection{Procedures for computing the \molexp\ of tree-like species}
There are procedures in \emph{Devmol} for computing the \molexp\ of the classes of 
tree-like species described in Section 3. These are \texttt{arborr} (English: \texttt{rrtrees}),
for the species of $R$-enriched rooted trees,
\texttt{arbrer} (\texttt{rtrees}), for $R$-enriched trees,
and \texttt{arborgadd} (\texttt{gaddrtrees}), for $G$-additive rooted trees.

 In each case, the parameters $R$ and $G$ are one-sort species of cyclo-set type.

%\subsubsection{$R$-enriched rooted trees}
\subsubsection{$R$-enriched rooted trees}

The command \texttt{arborr(R,d)} returns the \molexp\ up to degree $d$ of
the species $A_R$ of $R$-enriched rooted trees.

\vspace{.5\baselineskip}
\noindent 
\textbf{Example.} Ordinary rooted trees. %(autre ?)
%
\begin{maplelike}
%
\mwsin{R := 1 + sum(E[k](X), k = 1..5);}
\mwsout{%
$$\begin{array}{c}
R := 1 + {E_{1}}(X) + {E_{2}}(X) + {E_{3}}(X) + {E_{4}}(X) + {E_{5}}(X)
\end{array} $$
}
%
\mwsin{A := arborr(R,6);}
\mwsout{%
$$\begin{array}{c}
A:= X + X^{2} + X\,{E_{2}}(X) + X^{3} + X\,{E_{3}}(X) + 2\,X^{4} + X
^{2}\,{E_{2}}(X) \\
\mbox{} + X\,{E_{4}}(X) + 3\,X^{3}\,{E_{2}}(X) + X\,{E_{2}}(X^{2}) + 3\,X^{5} + X
^{2}\,{E_{3}}(X) + 6\,X^{6} \\
\mbox{} + X^{2}\,{E_{2}}(X)^{2} + X^{2}\,{E_{4}}(X) + 6\,X^{4}\,{
E_{2}}(X) + 3\,X^{3}\,{E_{3}}(X) \\
\mbox{} + 2\,X^{2}\,{E_{2}}(X^{2}) + X\,{E_{5}}(X) 
\end{array}$$
}
%
\mwsin{sge(A,6);}
\mwsout{%
$$\begin{array}{c}
x + {\displaystyle \frac {125}{24}} \,x^{5} + {\displaystyle 
\frac {3}{2}} \,x^{3} + {\displaystyle \frac {54}{5}} \,x^{6} + 
{\displaystyle \frac {8}{3}} \,x^{4} + x^{2}
\end{array} $$
}
%
\mwsin{sgef(A,6);}
\mwsout{%
$$\begin{array}{c}
{\displaystyle \frac {x}{1\mathrm{!}}}  
 + {\displaystyle \frac {2\,x^{2}}{2\mathrm{!}}} 
+ {\displaystyle \frac {9\,x^{3}}{3\mathrm{!}}}  
 + {\displaystyle \frac {64\,x^{4}}{4\mathrm{!}}}  
+ {\displaystyle \frac {625\,x^{5}}{5\mathrm{!}}}  
+ {\displaystyle \frac {7776\,x^{6}}{6\mathrm{!}}} 
\end{array} $$
}
%
\mwsin{sgt(A,6);}
\mwsout{%
\[
x + x^{2} + 2\,x^{3} + 4\,x^{4} + 9\,x^{5} + 20\,x^{6}
\]
}
\end{maplelike}
%

%\subsubsection{$R$-enriched trees}
\subsubsection{$R$-enriched trees}

The command \texttt{arbrer(R,d)} returns the \molexp\ up to degree $d$ of the species
$\arbres_R$ of $R$-enriched trees. 

\vspace{.5\baselineskip}
\noindent \textbf{Example.} The following example gives the \molexp\ (up to degree 8) 
of the species $\arbres_R$, where $R = C$. This is the species of \emph{plane trees}.
%
\begin{maplelike}
%
\mwsin{R := 1 + X + sum(C[k](X), k = 2..7);}
\mwsout{%
$$\begin{array}{c}
R := 1 + X + {C_{2}}(X) + {C_{3}}(X) + {C_{4}}(X) + {C_{5}}(X) + 
{C_{6}}(X) + {C_{7}}(X)
\end{array} $$
}
%
\mwsin{A := arbrer(R, 8);}
\mwsout{%
$$\begin{array}{c}
A:= \,X^{7} + 2\,{E_{2}}(X^{3}) + {E_{2}}(X^{2}) + X\,{C_{3}}(X^{2})
 + X\,{C_{7}}(X) + X\,{C_{6}}(X) + X\,{E_{2}}(X) \\
\mbox{} + X\,{C_{4}}(X) + X\,{C_{5}}(X) + X + 3\,X\,{E_{2}}(X^{3}
) + X\,{E_{2}}(X^{2}) + X\,{C_{3}}(X) \\
\mbox{} + 5\,{E_{2}}(X^{4}) + 3\,X^{6} + {E_{2}}(X) + X^{5} + 28
\,X^{8} 
\end{array}$$
}
%
\mwsin{sge(A,8);}
\mwsout{%
$$\begin{array}{c}
{\displaystyle \frac {7}{4}} \,x^{5} + {\displaystyle \frac {21}{
5}} \,x^{6} + 11\,x^{7} + {\displaystyle \frac {5}{6}} \,x^{4} + 
{\displaystyle \frac {1}{2}} \,x^{2} + {\displaystyle \frac {1}{2
}} \,x^{3} + {\displaystyle \frac {429}{14}} \,x^{8} + x
\end{array} $$
}
%
\mwsin{sgef(A,8);}
\mwsout{%
$$\begin{array}{c}
{\displaystyle \frac {x}{1\mathrm{!}}} 
 + {\displaystyle \frac {x^{2}}{2\mathrm{!}}} 
 + {\displaystyle \frac {3\,x^{3}}{3\mathrm{!}}} 
 + {\displaystyle \frac {20\,x^{4}}{4\mathrm{!}}} 
 + {\displaystyle \frac {210\,x^{5}}{5\mathrm{!}}}  
 + {\displaystyle \frac {3024\,x^{6}}{6\mathrm{!}}}  
 + {\displaystyle \frac {55440\,x^{7}}{7\mathrm{!}}}    
 + {\displaystyle \frac {1235520\,x^{8}}{8\mathrm{!}}} 
\end{array}$$
 }
%
\mwsin{sgt(A,8);}
\mwsout{%
\[
x + x^{2} + x^{3} + 2\,x^{4} + 3\,x^{5} + 6\,x^{6} + 14\,x^{7} + 
34\,x^{8}
\]
}
\end{maplelike}
%

%%
%\subsubsection{$G$-additive rooted trees}
\subsubsection{$G$-additive rooted trees}

The command \texttt{arborgadd(G,d)} returns the \molexp\ up to degree $d$ of the
species $\arbres_G$ of $G$-additive rooted trees.

\vspace{.5\baselineskip}
\noindent {\bf Example.}

\begin{maplelike}
%
\mwsin{G := E[2](X) + E[3](X);}
\mwsout{%
\[
%$$\begin{array}{c}
G := {E_{2}}(X) + {E_{3}}(X)
\]
%\end{array} $$
}
%
\mwsin{A := arborgadd(G,6);}
\mwsout{%
$$\begin{array}{c}
A := X + {E_{2}}(X) + {E_{3}}(X) + {E_{2}}(X)\,X + {E_{2}}(X)^{2}
 + {E_{2}}({E_{2}}(X)) + X\,{E_{3}}(X) \\
\mbox{} + {E_{2}}(X)\,X^{2} + 2\,{E_{2}}(X)\,{E_{3}}(X) + 3\,X\,{
E_{2}}(X)^{2} + 2\,X\,{E_{2}}({E_{2}}(X)) \\
\mbox{} + X^{2}\,{E_{3}}(X) + {E_{2}}(X)\,X^{3} + 6\,{E_{2}}(X)\,
X\,{E_{3}}(X) \\
\mbox{} + 2\,{E_{2}}(X)\,{E_{2}}({E_{2}}(X)) + 6\,{E_{2}}(X)^{2}
\,X^{2} + {E_{3}}({E_{2}}(X)) + 2\,{E_{2}}(X)^{3} \\
\mbox{} + {E_{2}}({E_{3}}(X)) + {E_{2}}({E_{2}}(X)\,X) + 2\,X^{2}
\,{E_{2}}({E_{2}}(X)) + X^{3}\,{E_{3}}(X) \\
\mbox{} + {E_{2}}(X)\,X^{4} 
\end{array}$$
}
%
\mwsin{sgt(A,6);}
\mwsout{%
\[
x + x^{2} + 2\,x^{3} + 4\,x^{4} + 9\,x^{5} + 23\,x^{6}
\]
}
\end{maplelike}

%%
%\subsection{A procedure for computing the roots of a species}
\subsection{A procedure for computing the $n^{th}$ root of a species}

There is a procedure, \texttt{rac} (English: \texttt{nroot}), in \emph{Devmol},
for computing the $n^{th}$ root of a species.
An $n^{th}$ root of a species $F$ is a species $\Phit$ such that $\Phit^n = F$.
As in the case of formal power series, $\Phit$ is uniquely determined once its constant
term $\Phit_0$ has been given, satisfying $\Phit_0^n = F_0$, 
under the condition that $F_0$ is invertible in the ring \C[\cal{V}]; 
and the algorithm for computing $\Phit$ is the same as for formal power series.
It makes use of Newton's binomial theorem. Let $F=F_0+F_+$. Then we have
\begin{eqnarray}
\Phit & = & F^{1/n} \nonumber \\
       & = & F_0^{1/n}\left(1+\frac{F_+}{F_0}\right)^{1/n} \nonumber \\
       & = & \Phit_0 \cdot \sum_{k \ge 0} {1/n \choose k} \left(\frac{F_+}{F_0}\right)^k.
       \label{eq:nrootf}
\end{eqnarray}
The command \texttt{rac(n,F,$\Phi_0$,d)} returns the molecular expansion of (\ref{eq:nrootf})
truncated at degree $d$.
Observe that we could compute in the same manner any rational power $F^\alpha$ of $F$, 
for $\alpha \in \Q$.

\vspace{.5\baselineskip}
\noindent 
\textbf{Examples. 1.}\  %\Examples \noindent 1)\ 
The following command sequence returns the square root of
the species $A(2X)/(2X)$, of constant term $1$, up to degree 6, 
where $A$ denotes the species of rooted trees.
It can be seen that the species $B=\sqrt{A(2X)/(2X)}$ satisfies the equation
\begin{equation}
B = 1 + E(XB^2). \label{eq:b}
\end{equation}
In fact, $B$ is the species of triangle-labelled oriented-edge-rooted 2-trees 
(see \cite{FGLL02}).

\begin{maplelike}
%
\mwsin{R := 1 + sum(E[k](X), k = 1..6);}
\mwsout{%
$$\begin{array}{c}
R := 1 + {E_{1}}(X) + {E_{2}}(X) + {E_{3}}(X) + {E_{4}}(X) + {E_{
}}(X) + {E_{6}}(X)
\end{array} $$
}
%
\mwsin{A := arborr(R,7):}%
\mwsin{A2 := dev(subs(X = 2*X,A)/(2*X),6):}%
\mwsin{rac(2,A2,1,6);}
\mwsout{%
$$\begin{array}{c}
1 + 2\,X\,{E_{2}}(X) + 2\,X\,{E_{3}}(X) + 10\,X^{2}\,{E_{2}}(X)
 + 2\,X\,{E_{4}}(X) + 43\,X^{3}\,{E_{2}}(X) \\
\mbox{} + 6\,X\,{E_{2}}(X^{2}) + 10\,X^{2}\,{E_{3}}(X) + 18\,X^{2}\,{E_{2}}(X)^{2} + 43\,X^{3}\,{E_{3}}(X) \\
\mbox{} + 22\,X^{2}\,{E_{2}}(X^{2}) + 201\,X^{4}\,{E_{2}}(X) + 10\,X^{2}\,{E_{4}}(X) + 
\,X\,{E_{5}}(X) \\
\mbox{} + 2\,{E_{2}}(X^{2}) + 2\,{E_{3}}(X^{2}) + 5\,{E_{2}}(X^{3
}) + 2\,{E_{2}}(X\,{E_{2}}(X)) + X \\
\mbox{} + 6\,{E_{3}}(X)\,X\,{E_{2}}(X) + 2\,{E_{2}}(X)\,{E_{2}}(X
^{2}) + 388\,X^{6} + {E_{4}}(X) \\
\mbox{} + {E_{5}}(X) + {E_{6}}(X) + {E_{2}}(X) + {E_{3}}(X) + 2\,
X^{2} + 7\,X^{3} + 24\,X^{4} \\
\mbox{} + 3\,X\,{E_{2}}(X)^{2} + 95\,X^{5}
\end{array}$$
}
\end{maplelike}
%

\vspace{.5\baselineskip}
\textbf{2.}\ The species $P=P(X)$ of parenthesizations, introduced in Section 3.3, is
defined by the functional equation (\ref{eq:parenth}) or equivalently, by
%
\begin{equation}
P^2 - P + X = 0, \label{eq:catalan}
\end{equation}
%
Solving this quadratic equation yields
%
\begin{equation}
P(X) = \frac{1-\sqrt{1-4X}}{2}. \label{eq:solutioncatalan}
\end{equation}
%
This expression is expanded up to degree $10$ in the following lines. Anyone will recognize
the familiar Catalan numbers.
\begin{maplelike}
%
\mwsin{S := rac(2,1-4*X,1,10);}
\mwsout{%
$$\begin{array}{c}
S:= 1 - 2\,X - 2\,X^{2} - 4\,X^{3} - 10\,X^{4} - 28\,X^{5} - 84
\,X^{6} - 264\,X^{7} \\
\mbox{} - 858\,X^{8} - 2860\,X^{9} - 9724\,X^{10}
\end{array}$$
}
%
\mwsin{P(X) := (1 - S)/2;}
\mwsout{%
$$\begin{array}{c}
P(X) := X + X^{2} + 2\,X^{3} + 5\,X^{4} + 14\,X^{5} + 42
\,X^{6} + 132\,X^{7} + 429\,X^{8} \\
\mbox{} + 1430\,X^{9} + 4862\,X^{10} 
\end{array}$$
}
\end{maplelike}
%

%%
%\subsection{A procedure for computing the inverse under substitution}
\subsection{A procedure for computing the inverse under substitution}

The inverse under substitution of a species $\Phit=\Phit(X)$ is defined 
whenever $\Phit(0) = 0$ and $\Phit'(0) = 1$, i.\ e.\ when $\Phit$ is of the
form $\Phit = X + \Phit_{\ge 2}$. 
%where $\Phit_{\ge 2}$ denotes the sum of the terms of $\Phit$ of degree at least 2. 
The inverse of such a species is then the species $\Psit$ such that
$\Phit \rond \Psit = X$. The procedure \texttt{invsubst} (English: \texttt{invsubs}) 
computes the inverse under substitution of a species, up to the given degree.

\vspace{.5\baselineskip}
\noindent 
\textbf{Examples. 1.}\ We compute the inverse under substitution up to degree 5 of
the species $X+E_{2}(X)+\ldots+E_{5}(X)$. Note that this inverse is equal to the inverse
of $E_+=E-1$ up to the same degree.
%
\begin{maplelike}
\mwsin{Phi := sum(E[k](X), k = 1..5);}
\mwsout{%
$$\begin{array}{c}
\Phi  := {E_{1}}(X) + {E_{2}}(X) + {E_{3}}(X) + {E_{4}}(X) + {E_{5}}(X)
\end{array} $$
}
%
\mwsin{invsubst(Phi, 5);}
\mwsout{%
$$\begin{array}{c}
X - {E_{2}}(X) - {E_{3}}(X) + X\,{E_{2}}(X) - {E_{4}}(X) + {E_{2}
}({E_{2}}(X)) + X\,{E_{3}}(X) \\
\mbox{} - X^{2}\,{E_{2}}(X) - {E_{5}}(X) + X\,{E_{4}}(X) + {E_{2}
}(X)\,{E_{3}}(X) - X^{2}\,{E_{3}}(X) \\
\mbox{} - {E_{2}}(X)^{2}\,X + X^{3}\,{E_{2}}(X) 
\end{array}$$
}
\end{maplelike}
%

%\vspace{.5\baselineskip}
\textbf{2.}\ The equation (\ref{eq:catalan}) shows that the species $P(X)$
is the substitutional inverse of $X-X^2$. This is verified here up to degree $10$.

\begin{maplelike}
%
\mwsin{Phi := X - X\^{}2;}
\mwsout{%
\[
\Phi  := X - X^{2}
\]
%
}
%
\mwsin{invsubst(Phi,10);}
\mwsout{%
$$\begin{array}{c}
X + X^{2} + 2\,X^{3} + 5\,X^{4} + 14\,X^{5} + 42\,X^{6} + 132\,X
^{7} + 429\,X^{8} + 1430\,X^{9} \\
\mbox{} + 4862\,X^{10} 
\end{array}$$
}
\end{maplelike}
%

%\vspace{.5\baselineskip}
\textbf{3.}\ In this example, we verify, up to degree 6, that the species 
$A$ of rooted trees satisfies the combinatorial equation
$A=(X E(-X))^{\langle -1 \rangle}$. 
%
\begin{maplelike}
%
\mwsin{EE := 1 + sum(E[k](X), k = 1..5);}
\mwsout{%
$$\begin{array}{c}
\mathit{EE} := 1 + {E_{1}}(X) + {E_{2}}(X) + {E_{3}}(X) + {E_{4}}
(X) + {E_{5}}(X)
\end{array} $$
}
%
\mwsin{AA := arborr(EE,6);}
\mwsout{%
$$\begin{array}{c}
X + X^{2} + X\,{E_{2}}(X) + X^{3} + X\,{E_{3}}(X) + 2\,X^{4} + X
^{2}\,{E_{2}}(X) + X\,{E_{4}}(X) \\
\mbox{} + 3\,X^{3}\,{E_{2}}(X) + X\,{E_{2}}(X^{2}) + 3\,X^{5} + X
^{2}\,{E_{3}}(X) + 6\,X^{6} + X\,{E_{5}}(X) \\
\mbox{} + 2\,X^{2}\,{E_{2}}(X^{2}) + 3\,X^{3}\,{E_{3}}(X) + X^{2}
\,{E_{4}}(X) + 6\,X^{4}\,{E_{2}}(X) \\
\mbox{} + X^{2}\,{E_{2}}(X)^{2}
\end{array}$$
}
%
\mwsin{FF := dev(X*subs(X=-X,EE), 6);}
\mwsout{%
$$\begin{array}{c}
\mathit{FF} := X - X^{2} - X\,{E_{2}}(X) + X^{3} - X\,{E_{3}}(X)
 + 2\,X^{2}\,{E_{2}}(X) - X^{4} - X\,{E_{4}}(X) \\
\mbox{} + 2\,X^{2}\,{E_{3}}(X) + X\,{E_{2}}(X)^{2} - 3\,X^{3}\,{E
_{2}}(X) + X^{5} - X\,{E_{5}}(X) \\
\mbox{} + 2\,X^{2}\,{E_{4}}(X) + 2\,X\,{E_{3}}(X)\,{E_{2}}(X) - 3
\,X^{3}\,{E_{3}}(X) - 3\,X^{2}\,{E_{2}}(X)^{2} \\
\mbox{} + 4\,X^{4}\,{E_{2}}(X) - X^{6}
\end{array}$$
}
%
\mwsin{BB := invsubst(FF,6);}
\mwsout{%
$$\begin{array}{c}
BB := X + X^{2} + X\,{E_{2}}(X) + X^{3} + X\,{E_{3}}(X) + 2\,X^{4} + X
^{2}\,{E_{2}}(X) + X\,{E_{4}}(X) \\
\mbox{} + 3\,X^{3}\,{E_{2}}(X) + X\,{E_{2}}(X^{2}) + 3\,X^{5} + X
^{2}\,{E_{3}}(X) + 6\,X^{6} + X\,{E_{5}}(X) \\
\mbox{} + 2\,X^{2}\,{E_{2}}(X^{2}) + 3\,X^{3}\,{E_{3}}(X) + X^{2}
\,{E_{4}}(X) + 6\,X^{4}\,{E_{2}}(X) \\
\mbox{} + X^{2}\,{E_{2}}(X)^{2}
\end{array}$$
}
%
\mwsin{ AA\ -\ BB;}
\mwsout{%
$$ 0 $$ }
\end{maplelike}


%%
%\subsection{Degree and table procedures}
\subsection{Degree and table procedures}


This category consists essentially of `interface' procedures related to the degree 
of a molecular species and to the homogeneous components of a species.  
These are the procedures
\texttt{degre}, \texttt{mdegre}, \texttt{coeffm} (English: \texttt{mcoeff}), 
\newline \texttt{phom} (\texttt{homcomp}), \texttt{tablephom} (\texttt{homcomptable}), 
\texttt{affichertable} (\texttt{print\-table}), 
\newline \texttt{sphom} (\texttt{homcompsum}),
as well as \texttt{tablearborr} (\texttt{rrtrees\-table}), 
\newline \texttt{tablearbrer} 
(\texttt{rtreestable}) and \texttt{tablearborgadd} (\texttt{gaddrtreestable}).

The command \texttt{degre(M)} returns the total degree of the molecular %one-sort
species $M$. In case of a multisort molecular species, the command \texttt{mdegre(M)}
can also be used, the result being a Maple table. 
The command \texttt{coeffm(F,M)} yields the coefficient (multiplicity) of the molecular
species $M$ in the species $F$.
Here are some examples.

\begin{maplelike}
%
\mwsin{degre(E[3](X*C[4](X)));}
\mwsout{%
\[
15
\]
}
%
\mwsin{mdegre(E[3](X*C[4](Y\^{}2*Z)));}
\mwsout{%
\[
\mathit{resultat}
\]
}
%
\mwsin{print(\%);}
\mwsout{%
$$\begin{array}{c}
\mathrm{table(}[X=3, \,Y=24, \,Z=12])
\end{array}$$
}
%
\mwsin{Phi:=1+X\^{}2+23*E[3](X*C[4](X))+6*E[3](C[5](X))+E[7](X);}%
\mwsout{%
$$\begin{array}{c}
\Phi:=1+X^{2}+23{E_{3}}(X{C_{4}}(X)) + 6{E_{3}}({C_{5}}(X)) + {E_{7}}(X)
\end{array}$$
}
%
\mwsin{coeffm(Phi,E[3](X*C[4](X)));}
\mwsout{%
\[
23
\]
}
\end{maplelike}
%

The command \texttt{phom(F,d)} returns the homogeneous part of degree $d$ of the species $F$,
while \texttt{tablephom(F)} stores in a Maple table the degrees which occur in $F$ and the
corresponding homogeneous components. This is particularly useful when the species $F$ is
big. Conversely, the procedure \texttt{sphom} converts a table into the sum of its entries
and hence returns the sum of the homogeneous parts in a table of the form \texttt{tablephom(F)}.
The procedure \texttt{affichertable} is a practical alternative to the Maple command
\texttt{print} for displaying a table.  

\begin{maplelike}
%
\mwsin{phom(Phi,15);}
\mwsout{%
$$\begin{array}{c}
23\,{E_{3}}(X\,{C_{4}}(X)) + 6\,{E_{3}}({C_{5}}(X))
\end{array} $$
}
%
\mwsin{T := tablephom(Phi);}
\mwsout{%
\[
T := \mathit{tph}
\]
}
%
\mwsin{print(T);}
\mwsout{%
$$\begin{array}{c}
\mathrm{table(}[0=1, \,2=X^{2}, \,7={E_{7}}(X), \,15=23\,{E_{3}}(
X\,{C_{4}}(X)) + 6\,{E_{3}}({C_{5}}(X))]) 
\end{array}$$
}
%
\mwsin{affichertable(T);}
\mwsout{%
$$\begin{array}{c}
0 \\
1
\end{array}$$
}
%
\mwsout{%
$$\begin{array}{c}
2 \\
X^{2}
\end{array}$$
}
%
\mwsout{%
$$\begin{array}{c}
7 \\
{E_{7}}(X)
\end{array}$$
}
%
\mwsout{%
$$\begin{array}{c}
15 \\
23\,{E_{3}}(X\,{C_{4}}(X)) + 6\,{E_{3}}({C_{5}}(X))
\end{array}$$
}
%
\mwsin{sphom(T);}
\mwsout{%
\[
1 + X^{2} + 23\,{E_{3}}(X\,{C_{4}}(X)) + 6\,{E_{3}}({C_{5}}(X))
 + {E_{7}}(X) \]
}
\end{maplelike}

Finally, the procedures \texttt{tablearborr}, \texttt{tablearbrer} and \texttt{tablearborgadd}
are simply the composition of \texttt{tablephom} with the procedures 
\texttt{arborr}, \texttt{arbrer} and \texttt{arborgadd} for enriched trees and rooted trees.

\subsection{Miscellaneous}
There are two other useful \emph{Devmol} procedures, \texttt{derpart} (English: \texttt{partder}) 
and \texttt{grouper} (\texttt{mcollect}),
which are illustrated in the following section.
The procedure \texttt{derpart} computes the partial derivative of a species with respect
to a given sort variable. The two basic facts here are the formulas 
\begin{equation}
\frac{\partial}{\partial X} E_n(X)=E_{n-1}(X) \ \ \mathrm{and} \ \ 
\frac{\partial}{\partial X} C_n(X)=X^{n-1}. \label{eq:derpart}
\end{equation}
Finally, the procedure \texttt{grouper} collects similar terms in a molecular expansion,
that is terms having the same molecule but various weights.

% Section 5 Two applications
\section{Two applications}
In this last section, we give two examples of applications of \emph{Devmol}.  The first one
is the computation of the \molexp\ of the species $A_w$ of rooted trees weighted by a leaf
counter $t$.  The second application is a procedure for the \molexp\ of the species
$\CB$ of connected (simple) graphs, all of whose blocks are in a given class $\B$ of 
$2$-connected graphs, for a generic $\B$. This procedure is then illustrated in the case
of the species $\Hu_w$ of weighted Husimi graphs presented as an example in Section 1.2.
%%
%\subsection{Rooted trees weighted with a leaf counter.}
\subsection{Rooted trees weighted with a leaf counter.}
Let us define the weight $w(\alpha)$ of a rooted tree $\alpha$ as $t^{l(\alpha)}$, where
$l(\alpha)$ denotes the number of leaves of $\alpha$. By convention, the root of a rooted
tree is a leaf only in the case of the single vertex rooted tree. The species of rooted trees
weighted in this manner will be denoted by $A_w$.
A slight modification of equation (\ref{eq:arbo}) leads to the functional equation
\begin{eqnarray}
A_w & = & X(t-1) + X\,E(A_w) \nonumber \\
  & = & tX + X\,E_+(A_w). \label{eq:aw}
\end{eqnarray}

It is thus possible to compute iteratively the \molexp\ of the species $A_w$ as explained 
in Section 3.1, up to a given degree $d$.
The procedure \texttt{lwrtrees(d)} which performs this computation is presented below.

%
\begin{maplelike}
%\mwsin{lwrtrees := proc(n)\\
%local k,Awl,Ek;\\
%with(devmol);\\
%Awl := t*X;\\
%Ek := 0;\\
%for k from 1 to n-1 do\\
%  Ek := Ek + E[k](X);\\
%  Awl := t*X + expand(X*dev(subs(X=Awl,Ek),k)); od;\\
%grouper(Awl)\\
%end;}
%
\mwsout{%
$$\begin{array}{l}
\mathit{lwrtrees} := \textbf{proc} (n) \\
\textbf{local} \,k, \,\mathit{Awl}, \,\mathit{Ek}; \\
\mapleIndent{1} \mathrm{with}(\mathit{devmol})\,; \\
\mapleIndent{1} \mathit{Awl} := t \ast X\,; \\
\mapleIndent{1} \mathit{Ek} := 0\,; \\
\mapleIndent{1} \textbf{for} \,k\,\textbf{to} \,n - 1\,\textbf{do
}  \\
\mapleIndent{2} \mathit{Ek} := \mathit{Ek} + {E_{k}}(X)\,; \\
\mapleIndent{2} \mathit{Awl} := t \ast X + \mathrm{expand}(X
 \ast \mathit{devmol}:-\mathit{dev}(\mathrm{subs}(X=\mathit{Awl}
, \,\mathit{Ek}), \,k)) \\
\mapleIndent{1} \textbf{end do} ; \\
\mapleIndent{1} \mathit{devmol}:-\mathit{grouper}(\mathit{Awl})
 \\
\textbf{end proc} 
\end{array}$$
}
\end{maplelike}

Here is the result of this computation up to degree 8.
%
\begin{maplelike}
\mwsin{affichertable(tablephom(lwrtrees(8)));}
\mwsout{%
$$\begin{array}{c}
1\\
t\,X
\end{array}$$
%
$$\begin{array}{c}
2\\
t\,X^{2}
\end{array}$$
%
$$\begin{array}{c}
3\\
t^{2}\,X\,{E_{2}}(X) + t\,X^{3}
\end{array}$$
%
$$\begin{array}{c}
4\\
t^{2}\,X^{2}\,{E_{2}}(X) + t^{3}\,X\,{E_{3}}(X) + (t + t^{2})\,X^{4}
\end{array}$$
%
$$\begin{array}{c}
5\\
(t + 2\,t^{2})\,X^{5} + (2\,t^{3} + t^{2})\,X^{3}\,{E_{2}}(X) + 
t^{3}\,X^{2}\,{E_{3}}(X) + t^{2}\,X\,{E_{2}}(X^{2}) \\
\mbox{} + t^{4}\,X\,{E_{4}}(X)
\end{array}$$
%
$$\begin{array}{c}
6\\
t^{4}\,{E_{2}}(X)^{2}\,X^{2} + t^{4}\,X^{2}\,{E_{4}}(X) + 
t^{5}\,X\,{E_{5}}(X) + (t^{3} + t^{2})\,X^{2}\,{E_{2}}(X^{2}) \\
\mbox{} + (2\,t^{4} + t^{3})\,X^{3}\,{E_{3}}(X) + (t^{2} + 5\,t^{3})\,X^{4}\,{E_{2}}(X) \\
\mbox{} + (t + 4\,t^{2} + t^{3})\,X^{6}
\end{array}$$
%
$$\begin{array}{c}
7\\
2\,t^{5}\,{E_{2}}(X)\,X^{2}\,{E_{3}}(X) + t^{4}\,X\,{E_{2}}(X)\,{E_{2}}(X^{2}) 
+ (t^{2} + 9\,t^{3} + 4\,t^{4})\,X^{5}\,{E_{2}}(X) \\
\mbox{} + 2\,t^{4}\,{E_{2}}(X)^{2}\,X^{3} + t^{5}\,X^{2}\,{E_{5}}(X) 
+ (2\,t^{3} + t^{2})\,X^{3}\,{E_{2}}(X^{2}) \\
\mbox{} + (5\,t^{4} + t^{3})\,X^{4}\,{E_{3}}(X) + (t^{4} + 2\,t^{
5})\,X^{3}\,{E_{4}}(X) + X\,t^{2}\,{E_{2}}(X^{3}) \\
\mbox{} + t^{4}\,X\,{E_{2}}(X\,{E_{2}}(X)) + t^{3}\,X\,{E_{3}}(X^{2}) 
+ t^{6}\,X\,{E_{6}}(X) \\
\mbox{} + (t + 6\,t^{2} + 5\,t^{3})\,X^{7}
\end{array}$$
%
$$\begin{array}{c}
8\\
t^{5}\,X\,{E_{3}}(X)\,{E_{2}}(X^{2}) + 2\,t^{6}\,{E_{2}}(X)\,X^{2
}\,{E_{4}}(X) + 3\,t^{4}\,X^{2}\,{E_{2}}(X)\,{E_{2}}(X^{2}) \\
\mbox{} + 5\,t^{5}\,{E_{2}}(X)\,X^{3}\,{E_{3}}(X) + (2\,t^{4} + t
 + 9\,t^{2} + 13\,t^{3})\,X^{8} \\
\mbox{} + (t^{4} + t^{5})\,X^{2}\,{E_{2}}(X\,{E_{2}}(X)) + (t^{3}
 + t^{2})\,X^{2}\,{E_{2}}(X^{3}) + t^{7}\,X\,{E_{7}}(X) \\
\mbox{} + t^{6}\,X^{2}\,{E_{6}}(X) + t^{6}\,{E_{3}}(X)^{2}\,X^{2}
 + (t^{5} + 2\,t^{6})\,X^{3}\,{E_{5}}(X) \\
\mbox{} + (t^{2} + 5\,t^{3} + t^{4})\,X^{4}\,{E_{2}}(X^{2}) + (14
\,t^{3} + t^{2} + 17\,t^{4})\,X^{6}\,{E_{2}}(X) \\
\mbox{} + (t^{3} + 9\,t^{4} + 4\,t^{5})\,X^{5}\,{E_{3}}(X) + (4\,
t^{4} + 4\,t^{5})\,{E_{2}}(X)^{2}\,X^{4} \\
\mbox{} + (5\,t^{5} + t^{4})\,X^{4}\,{E_{4}}(X) + (t^{3} + t^{4})
\,X^{2}\,{E_{3}}(X^{2})
\end{array}$$
}
\end{maplelike}

%%
%\subsection{Connected graphs with blocks in a given class $\B$}
\subsection{Connected graphs with blocks in a given class $\B$}

Let $\B$ be a class of 2-connected graphs.  A \emph{$\CB$-graph} is
defined as a connected graph all of whose blocks (2-connected components)
are in $\B$. The species of $\CB$-graphs is denoted by $\CB$.
Here are some examples for various choices of $\B$:
%%
\begin{enumerate}

\item % item 1
If $\B = \B_a$, the class of \emph{all} 2-connected graphs, then $\CB=\Gcon$, 
the species of (all) connected graphs.

\item % item 2
If  $\B=K_2$, the class of ''edges'', then $\CB=\arbres$, the species of (unrooted, free) trees.

\item % item 3
If $\B=\{P_m, m \geq 2\}$, where $P_m$ denotes the class of size-$m$ polygons (by convention,
$P_2=K_2$), then $\CB=\Ca$, the species of cacti. 
A \emph{cactus} can also be defined as a  connected graph
in which no edge lies in more than one cycle. 
Figure \ref{fig:cactus}, a),  represents a typical cactus.
%

\item % item 4
If $\B=K_3=P_3$, the class of "triangles", then $\CB=\delta$, the class of triangular cacti.

\item  % item 5
If $\B=\{ K_n, n \geq 2 \}$, the family of complete graphs, then $\CB= \Hu$, the species
of \emph{Husimi graphs}.
% that is of connected graphs whose blocks are complete graphs. They were
%first (informally) introduced by Husimi in \cite{Hu50}.
A Husimi graph is shown in Figure \ref{fig:Husimi}.
%

\item % item 6

If $\B = \{ C_n, n \geq 2 \}$, the family of oriented cycles, then  $\CB = \Oc$, the species of 
\emph{oriented cacti}. These structures were introduced by C. Springer \cite{Sp96} in 1996.
Although directed graphs are involved here, the functional equations (\ref{eq:cbpoint}) 
and (\ref{eq:CBBbis}) given below are still valid. 
Figure \ref{fig:cactus}, b) shows a typical oriented cactus.
%
\begin{figure}[bht] 
\begin{center}
\includegraphics[scale=.8]{fig-cactus.eps}
\end{center}
\caption{a) a
typical cactus, b) a typical oriented cactus \label{fig:cactus}}
\end{figure}
%
\end{enumerate}

Let $\CBpoint$ denote the species of rooted (at a vertex) $\CB$-graphs. Then the following two
equations (see \cite{BLL98}, \cite{Le03}) can be used to compute 
the molecular expansion of the species $\CB$. 
%
\begin{eqnarray}
\CBpoint & = & X \, E(\Bprime(\CBpoint)), \label{eq:cbpoint} \\
\CB & = & \CBpoint + \B(\CBpoint) - \CBpoint \, \Bprime(\CBpoint). \label{eq:CBBbis}
\end{eqnarray}
%
Here, $\Bprime$ denotes the derivative of the species $\B$.
Observe that equation (\ref{eq:cbpoint}) is of the form $Y=X\,R(Y)$, with $R=E(\Bprime)$, 
so that the procedure for $R$-enriched rooted trees can be used.  Moreover,
equations (\ref{eq:cbpoint}) and (\ref{eq:CBBbis}) are also valid for weighted 
$\CB$-graphs, whenever the weight function $w$ is multiplicative on the 2-connected
components. See \cite{Le03} for more details.

The procedure \texttt{CBgraphes} takes the class $\B$ of blocks and the degree $d$
as arguments. It computes the \molexp\ of the species of $\CB$-graphs up to
degree $d$.

\begin{maplelike}
\mwsout{%
$$\begin{array}{l}
\mathit{CBgraphes} := \textbf{proc} (B, \,n) \\
\textbf{local} \,\mathit{EE}, \,\mathit{Bprime}, \,R, \,\mathit{
GP}, \,\mathit{resultat}; \\
\mapleIndent{1} \mathrm{with}(\mathit{devmol})\,; \\
\mapleIndent{1} \mathit{EE} := 1 + \mathrm{sum}({E_{k}}(X), \,k=1
 .. n - 1)\,; \\
\mapleIndent{1} \mathit{Bprime} := \mathit{devmol}:-\mathit{
derpart}(B, \,X)\,; \\
\mapleIndent{1} R := \mathit{devmol}:-\mathit{dev}(\mathrm{subs}(
X=\mathit{Bprime}, \,\mathit{EE}), \,n - 1)\,; \\
\mapleIndent{1} \mathit{GP} := \mathit{devmol}:-\mathit{
arborr}(R, \,n)\,; \\
\mapleIndent{1} \mathit{resultat} :=  %\\ \mapleIndent{2} 
\mathit{devmol}:-\mathit{dev}(\mathrm{subs}(X=
\mathit{GP}, \,X + B - X \ast \mathit{Bprime}), \,n) \\
\textbf{end proc}
\end{array}$$
}
\end{maplelike}

In what follows, \emph{devmol} computes the \molexp, up to degree $7$,
of the weighted species $\Oc_w$ of oriented cacti, where the weight $w(c)$ 
of an oriented cactus $c$ is defined by $w(c) = y_2^{n_2} y_3^{n_3} \cdots$, 
where $n_k$ is the number of cycles of $c$ of size $k$. 
This is the case of $\CB$-graphs with $B=B_w$, 
the species of weighted oriented cycles of length at least $2$, 
where the weight of a cycle of length $k$ is $y_k$.
%
\begin{maplelike}
\mwsin{n := 7;}
\mwsout{%
$$n := 7$$
}
\mwsin{ajoutvv(seq(y[k], k = 1..n));}
\mwsout{%
$$\{t, \,{y_{1}}, \,{y_{2}}, \,{y_{3}}, \,{y_{4}}, \,{y_{5}}, \,{y
_{6}}, \,{y_{7}}\}$$
}
\mwsin{B := sum(y[k]*C[k](X), k = 2..n);}
\mwsout{%
$$\begin{array}{c}
B := {y_{2}}\,{C_{2}}(X) + {y_{3}}\,{C_{3}}(X) + {y_{4}}\,{C_{4}}
(X) + {y_{5}}\,{C_{5}}(X) + {y_{6}}\,{C_{6}}(X) \\
\mbox{} + {y_{7}}\,{C_{7}}(X) 
\end{array}$$
}
\mwsin{CBW := CBgraphes(B,n):}
\newpage
\mwsin{affichertable(tablephom(CBW));}
\mwsout{%
$$\begin{array}{c}
1\\
X
\end{array}$$
}
%
\mwsout{%
$$\begin{array}{c}
2\\
{y_{2}}\,{E_{2}}(X)
\end{array}$$
}
%
\mwsout{%
$$\begin{array}{c}
3\\
{y_{2}}^{2}\,X\,{E_{2}}(X) + {y_{3}}\,{C_{3}}(X)
\end{array}$$
}
%
\mwsout{%
$$\begin{array}{c}
4\\
{y_{2}}\,{y_{3}}\,X^{4} + {y_{2}}^{3}\,X\,{E_{3}}(X) + {y_{2}}^{3
}\,{E_{2}}(X^{2}) + {y_{4}}\,{C_{4}}(X)
\end{array}$$
}
%
\mwsout{%
$$\begin{array}{c}
5\\
({y_{3}}\,{y_{2}}^{2} + {y_{2}}^{4})\,X^{3}\,{E_{2}}(X) + ({y_{2}
}^{4} + {y_{3}}^{2})\,X\,{E_{2}}(X^{2}) + {y_{2}}^{4}\,X\,{E_{4}}
(X) \\
\mbox{} + ({y_{4}}\,{y_{2}} + 2\,{y_{3}}\,{y_{2}}^{2})\,X^{5} + {
y_{5}}\,{C_{5}}(X)
\end{array}$$
}
%
\mwsout{%
$$\begin{array}{c}
6\\
{y_{2}}^{5}\,{E_{2}}(X\,{E_{2}}(X)) + ({y_{2}}^{5} + {y_{3}}^{2}
\,{y_{2}} + {y_{4}}\,{y_{2}}^{2})\,{E_{2}}(X^{3}) \\
\mbox{} + ({y_{3}}\,{y_{2}}^{3} + {y_{2}}^{5})\,X^{3}\,{E_{3}}(X) + ({y_{4}}\,{y_{2}}^{2} + 3\,{y_{3}}\,{y_{2}}^{3} + {y_{2}}^{5})\,X^{4}\,{E_{2}}(X) \\
\mbox{} + ({y_{2}}^{5} + {y_{3}}^{2}\,{y_{2}})\,X^{2}\,{E_{2}}(X
^{2}) + {y_{3}}\,{y_{2}}^{3}\,{C_{3}}(X^{2}) + {y_{2}}^{5}\,X\,{E_{5}}(X) \\
\mbox{} + (2\,{y_{3}}^{2}\,{y_{2}} + 2\,{y_{4}}\,{y_{2}}^{2} + 4
\,{y_{3}}\,{y_{2}}^{3} + {y_{5}}\,{y_{2}} + {y_{3}}\,{y_{4}})\,X
^{6} + {y_{6}}\,{C_{6}}(X) 
\end{array}$$
}
%
\mwsout{%
$$\begin{array}{c}
7\\
(7\,{y_{4}}\,{y_{3}}\,{y_{2}} + {y_{3}}^{3} + {y_{2}}^{6} + {y_{5
}}\,{y_{3}} + {y_{6}}\,{y_{2}} + 3\,{y_{5}}\,{y_{2}}^{2} + 6\,{y
_{4}}\,{y_{2}}^{3} + 9\,{y_{3}}\,{y_{2}}^{4} %\\ \mbox{} 
+ 9\,{y_{3}}^{2}\,{y_{2}}^{2})X^{7} \\
\mbox{} + (2\,{y_{3}}^{2}\,{y_{2}}^{2} + {y_{5}}\,{y_{2}}^{2} + 8
\,{y_{3}}\,{y_{2}}^{4} + 4\,{y_{4}}\,{y_{2}}^{3} + 2\,{y_{2}}^{6}
)\,X^{5}\,{E_{2}}(X) + {y_{3}}\,{y_{2}}^{4}\,X^{3}\,{E_{2}}(X)^{2} \\
\mbox{}  + ({y_{3}}\,{y_{2}}^{4} + {y_{3}}^{2}\,{y_{2}}^{2})\,X^{3}\,{E_{2}}(X^{2}) %\\ \mbox{} 
+ ({y_{4}}\,{y_{2}}^{3} + 3\,{y_{3}}\,{y_{2}}^{4}  + {y_{2}}^{6})\,X^{4}\,{E_{3}}(X) +  \\
\mbox{} ({y_{3}}\,{y_{2}}^{4} + {y_{2}}^{6})
\,X^{3}\,{E_{4}}(X) + (3\,{y_{3}}^{2}\,{y_{2}}^{2} + {y_{4}}^{2} + {y_{2}}^{6
})\,X\,{E_{2}}(X^{3}) \\
\mbox{} + ({y_{2}}^{6} + {y_{3}}^{2}\,{y_{2}}^{2})\,X\,{E_{2}}(X)
\,{E_{2}}(X^{2}) + {y_{2}}^{6}\,X\,{E_{2}}(X\,{E_{2}}(X)) \\
\mbox{} + ({y_{3}}^{3} + {y_{2}}^{6})\,X\,{E_{3}}(X^{2}) + {y_{2}
}^{6}\,{E_{3}}(X)\,{E_{2}}(X)\,X^{2} + {y_{2}}^{6}\,X\,{E_{6}}(X) %\\ \mbox{} 
+ {y_{7}}\,{C_{7}}(X)
\end{array}$$
}
\end{maplelike}
%
%section{Availability of Devmol}
\section{Availability of Devmol}
The current version is Devmol 2.2.  It is constructed as a Maple module. The basic version
is in French but an English version, where the English aliases of the exported
procedures are implemented, is also available. 

It is freely available at the Web site of LaCIM: www.lacim.uqam.ca.

\subsection{Glossary}
Here is a short dictionary, from French to English, of the exported procedures of Devmol.

affichertable  =  printtable

ajoutvs  =  addsv

ajoutvv  =  addwv

arborgadd  =  gaddrtrees

arborr  =  rrtrees

arbrer  =  rtrees

coeffm  =  mcoeff

derpart  =  partder

grouper  =  mcollect

invsubst  =  invsubs

phom  =  homcomp

rac  =  nroot

sge  =  egs

sgef  =  fegs

sgt  =  tgs

sphom  =  homcompsum

tablearborgadd  =  gaddrtreestable

tablearborr  =  rrtreestable

tablearbrer  =  rtreestable

tablephom  =  homcomptable


%
\input{bibliodevmol}
%
\end{document}




