Séminaire Lotharingien de Combinatoire 49 (2003), Article B49z

Computing the molecular expansion of species with the Maple package Devmol

Pierre Auger, Gilbert Labelle and Pierre Leroux LaCIM, Université du Québec à Montréal

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 tilde generating function

F̃(x) = ∑_{n≥0} f̃_{n}x^{n}  (1)

of the number f̃_{n} of unlabelled F -structures of size n.

For example, the tilde generating function Ã(x) of the species A of (free) rooted trees, up to size 6, is

Ã(x) = x + x^{2} + 2x^{3} + 4x^{4} + 9x^{5} + 20x^{6} + · · · .  (2)

It is refined by the molecular expansion of A given in Section 1.1 (see (6)) 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 while XE_{2}(X) represents the rooted star .

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. 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 ≥ 0, 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, Devmol has the capacity to handle weighted multisort species with scalar coefficients in the complex field ℂ. 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 [9] and [2] for a basic presentation of species theory and also to [4] 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 isomorphic if one can be obtained from the other by a relabelling along a bijection. Unlabelled F -structures can be seen as isomorphism classes of F -structures. A species M is called molecular if it has only one isomorphism class. It is completely determined by the stabilizer H = Stab(s) of one of its structures, say s ∈ M[n], where n is the degree of M and [n] = {1, 2, …, n}. We write M(X) = X^{n}/H. In particular, we have

L_{n} = X^{n}/{1}, E_{n} = X^{n}/S_{n}, C_{n} = X^{n}/⟨ρ⟩,  (3)

where S_{n} denotes the symmetric group on [n] and ρ generates a cyclic subgroup of order n of S_{n}.

For a general molecular species

M(X) = X^{n}/H,

the cycle index series Z_{M}(x_{1}, x_{2}, …) coincides with the cycle index polynomial Z_{H}(x_{1}, x_{2}, …) of H ≤ 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 [2], Section 4.6, for more details.

Two F -structures are called 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 1 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 molecular expansion of a species F is defined as the equality (natural isomorphism)

F = ∑_{M∈M} f_{M}M,  (4)

where f_{M} is the multiplicity of the molecular species M in F and 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 B of species of cyclo-set type.

1 Some examples of molecular expansions

The 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.

1.1 Rooted trees

First, consider the well-known species A of rooted trees, defined by the functional equation

A = XE(A),  (5)

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{matrix}A = X + X^{2} + XE_{2}(X) + X^{3} + XE_{3}(X) + 2X^{4} + X^{2}E_{2}(X) \\ +XE_{4}(X) + 3X^{3}E_{2}(X) + XE_{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} + XE_{5}(X) + 6X^{6} + · · · . \end{matrix}  (6)

The homogeneous component of degree 5 of this molecular expansion is

XE_{4}(X) + 3X^{3}E_{2}(X) + XE_{2}(X^{2}) + 3X^{5} + X^{2}E_{3}(X)

These terms are illustrated in Figure 1.

1.2 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 weight variables. For example, let the weight variables be y_{2}, y_{3}, . . .. Define a Husimi graph as a connected graph all of whose blocks (2-connected components) are complete graphs (see [14]). The weight w(g) of a Husimi graph g is defined by w(g) = y_{2}^{n_{2}}y_{3}^{n_{3}} ⋯, where n_{i} is the number of blocks of g of size i for

3 X^{3}E_{2}(X) 3 X^{5} X^{2}E_{3}(X) XE_{2}(X^{2})  XE_{4}(X)

Figure 1: Rooted trees of size 5

i = 2, 3, . . .. An example is given in Figure 2. The weighted species of Husimi graphs is denoted by Hu_{w}. Its molecular expansion up to degree 6 is computed by Devmol as:

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{matrix}(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) + y_{3}^{2} X E_{2}(E_{2}(X)) + y_{5} E_{5}(X) + y_{2} y_{4} X^{2} E_{3}(X) \end{matrix}

Figure 2: A Husimi graph of weight y_{2}^{4}y_{3}y_{4}^{2}y_{5}

Degree 6:

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}) + (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))

+ 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) + 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).

As an illustration, the nine terms of size 5 are shown in Figure 3. 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.

2 Addition formulas

The main feature of 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)

y_{2}^{2}y_{3} · XE_{2}(X)^{2} y_{2}^{2}y_{3} · XE_{2}(X^{2}) y_{3}^{2} · XE_{2}(E_{2}(X))  y_{2}^{2}y_{3} · X^{3}E_{2}(X) y_{2}^{4} · X^{3}E_{2}(X)  y_{5} · E_{5}(X) y_{2}^{4} · XE_{2}(X^{2})  y_{2}y_{4} · X^{2}E_{3}(X)  y_{2}^{4} · XE_{4}(X)

Figure 3: Husimi graphs of size 5

n. Observe that Maple already knows the addition formulas for the species L_{n} = X^{n}, using the “expand” function: for a given n ≥ 0, we have, for example,

(X + Y)^{n} = ∑_{i=0}^{n} \binom{n}{i}X^{i}Y^{n−i}.  (7)

Note that for any molecular species M of degree n, we have M(1) = 1 and, more generally, for any scalar k,

M(k) = Z_{M}(k, k, …).  (8)

Formula (8) holds for any non-negative integer k in virtue of Pólya theory and the extension to a general scalar is valid by polynomiality. Also, for any weight variable t, we have

M(tX) = t^{n}M(X).  (9)

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 [1]. They are implemented in Devmol.

2.1 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 ≥ 0, we have

E_{n}(X_{1} + ⋯ + X_{k}) = ∑_{{n_{1}+···+n_{k}=n \atop n_{i}≥0}} E_{n_{1}}(X_{1}) ⋯ E_{n_{k}}(X_{k}).  (10)

It follows that

E_{n}(kX) = ∑_{i=1}^{n} \binom{k}{i} ∑_{λ⊢_{i}n} \binom{n}{λ_{1}, …, λ_{i}} E_{λ_{1}}(X) ⋯ E_{λ_{i}}(X),  (11)

the expression λ ⊢_{i} n meaning that the summation index λ is a partition of n into i parts, and that

E_{n}(k + X) = \frac{k^{⟨n⟩}}{n!} + \frac{k^{⟨n−1⟩}}{(n − 1)!}X + … + E_{n}(X),  (12)

where k^{⟨n⟩} = k(k + 1) ⋯ (k + n − 1).

2.2 Addition formulas related to the species of cycles

For the species C of oriented cycles, we have

C_{n}(X_{1} + ⋯ + X_{k}) = ∑_{d|n} ∑_{{ψ_{1}+···+ψ_{k}=d \atop ψ_{i}≥0}} λ_{ψ}C_{n/d} (X_{1}^{ψ_{1}} ⋯ X_{k}^{ψ_{k}}) ,  (13)

where, for ψ = (ψ_{1}, …, ψ_{k}), λ_{ψ} denotes the number of Lyndon words on 𝔛 = {x_{1} < … < x_{k}} having distribution ψ, i. e. ψ_{ν} occurrences of the letter x_{ν}, ν = 1, …, k. Recall that a Lyndon word is a primitive (not a power of another word) lexicographically minimal word in its cyclic conjugacy class. Using Möbius inversion, it can be shown that

λ_{ψ} = \frac{1}{ψ_{1} + ⋯ + ψ_{k}} ∑_{d|gcd(ψ_{1},···,ψ_{k})} μ(d) ( \frac{ψ_{1}}{d} , ⋯, \frac{ψ_{k}}{d}^{\frac{ψ_{1}+···+ψ_{k}}{d}} ) .  (14)

Moreover, one has

C_{n}(kX) = ∑_{d|n} λ_{d}(k)C_{n/d}(X^{d}),  (15)

where λ_{d}(k) = \frac{1}{d} ∑_{δ|d} μ(δ)k^{d/δ} is the number of Lyndon words of length d in a k-element alphabet, and

C_{n}(k + X) = \frac{1}{n} ∑_{d|n} ϕ(d)k^{n/d} + ∑_{d|n} ∑_{{i+j=d \atop i>0}} λ_{i,j}(k) C_{n/d}(X^{i}),  (16)

the coefficients λ_{i,j}(k) being given by the formula

λ_{i,j}(k) = \frac{1}{i + j} ∑_{δ|(i,j)} μ(δ)\binom{(i + j)/δ}{i/δ}k^{j/δ}.  (17)

Note that by polynomiality, equations (11), (12), (15) and (16) are also valid for any scalar k = ξ ∈ ℂ.

3 Species implicitly defined by functional equations

3.1 R-enriched rooted trees

Let R be a species such that R(0) ≠ 0. The species A_{R} of R-enriched rooted trees is the unique species satisfying the combinatorial equation

A_{R} = X R(A_{R}).  (18)

Figure 4: Typical R-enriched rooted tree

Figure 4 shows a typical R-enriched rooted tree on the set U = {a, b, …, k}, where all edges have been oriented towards the root, the vertex e. Hence, an A_{R}-structure is a rooted tree where the fiber of each vertex (that is the set of immediate predecessors) is endowed with an R-structure. Familiar examples include

1. Ordered (or plane) rooted trees, where R = L,

2. Ordinary rooted trees, where R = E,

3. Mobiles, where R = 1 + C.

Let us illustrate the iterative method for computing the molecular expansion 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

F_{≤n} = F |_{≤n} = F_{0} + F_{1} + … + F_{n}  (19)

to denote the restriction of F to sets of size at most n.

We start with

A_{≤0} = 0,

since there is no rooted tree on the empty set. Next, we have

A_{≤1} = (X · E_{0}(A)) |_{≤1} = X.

The general iteration formula is given by

A_{≤n} = (X · E_{≤n−1}(A_{≤n−1})) |_{≤n}
= X · E_{≤n−1}(A_{≤n−1})|_{≤n−1}.  (20)

Hence, one has successively

A_{≤2} = X · E_{≤1}(A_{1})|_{≤1}
= X · ((1 + X)^{∘} X)|_{≤1}
= X · (1 + X)
= X + X^{2},

A_{≤3} = X · E_{≤2}(A_{≤2})|_{≤2}
= X · ((1 + X + E_{2}(X))^{∘} (X + X^{2}))|_{≤2}
= X · (1 + X + X^{2} + E_{2}(X + X^{2}))|_{≤2}
= X · (1 + X + X^{2} + E_{2}(X) + X^{3} + E_{2}(X^{2}))|_{≤2}
= X + X^{2} + X^{3} + XE_{2}(X),

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 = XR(A). We start with A_{0} = 0 or A_{1} = XR_{0}. Furthermore, the general recurrence relation can be written as

A_{≤n} = X · R_{≤n−1}(A_{≤n−1})|_{≤n−1}.  (21)

The molecular expansion of A can then be computed recursively, using (21). Hence, the Maple package Devmol can compute the molecular expansion of the species A_{R} for any R of cyclo-set type. For example, the molecular expansion of the species A_{1+C} of “mobiles” is, up to degree 6,

A_{1+C}|_{≤6} = X + X^{2} + XE_{2}(X) + X^{3} + XC_{3}(X) + 2X^{4} + X^{2}E_{2}(X)

+XC_{4}(X) + 4X^{5} + XE_{2}(X^{2}) + 2X^{3}E_{2}(X) + X^{2}C_{3}(X)

+XC_{5}(X) + 5X^{4}E_{2}(X) + 2X^{3}C_{3}(X) + X^{2}C_{4}(X)  (22)
+X^{2}E_{2}(X^{2}) + 10X^{6}.

3.2 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 5 for an illustration. For example, plane trees can be seen as 1 + C-enriched trees.

The species of R-enriched trees is denoted by a_{R}. It can be expressed in terms of the species A_{R′} of R′-enriched rooted trees, where R′ denotes the derivative of the species R, using the Dissymmetry Theorem for R-enriched trees (see [2], Theorem 4.1.2). Indeed, we have

a_{R} = XR(A_{R′}) + E_{2}(A_{R′}) − A_{R′}^{2}.  (23)

Figure 5: Typical R-enriched tree

Figure 6: Typical G-additive rooted tree

3.3 G-additive rooted trees.

Another important family of species defined by functional equations is that of G-additive rooted trees, where G is a given species such that O(G) ≥ 2, that is G(0) = G′(0) = 0. It is defined as the species B = B(X) which satisfies the additive functional equation

B = X + G(B).  (24)

This species is often denoted by B = _{G}A. See Figure 6 for an illustration of a typical _{G}A-structure.

An example is also given by the species P = P (X) of parenthesizations, which can be defined by the functional equation

P = X + P^{2}.  (25)

It is clear that the molecular expansion of the species _{G}A of G-additive rooted trees can also be computed recursively, whenever effective addition formulas are known for G.

4 Presentation of the Maple package Devmol

4.1 Basic purpose

The basic purpose of the Maple package Devmol is to compute the molecular expansion 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} + 2XY + Y^{2}.

Let A denote the alphabet of sort variables and V the alphabet of weight variables. The language L_{A} of recognized expressions is then defined by the following grammar :

1. 1 ∈ L_{A},

2. X ∈ A ⇒ X ∈ L_{A},

3. p ∈ ℂ[V], Φ ∈ L_{A} ⇒ p ∗ Φ ∈ L_{A},

4. Φ, Ψ ∈ L_{A} ⇒ Φ + Ψ ∈ L_{A} and Φ ∗ Ψ ∈ L_{A},

5. n ∈ ℕ, Φ ∈ L_{A} ⇒ E_{n}(Φ) ∈ L_{A} and C_{n}(Φ) ∈ L_{A}.

The package Devmol, or , more precisely, its main procedure dev, can then be seen as an operator of the form

L_{A} ⟶ ℂ[V][[M_{A}]]

which computes the molecular expansion of a recognized expression. The result is a formal power series with coefficients in the ring ℂ[V] over the set M_{A}, of (unweighted) molecular species of cyclo-set type in the sorts A. This set is defined recursively as follows:

1. 1 ∈ M_{A}

2. X ∈ A ⇒ X ∈ M_{A},

3. M, N ∈ M_{A} ⇒ M · N ∈ M_{A}, 4. n ∈ ℕ, n ≥ 2, M ∈ M_{A} ⇒ E_{n}(M) ∈ M_{A},

5. n ∈ ℕ, n ≥ 3, M ∈ M_{A} ⇒ C_{n}(M) ∈ M_{A}.

The Maple package Devmol comprises basically two main (internal) procedures, expand/E and expand/C which extend the Maple procedure expand. When the expand procedure is applied to a recognized expression, it recursively calls the relevant procedure each time a sub-expression of the form E_{n}(·) or C_{n}(·) is met. Each of these procedures “executes” the corresponding addition formula.

As mentioned in the introduction, the default set of sort variables is A = {X, Y, Z}. To include new sort variables, one uses the procedure ajoutvs, which is short for French “ajouter variables de sortes” (English alias: addsv). More precisely, the command

 > ajoutvs(YY);

adds the name Y Y to the set 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 ajoutvv (English alias: addwv) to add new elements to the set V of weight variables. Once added to this set, a weight variable becomes global too. The initial set of weight variables is V = {t}.

4.2 The procedure dev

The most fundamental procedure of Devmol is dev. The purpose of dev(Phi,d) is to compute the molecular expansion of the recognized expression Phi, up to the given truncation degree d.

Examples.

 > ajoutvv(u);

{t, u}

 > Phi := E[5](E[2](X) + u*X);

Φ := E_{5}(E_{2}(X) + u X)

 > dev(Phi,10);

\begin{matrix}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)) \\ + u^{3} E_{3}(X) E_{2}(E_{2}(X)) + u^{2} E_{2}(X) E_{3}(E_{2}(X)) \end{matrix}

 > dev((X^2 + t*E[3](Y))^5, infinity);

\begin{matrix}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} \\ + 5 t^{4} E_{3}(Y)^{4} X^{2} + t^{5} E_{3}(Y)^{5} \end{matrix}

 > dev((1 - Z - Z^2)^(-1), 10);

\begin{matrix}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} \\ + 89 Z^{10} \end{matrix}

 > dev(E[5](1 + t * X), 5);

1 + t X + t^{2} E_{2}(X) + t^{3} E_{3}(X) + t^{4} E_{4}(X) + t^{5} E_{5}(X)

 > dev(E[5](3 + t*X), 5);

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)

 > dev(E[5](a + t*X), 5);

\frac{a (a + 1) (a + 2) (a + 3) (a + 4)}{120} + \frac{a (a + 1) (a + 2) (a + 3) t X}{24}

+ \frac{1}{6} a (a + 1) (a + 2) t^{2} E_{2}(X) + \frac{1}{2} a (a + 1) t^{3} E_{3}(X)

+ a t^{4} E_{4}(X) + t^{5} E_{5}(X)

 > dev(E[5](u + t*X), 5);

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)

4.3 Procedures for computing generating series

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

Examples 1. We compute these series up to degree 10 for the species of oriented cycles.

 > FF := sum(C[k](X), k = 1..10);

\begin{matrix}FF := C_{1}(X) + C_{2}(X) + C_{3}(X) + C_{4}(X) + C_{5}(X) + C_{6}(X) + C_{7}(X) \\ + C_{8}(X) + C_{9}(X) + C_{10}(X) \end{matrix}

 > GG := dev(FF,10);

\begin{matrix}GG := X + E_{2}(X) + C_{3}(X) + C_{4}(X) + C_{5}(X) + C_{6}(X) + C_{7}(X) + C_{8}(X) \\ + C_{9}(X) + C_{10}(X) \end{matrix}

 > sge(GG,10);

x + \frac{1}{2} x^{2} + \frac{1}{3} x^{3} + \frac{1}{4} x^{4} + \frac{1}{5} x^{5} + \frac{1}{6} x^{6} + \frac{1}{7} x^{7} + \frac{1}{8} x^{8} + \frac{1}{9} x^{9} + \frac{1}{10} x^{10}

 > sgef(GG,10);

\begin{matrix}\frac{x}{1!} + \frac{x^{2}}{2!} + \frac{2 x^{3}}{3!} + \frac{6 x^{4}}{4!} + \frac{24 x^{5}}{5!} + \frac{120 x^{6}}{6!} + \frac{720 x^{7}}{7!} + \frac{5040 x^{8}}{8!} \\ + \frac{40320 x^{9}}{9!} + \frac{362880 x^{10}}{10!} \end{matrix}

 > sgt(GG,10);

x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6} + x^{7} + x^{8} + x^{9} + x^{10}

2. Here is an example involving a two-sort species:

 > Phi := (1 + X + E[2](X) + E[3](X)) * (1 + C[3](Y));

Φ := (1 + X + E_{2}(X) + E_{3}(X)) (1 + C_{3}(Y))

 > dev(Phi,9);

\begin{matrix}1 + C_{3}(Y) + X + X C_{3}(Y) + E_{2}(X) + E_{2}(X) C_{3}(Y) + E_{3}(X) \\ + E_{3}(X) C_{3}(Y) \end{matrix}

 > sge(Phi,9);

1 + \frac{1}{3} y^{3} + x + \frac{1}{3} x y^{3} + \frac{1}{2} x^{2} + \frac{1}{6} x^{2} y^{3} + \frac{1}{6} x^{3} + \frac{1}{18} x^{3} y^{3}

 > sgef(Phi,9);

\frac{1}{1!} + \frac{2 y^{3}}{3!} + \frac{x}{1!} + \frac{2 x y^{3}}{1! 3!} + \frac{x^{2}}{2!} + \frac{2 x^{2} y^{3}}{2! 3!} + \frac{x^{3}}{3!} + \frac{2 x^{3} y^{3}}{(3!)^{2}}

 > sgt(Phi,9);

1 + y^{3} + x + x y^{3} + x^{2} + x^{2} y^{3} + x^{3} + x^{3} y^{3}

4.4 Procedures for computing the molecular expansion of tree-like species

There are procedures in Devmol for computing the molecular expansion of the classes of tree-like species described in Section 3. These are arborr (English: rrtrees), for the species of R-enriched rooted trees, arbrer (rtrees), for R-enriched trees, and arborgadd (gaddrtrees), for G-additive rooted trees.

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

4.4.1 R-enriched rooted trees

The command arborr(R,d) returns the molecular expansion up to degree d of the species A_{R} of R-enriched rooted trees.

Example. Ordinary rooted trees.

 > R := 1 + sum(E[k](X), k = 1..5);

R := 1 + E_{1}(X) + E_{2}(X) + E_{3}(X) + E_{4}(X) + E_{5}(X)

 > A := arborr(R,6);

A := 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) + 3 X^{3} E_{2}(X) + X E_{2}(X^{2}) + 3 X^{5} + X^{2} E_{3}(X) + 6 X^{6}
+ X^{2} E_{2}(X)^{2} + X^{2} E_{4}(X) + 6 X^{4} E_{2}(X) + 3 X^{3} E_{3}(X)
+ 2 X^{2} E_{2}(X^{2}) + X E_{5}(X)

 > sge(A,6);

x + \frac{125}{24} x^{5} + \frac{3}{2} x^{3} + \frac{54}{5} x^{6} + \frac{8}{3} x^{4} + x^{2}

 > sgef(A,6);

\frac{x}{1!} + \frac{2 x^{2}}{2!} + \frac{9 x^{3}}{3!} + \frac{64 x^{4}}{4!} + \frac{625 x^{5}}{5!} + \frac{7776 x^{6}}{6!}

 > sgt(A,6);

x + x^{2} + 2 x^{3} + 4 x^{4} + 9 x^{5} + 20 x^{6}

4.4.2 R-enriched trees

The command arbrer(R,d) returns the molecular expansion up to degree d of the species a_{R} of R-enriched trees.

Example. The following example gives the molecular expansion (up to degree 8) of the species a_{R}, where R = C. This is the species of plane trees.

 > R := 1 + X + sum(C[k](X), k = 2..7);

R := 1 + X + C_{2}(X) + C_{3}(X) + C_{4}(X) + C_{5}(X) + C_{6}(X) + C_{7}(X)

 > A := arbrer(R, 8);

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)

+ X C_{4}(X) + X C_{5}(X) + X + 3 X E_{2}(X^{3}) + X E_{2}(X^{2}) + X C_{3}(X)

+ 5 E_{2}(X^{4}) + 3 X^{6} + E_{2}(X) + X^{5} + 28 X^{8}

 > sge(A,8);

\frac{7}{4} x^{5} + \frac{21}{5} x^{6} + 11 x^{7} + \frac{5}{6} x^{4} + \frac{1}{2} x^{2} + \frac{1}{2} x^{3} + \frac{429}{14} x^{8} + x

 > sgef(A,8);

\frac{x}{1!} + \frac{x^{2}}{2!} + \frac{3 x^{3}}{3!} + \frac{20 x^{4}}{4!} + \frac{210 x^{5}}{5!} + \frac{3024 x^{6}}{6!} + \frac{55440 x^{7}}{7!} + \frac{1235520 x^{8}}{8!}

 > sgt(A,8);

x + x^{2} + x^{3} + 2 x^{4} + 3 x^{5} + 6 x^{6} + 14 x^{7} + 34 x^{8}

4.4.3 G-additive rooted trees

The command arborgadd(G,d) returns the molecular expansion up to degree d of the species a_{G} of G-additive rooted trees.

Example.

 > G := E[2](X) + E[3](X);

G := E_{2}(X) + E_{3}(X)

 > A := arborgadd(G,6);

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)

+ 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))

+ X^{2} E_{3}(X) + E_{2}(X) X^{3} + 6 E_{2}(X) X E_{3}(X)
+ 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}
+ E_{2}(E_{3}(X)) + E_{2}(E_{2}(X) X) + 2 X^{2} E_{2}(E_{2}(X)) + X^{3} E_{3}(X)
+ E_{2}(X) X^{4}

 > sgt(A,6);

x + x^{2} + 2 x^{3} + 4 x^{4} + 9 x^{5} + 23 x^{6}

4.5 A procedure for computing the n^{th} root of a species

There is a procedure, rac (English: nroot), in Devmol, for computing the n^{th} root of a species. An n^{th} root of a species F is a species Φ such that Φ^{n} = F. As in the case of formal power series, Φ is uniquely determined once its constant term Φ_{0} has been given, satisfying Φ_{0}^{n} = F_{0}, under the condition that F_{0} is invertible in the ring ℂ[V]; and the algorithm for computing Φ is the same as for formal power series. It makes use of Newton’s binomial theorem. Let F = F_{0} + F_{+}. Then we have

Φ = F^{1/n}
= F_{0}^{1/n} (1 + \frac{F_{+}}{F_{0}} )^{1/n}
= Φ_{0} · ∑_{k≥0} \binom{1/n}{k} (\frac{F_{+}}{F_{0}} )^{k} .  (26)

The command rac(n,F,Φ_{0},d) returns the molecular expansion of (26) truncated at degree d. Observe that we could compute in the same manner any rational power F^{α} of F, for α ∈ ℚ.

Examples. 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

B = 1 + E(XB^{2}).  (27)

In fact, B is the species of triangle-labelled oriented-edge-rooted 2-trees (see [5]).

 > R := 1 + sum(E[k](X), k = 1..6);

R := 1 + E_{1}(X) + E_{2}(X) + E_{3}(X) + E_{4}(X) + E(X) + E_{6}(X)

 > A := arborr(R,7):
 > A2 := dev(subs(X = 2*X,A)/(2*X),6):
 > rac(2,A2,1,6);

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) + 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) + 22 X^{2} E_{2}(X^{2}) + 201 X^{4} E_{2}(X) + 10 X^{2} E_{4}(X) + X E_{5}(X) + 2 E_{2}(X^{2}) + 2 E_{3}(X^{2}) + 5 E_{2}(X^{3}) + 2 E_{2}(X E_{2}(X)) + X + 6 E_{3}(X) X E_{2}(X) + 2 E_{2}(X) E_{2}(X^{2}) + 388 X^{6} + E_{4}(X) + E_{5}(X) + E_{6}(X) + E_{2}(X) + E_{3}(X) + 2 X^{2} + 7 X^{3} + 24 X^{4}

+ 3 X E_{2}(X)^{2} + 95 X^{5}

2. The species P = P (X) of parenthesizations, introduced in Section 3.3, is defined by the functional equation (25) or equivalently, by

P^{2} − P + X = 0,  (28)

Solving this quadratic equation yields

P (X) = \frac{1 − \sqrt{1 − 4X}}{2} .  (29)

This expression is expanded up to degree 10 in the following lines. Anyone will recognize the familiar Catalan numbers.

 > S := rac(2,1-4*X,1,10);

\begin{matrix}S := 1 − 2 X − 2 X^{2} − 4 X^{3} − 10 X^{4} − 28 X^{5} − 84 X^{6} − 264 X^{7} \\ − 858 X^{8} − 2860 X^{9} − 9724 X^{10} \end{matrix}

 > P(X) := (1 - S)/2;

\begin{matrix}P (X) := X + X^{2} + 2 X^{3} + 5 X^{4} + 14 X^{5} + 42 X^{6} + 132 X^{7} + 429 X^{8} \\ + 1430 X^{9} + 4862 X^{10} \end{matrix}

4.6 A procedure for computing the inverse under substitution

The inverse under substitution of a species Φ = Φ(X) is defined whenever Φ(0) = 0 and Φ′(0) = 1, i. e. when Φ is of the form Φ = X +Φ_{≥2}. The inverse of such a species is then the species Ψ such that Φ^{∘} Ψ = X. The procedure invsubst (English: invsubs) computes the inverse under substitution of a species, up to the given degree.

Examples. 1. We compute the inverse under substitution up to degree 5 of the species X + E_{2}(X) + … + E_{5}(X). Note that this inverse is equal to the inverse of E_{+} = E − 1 up to the same degree.

 > Phi := sum(E[k](X), k = 1..5);

Φ := E_{1}(X) + E_{2}(X) + E_{3}(X) + E_{4}(X) + E_{5}(X)

> invsubst(Phi, 5);

X − E_{2}(X) − E_{3}(X) + X E_{2}(X) − E_{4}(X) + E_{2}(E_{2}(X)) + X E_{3}(X)

− X^{2} E_{2}(X) − E_{5}(X) + X E_{4}(X) + E_{2}(X) E_{3}(X) − X^{2} E_{3}(X)

− E_{2}(X)^{2} X + X^{3} E_{2}(X)

2. The equation (28) shows that the species P (X) is the substitutional inverse of X − X^{2}. This is verified here up to degree 10.

> Phi := X - X^2;

Φ := X − X^{2}

> invsubst(Phi,10);

\begin{matrix}X + X^{2} + 2 X^{3} + 5 X^{4} + 14 X^{5} + 42 X^{6} + 132 X^{7} + 429 X^{8} + 1430 X^{9} \\ + 4862 X^{10} \end{matrix}

3. In this example, we verify, up to degree 6, that the species A of rooted trees satisfies the combinatorial equation A = (XE(−X))^{⟨−1⟩}.

> EE := 1 + sum(E[k](X), k = 1..5);

EE := 1 + E_{1}(X) + E_{2}(X) + E_{3}(X) + E_{4}(X) + E_{5}(X)

> AA := arborr(EE,6);

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)

+ 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)

+ 2 X^{2} E_{2}(X^{2}) + 3 X^{3} E_{3}(X) + X^{2} E_{4}(X) + 6 X^{4} E_{2}(X)

+ X^{2} E_{2}(X)^{2}

> FF := dev(X*subs(X=-X,EE), 6);

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)

+ 2 X^{2} E_{3}(X) + X E_{2}(X)^{2} − 3 X^{3} E_{2}(X) + X^{5} − X E_{5}(X)

+ 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}
+ 4 X^{4} E_{2}(X) − X^{6}

> BB := invsubst(FF,6);

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)

+ 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)

+ 2 X^{2} E_{2}(X^{2}) + 3 X^{3} E_{3}(X) + X^{2} E_{4}(X) + 6 X^{4} E_{2}(X)
+ X^{2} E_{2}(X)^{2}

 > AA - BB;

0

4.7 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 degre, mdegre, coeffm (English: mcoeff),

phom (homcomp), tablephom (homcomptable), affichertable (printtable),
sphom (homcompsum), as well as tablearborr (rrtreestable),
tablearbrer (rtreestable) and tablearborgadd (gaddrtreestable).

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

 > degre(E[3](X*C[4](X)));

15

 > mdegre(E[3](X*C[4](Y^2*Z)));

resultat

 > print(%);

table([X = 3, Y = 24, Z = 12])

 > Phi:=1+X^2+23*E[3](X*C[4](X))+6*E[3](C[5](X))+E[7](X);

Φ := 1 + X^{2} + 23E_{3}(XC_{4}(X)) + 6E_{3}(C_{5}(X)) + E_{7}(X)

 > coeffm(Phi,E[3](X*C[4](X)));

23

The command phom(F,d) returns the homogeneous part of degree d of the species F, while 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 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 tablephom(F). The procedure affichertable is a practical alternative to the Maple command print for displaying a table.

 > phom(Phi,15);

23 E_{3}(X C_{4}(X)) + 6 E_{3}(C_{5}(X))

 > T := tablephom(Phi);

T := tph

 > print(T);

table([0 = 1, 2 = X^{2}, 7 = E_{7}(X), 15 = 23 E_{3}(X C_{4}(X)) + 6 E_{3}(C_{5}(X))])

 > affichertable(T);

{0 \atop 1}

\begin{matrix}2 \\ X^{2} \end{matrix}

\begin{matrix}7 \\ E_{7}(X) \end{matrix}

\begin{matrix}15 \\ 23 E_{3}(X C_{4}(X)) + 6 E_{3}(C_{5}(X)) \end{matrix}

 > sphom(T);

1 + X^{2} + 23 E_{3}(X C_{4}(X)) + 6 E_{3}(C_{5}(X)) + E_{7}(X)

  Finally, the procedures tablearborr, tablearbrer and tablearborgadd

are simply the composition of tablephom with the procedures arborr, arbrer and arborgadd for enriched trees and rooted trees.

4.8 Miscellaneous

There are two other useful Devmol procedures, derpart (English: partder) and grouper (mcollect), which are illustrated in the following section. The procedure derpart computes the partial derivative of a species with respect to a given sort variable. The two basic facts here are the formulas

\frac{∂}{∂X} E_{n}(X) = E_{n−1}(X) and \frac{∂}{∂X} C_{n}(X) = X^{n−1}.  (30)

Finally, the procedure grouper collects similar terms in a molecular expansion, that is terms having the same molecule but various weights.

5 Two applications

In this last section, we give two examples of applications of Devmol. The first one is the computation of the molecular expansion of the species A_{w} of rooted trees weighted by a leaf counter t. The second application is a procedure for the molecular expansion of the species C_{B} 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.

5.1 Rooted trees weighted with a leaf counter.

Let us define the weight w(α) of a rooted tree α as t^{l(α)}, where l(α) denotes the number of leaves of α. 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 (5) leads to the functional equation

A_{w} = X(t − 1) + X E(A_{w})
= tX + X E_{+}(A_{w}).  (31)

It is thus possible to compute iteratively the molecular expansion of the species A_{w} as explained in Section 3.1, up to a given degree d. The procedure lwrtrees(d) which performs this computation is presented below.

lwrtrees := proc(n) local k, Awl, Ek;

with(devmol) ; Awl := t ∗ X; Ek := 0 ; for k to n − 1 do

Ek := Ek + E_{k}(X) ;

Awl := t ∗ X + expand(X ∗ devmol : −dev(subs(X = Awl, Ek), k)) end do; devmol : −grouper(Awl)

end proc

Here is the result of this computation up to degree 8.

> affichertable(tablephom(lwrtrees(8)));

\begin{matrix}1 \\ t X \end{matrix}

\begin{matrix}2 \\ t X^{2} \end{matrix}

\begin{matrix}3 \\ t^{2} X E_{2}(X) + t X^{3} \end{matrix}

\begin{matrix}4 \\ t^{2} X^{2} E_{2}(X) + t^{3} X E_{3}(X) + (t + t^{2}) X^{4} \end{matrix}

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})

+ t^{4} X E_{4}(X) 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})

+ (2 t^{4} + t^{3}) X^{3} E_{3}(X) + (t^{2} + 5 t^{3}) X^{4} E_{2}(X)

+ (t + 4 t^{2} + t^{3}) X^{6}

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)

+ 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}) + (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})

+ t^{4} X E_{2}(X E_{2}(X)) + t^{3} X E_{3}(X^{2}) + t^{6} X E_{6}(X)

+ (t + 6 t^{2} + 5 t^{3}) X^{7}

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})

+ 5 t^{5} E_{2}(X) X^{3} E_{3}(X) + (2 t^{4} + t + 9 t^{2} + 13 t^{3}) X^{8} + (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)

+ 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) + (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)

+ (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}

+ (5 t^{5} + t^{4}) X^{4} E_{4}(X) + (t^{3} + t^{4}) X^{2} E_{3}(X^{2})

5.2 Connected graphs with blocks in a given class B

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

1. If B = B_{a}, the class of all 2-connected graphs, then C_{B} = C, the species of (all) connected graphs.

2. If B = K_{2}, the class of ”edges”, then C_{B} = a, the species of (unrooted, free) trees.

3. If B = {P_{m}, m ≥ 2}, where P_{m} denotes the class of size-m polygons (by convention, P_{2} = K_{2}), then C_{B} = Ca, the species of cacti. A cactus can also be defined as a connected graph in which no edge lies in more than one cycle. Figure 7, a), represents a typical cactus.

4. If B = K_{3} = P_{3}, the class of ”triangles”, then C_{B} = δ, the class of triangular cacti.

5. If B = {K_{n}, n ≥ 2}, the family of complete graphs, then C_{B} = Hu, the species of Husimi graphs. A Husimi graph is shown in Figure 2.

6. If B = {C_{n}, n ≥ 2}, the family of oriented cycles, then C_{B} = Oc, the species of oriented cacti. These structures were introduced by C. Springer [20] in 1996. Although directed graphs are involved here, the functional equations (32) and (33) given below are still valid. Figure 7, b) shows a typical oriented cactus.

Figure 7: a) a typical cactus, b) a typical oriented cactus

Let C_{B}^{•} denote the species of rooted (at a vertex) C_{B}-graphs. Then the following two equations (see [2], [14]) can be used to compute the molecular expansion of the species C_{B}.

C_{B}^{•} = X E(B′(C_{B}^{•})),  (32)
C_{B} = C_{B}^{•} + B(C_{B}^{•}) − C_{B}^{•} B′(C_{B}^{•}).  (33)

Here, B′ denotes the derivative of the species B. Observe that equation (32) is of the form Y = X R(Y), with R = E(B′), so that the procedure for R-enriched rooted trees can be used. Moreover, equations (32) and (33) are also valid for weighted C_{B}-graphs, whenever the weight function w is multiplicative on the 2-connected components. See [14] for more details.

The procedure CBgraphes takes the class B of blocks and the degree d as arguments. It computes the molecular expansion of the species of C_{B}-graphs up to degree d.

CBgraphes := proc(B, n) local EE, Bprime, R, GP, resultat;

with(devmol) ; EE := 1 + sum(E_{k}(X), k = 1..n − 1) ; Bprime := devmol : −derpart(B, X) ; R := devmol : −dev(subs(X = Bprime, EE), n − 1) ; GP := devmol : −arborr(R, n) ; resultat := devmol : −dev(subs(X = GP, X + B − X ∗ Bprime), n)

end proc

In what follows, devmol computes the molecular expansion, 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}} ⋯, where n_{k} is the number of cycles of c of size k. This is the case of C_{B}-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}.

> n := 7;

n := 7

> ajoutvv(seq(y[k], k = 1..n));

{t, y_{1}, y_{2}, y_{3}, y_{4}, y_{5}, y_{6}, y_{7}}

> B := sum(y[k]*C[k](X), k = 2..n);

\begin{matrix}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) \\ + y_{7} C_{7}(X) \end{matrix}

> CBW := CBgraphes(B,n):

 > affichertable(tablephom(CBW));

\begin{matrix}1 \\ X \end{matrix}

\begin{matrix}2 \\ y_{2} E_{2}(X) \end{matrix}

\begin{matrix}3 \\ y_{2}^{2} X E_{2}(X) + y_{3} C_{3}(X) \end{matrix}

\begin{matrix}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{matrix}

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) + (y_{4} y_{2} + 2 y_{3} y_{2}^{2}) X^{5} + y_{5} C_{5}(X) 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}) + (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) + (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) + (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) 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} + 9 y_{3}^{2} y_{2}^{2})X^{7} + (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}

+ (y_{3} y_{2}^{4} + y_{3}^{2} y_{2}^{2}) X^{3} E_{2}(X^{2}) + (y_{4} y_{2}^{3} + 3 y_{3} y_{2}^{4} + y_{2}^{6}) X^{4} E_{3}(X)+

(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})
+ (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))

+ (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) + y_{7} C_{7}(X)

6 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.

6.1 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

References

[1] Pierre Auger, Gilbert Labelle and Pierre Leroux, Combinatorial addition formulas and applications, Advances in Applied Mathematics, 28 (2002), 302–342.

[2] François Bergeron, Gilbert Labelle and Pierre Leroux, Combinatorial Species and Tree-Like Structures, Cambridge University Press, 1998, 457 p. Vol. 67 of the series Encyclopedia of Mathematics and its Applications.

[3] Miklós Bóna, Michel Bousquet, Gilbert Labelle and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24, 2000, 22–56.

[4] Yves Chiricota, Structures combinatoires et calcul symbolique, PhD Thesis, UQAM, 1992, Publications du LaCIM, Vol. 12, 1993.

[5] Tom Fowler, Ira Gessel, Gilbert Labelle and Pierre Leroux, The specification of 2-tress, Advances in Applied Mathematics, 28, 2002, 145–168.

[6] Frank Harary, Graph Theory, Addison-Wesley, 1969, 274 p.

[7] Frank Harary and Edgar Palmer. Graphical Enumeration, Academic Press, New York and London, 1973, 271 p.

[8] Kodi Husimi. Note on Mayers’ theory of cluster integrals, The Journal of Chemical Physics, 18, 1950, 682–684.

[9] André Joyal, Une théorie combinatoire des séries formelles, Advances in Mathematics, 42, 1981, 1–82.

[10] Gilbert Labelle, Counting asymmetric enriched trees, Journal of Symbolic Computation, 14, 1992, 211–242.

[11] Gilbert Labelle, Cédric Lamathe, Pierre Leroux, Énumération des 2arbres k-gonaux, Proceedings of the conference Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, Versailles, September 16–19, 2002, in Mathematics and Computer Science II, B. Chauvin, P. Flajolet, D. Gardy, and A. Mokkadem, ed., Birkhäuser, Basel, 2002, 95–109.

[12] Gilbert Labelle, Cédric Lamathe and Pierre Leroux, A classification of plane and planar 2-trees, Theoretical Computer Science, To appear.

[13] Pierre Leroux, Methoden der Anzahlbestimmung für einige Klassen von Graphen, Bayreuther Mathematische Schriften, 26, 1988, 1–36.

[14] Pierre Leroux, Enumerative problems inspired by Mayer’s theory of cluster integrals, Plenary talk, FPSAC03 Conference, Linköping University (Sweden), June 23 - 27, 2003.

[15] Pierre Leroux and Brahim Miloudi, Généralisations de la formule d’Otter, Annales des Sciences Mathématiques du Québec, 16, 1992, 53– 80.

[16] Mélanie Nadeau, Graphes de Husimi, cactus, et mécanique statistique. Mémoire de maîtrise, UQAM, 2002.

[17] Robert Z. Norman, On the number of linear graphs with given blocks, Dissertation, University of Michigan, 1954.

[18] Richard Otter, The number of trees, Annals of Mathematics, 49, 1948, 583–599.

[19] Robert Robinson, Enumeration of non-separable graphs, Journal of Combinatorial Theory, 9, 1970, 327–356.

[20] Colin Springer, Factorizations, trees, and cacti, Proceedings of the Eighth International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC), University of Minnesota, 1996, 427–438.