<figure><img src="image_1.png" /></figure>

HAL
open science

# Composition of grammars and associated L-species

Benjamin Randrianirina

► To cite this version:

Benjamin Randrianirina. Composition of grammars and associated L-species. 2025. hal-05091963

HAL Id: hal-05091963

https://hal.science/hal-05091963v1

Preprint submitted on 2 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Open licence - etalab
Composition of grammars and associated L-species

Benjamin RANDRIANIRINA*

Laboratoire de Mathématiques et Applications de l'Université de Fianarantsoa (LaMAF),
University of Fianarantsoa, Madagascar

à la mémoire de Pierre Leroux (1942-2008)

Abstract

The main goal of the article is to demonstrate a compositional version of L-species of the notion of grammar composition defined by William Chen. The result is applied to a particular class of grammar, which we call type (E) grammar, and whose composition is equivalent to the product of the matrices associated with these grammars. Our primary tool is the Leroux-Viennot's method for solving combinatorial differential equations and systems. We therefore begin our study with a review of the main results on this method and its connection with the William Chen's grammar.

Keywords: Species, system of combinatorial differential equations, grammar, composition of grammars

# 1 Introduction

The use of production rules from algebraic grammars in enumerative combinatorics was initiated by W.Y. C. Chen in [5]. This idea was further taken by D. Dumont in [6], by showing in particular that grammatical calculus often reflects a combinatorial calculus on enumerating polynomials, as W.Y.C. Chen and A. M. Fu do in [4]. He also asserted that a grammar can be transformed into a system of analytic differential equations, allowing the calculation of exponential generating series.

A notion of grammar composition was defined by Chen in his article. The main purpose of this article is to provide an L-species composition version of this notion in section 5. The results will be applied in the section 6 to the particular class of type grammars to show that the composition of these grammars is equivalent to a convolution of associated matrices (see Boyadzhiev [2], or D. E. Knuth [11]).

The fundamental tools that we will use for this purpose are the Leroux-Viennot's methods for solving combinatorial differential equations and systems (see [14], [15], and [16]), methods based on species theory ([10] or [1]), and more specifically on L-species ([1] chapter 5 or [23] or [22]). Unfortunately, this method is not very well known. For example, in [17], Mendez and Ramirez assert that the combinatorial differential calculus related to William Chen's grammars is not equivalent to the combinatorial differential calculus introduced by A. Joyal within the species theory framework. This assertion is

<footnote>*Email: benjamin.randrianirina@univ-fianarantsoa.mg</footnote>
true if we limit ourselves to a particular class of species known as $\mathcal{B}$-species. Indeed, in [23] (see also [22]), it was shown that, under certain conditions, providing a system of combinatorial differential equations is equivalent as providing a Chen's grammar or as providing a system of analytical differential equations. A review of the essential results on the Leroux-Viennot method and its connection with Chen's grammars is therefore necessary.

In section 2, we show the difference between $\mathcal{B}$-species, $\mathcal{L}$-species, and mixed species. The review of the Leroux-Viennot methods and their connection with Chen's grammars will be provided in section 3 and its links with William Chen's grammars in section 4.

## 2 $\mathcal{B}$-species, $\mathcal{L}$-species, and mixed species

According to André Joyal ([6], definition 1), a species of structure, also known as a $\mathcal{B}$-species, is a functor from the category $\mathcal{B}$ of finite sets and bijection to the category $\mathcal{B}$. In other words, a $\mathcal{B}$-species ($[1]$) is a rule $\mathcal{F}$ which:

1. produces, for each finite set $U$, a finite set $\mathcal{F}[U]$,

2. produces, for each bijection $\sigma : U \to V$, a function $\mathcal{F}[\sigma] : \mathcal{F}[U] \to \mathcal{F}[V]$, satisfying the following properties:

a) for all bijection $\sigma : U \to V$ and $\tau : V \to W$, $\mathcal{F}[\tau \circ \sigma] = \mathcal{F}[\tau] \circ \mathcal{F}[\sigma]$,

b) for the identity map $\mathrm{Id}_U : U \to U$, $\mathcal{F}[\mathrm{Id}_U] = \mathrm{Id}_{\mathcal{F}[U]}$.

An element $s \in \mathcal{F}[U]$ is called an $\mathcal{F}$-structure on $U$. The function $\mathcal{F}[\sigma]$ is called the transport of $\mathcal{F}$-structures along $\sigma$.

A linear species or $\mathcal{L}$-species ([6], definition 12) is a functor from the category $\mathcal{L}$ of finite linear orders and order-preserving bijection to the category $\mathcal{B}$. So, a $\mathcal{L}$-species ($[1]$) is a rule $\mathcal{F}$ which:

1. produces, for each totally ordered finite set $U$, a finite set $\mathcal{F}[U]$,

2. produces, for each increasing bijection $\sigma : U \to V$, a function $\mathcal{F}[\sigma] : \mathcal{F}[U] \to \mathcal{F}[V]$, satisfying the following properties:

a) for all increasing bijection $\sigma : U \to V$ and $\tau : V \to W$, we have $\mathcal{F}[\tau \circ \sigma] = \mathcal{F}[\tau] \circ \mathcal{F}[\sigma]$,

b) for the identity map we have $\mathrm{Id}_U : U \to U$, $\mathcal{F}[\mathrm{Id}_U] = \mathrm{Id}_{\mathcal{F}[U]}$.

It should be noted that $\mathcal{B}$-species are more suited to set-theoretic actions of symmetric groups: calculating the number of isomorphism classes or the number of structures fixed by these actions. Recall that if $\mathcal{F}$ is a $\mathcal{B}$-species and $E$ is a finite set, then two structures $s$ and $s'$ in $\mathcal{F}(E)$ are isomorphic if there exists a bijection $\sigma : E \to E$ such that $s' = \mathcal{F}(\sigma)(s)$. The isomorphism class of $s$ is then called the isomorphism type of $s$. A $\mathcal{B}$-species $\mathcal{F}$ is asymmetric if each type of isomorphism is reduced to a singleton.

For a totally ordered set $l$, the unique increasing bijection of $l$ is the identity, so the notion of type of isomorphism has no meaning in the context of $\mathcal{L}$-species. However, $\mathcal{L}$-species, particularly developed by Leroux and Viennot, are more directly suited to calculations on formal series, or more precisely exponential generating series, and are closely related to differential equations in the classical analytic sense.
A weighted $\mathbb{L}$-species is a functor from the category $\mathbb{L}$ of finite linear orders and order-preserving bijection to the category of weighted set. An isomorphism of weighted $\mathbb{L}$-species $\mathbb{F}$ and $\mathbb{G}$ is a family $\phi = (\phi_l)_l$, of bijection $\phi_l : \mathbb{F}(l) \to \mathbb{G}(l)$ preserving the weight. We write $\mathbb{F} = \mathbb{G}$ if there exist an isomorphism $\phi : \mathbb{F} \to \mathbb{G}$. As an example, the $\mathbb{L}$-species $\mathbb{L}$ of lists, $\mathbb{A}_2$ of increasing binary trees, and $\mathbb{S}$ of permutations are isomorphic, that is $\mathbb{L} = \mathbb{A}_2 = \mathbb{S}$.

The exponential generating series of a species ($\mathbb{L}$ or $\mathbb{B}$) is the series $\mathbb{F}(t) = \sum_{n \ge 0} f_n \frac{t^n}{n!}$, where $f_n = |\mathbb{F}[n]|$.

Operations sum, product, composition, and derivations that are compatible with the transition to exponential generating series are defined on the class of species ($\mathbb{L}$ or $\mathbb{B}$). Hereafter, the product and composition of two $\mathbb{L}$-species $\mathbb{F}$ and $\mathbb{G}$ will be denoted respectively by $\mathbb{F} \cdot \mathbb{G}$ and $\mathbb{F} \circ \mathbb{G}$. Note that $s \in (\mathbb{F} \cdot \mathbb{G})[l]$ if only if $s = (s_1, s_2)$, $s_1 \in \mathbb{F}[A]$ and $s_2 \in \mathbb{G}[l \setminus A]$, $A \subset l$. And $s \in (\mathbb{F} \circ \mathbb{G})[l]$ if only if $s = (\pi, (f, (g_b)_{b \in \pi}))$, where $\pi$ is a partition of $l$, ordered by $b_i \le b_j$ iff $\min b_i \le \min b_j$, $f$ is an $\mathbb{F}$-structure on $\pi$, and for each block $b \in \pi$, $g_b$ is a $\mathbb{G}$-structure on $b$. Note also that the composition of $\mathbb{L}$-species is associative, meaning that if $\mathbb{F}, \mathbb{G}$, and $\mathbb{H}$ are $\mathbb{L}$-species, then $(\mathbb{F} \circ \mathbb{G}) \circ \mathbb{H} = \mathbb{F} \circ (\mathbb{G} \circ \mathbb{H})$.

**Lemma 1** If $\mathbb{F}$ and $\mathbb{G}$ are two $\mathbb{L}$-species such that $\mathbb{G}(\emptyset) = \emptyset$, then $s \in (\mathbb{F} \circ \mathbb{G})[n]$ if and only if $s$ can be identified with a pair $(s_1, s_2)$ such that $s_1 \in \mathbb{F}[k]$, $k \in [n]$, and $s_2 \in \mathbb{E}_k \circ \mathbb{G}[n]$, where $\mathbb{E}_k$ is the species of sets of cardinality $k$.

*Proof:* If $s = (\pi, (f, (g_b)_{b \in \pi})) \in (\mathbb{F} \circ \mathbb{G})[n]$, then $f$ can be identified, by structure transport, with an $\mathbb{F}$-structure $s_1$ on $[k]$, where $k = |\pi|$. Taking $s_2 = \{g_b, b \in \pi\}$, we obtain the result. ◇

**Definition 1** Let $\mathbb{E}$ be the $\mathbb{L}$-species of sets, $\mathbb{G}$ an $\mathbb{L}$-species such that $\mathbb{G}(\emptyset) = \emptyset$, $\mathbb{F} = \mathbb{E} \circ \mathbb{G}$ and $s$ an $\mathbb{F}$-structure. Each element of $s$ is called a connected component of $s$. The matrix $M = (a(n, k))_{n,k \in \mathbb{N}}$, where $a(n, k)$ is the number of elements of $\mathbb{F}[n]$ having $k$ connected components, is called the matrix of $\mathbb{F}$.

<figure><img src="image_3.png" /><figcaption>Figure 1: An $\int \mathbb{F}$-structure</figcaption></figure>

However, integration is only possible for $\mathbb{L}$-species. If $\mathbb{F}$ is an $\mathbb{L}$-species, then the integral of $\mathbb{F}$, denoted $\int \mathbb{F}$, is defined for every finite totally ordered set $l$ by $(\int \mathbb{F})(l) = \emptyset$ if $l = \emptyset$, and $(\int \mathbb{F})(l) = \mathbb{F}(l \setminus \{\min l\})$ if $l \ne \emptyset$. Figure 1 shows a generic $(\int \mathbb{F})$-structure over $l = \{1, 2, 3, 4, 5\}$. As example, the $\mathbb{L}$-specie $\mathcal{C}$ of circular permutation verify $\mathcal{C} = \int \mathbb{S} = \int \mathbb{L}$, and $\mathbb{S} = \mathbb{L} = \mathbb{E} \circ \mathcal{C}$.

Note that, if $\mathbb{F}$ is a species, then $\mathbb{F}^+$ is the species defined by $\mathbb{F}^+(E) = \mathbb{F}(E)$ if $E \ne \emptyset$ and $\mathbb{F}^+(\emptyset) = \emptyset$. On the other hand, $\int \mathbb{E} = \mathbb{E}^+$.

A mixed species is a functor from the category $\mathbb{L} \times \mathbb{B}$ to the category of weighted finite sets and weight-preserving bijection. In other words, a mixed species is a rule $\mathbb{F} = \mathbb{F}(T, X)$ which:
1. for each $(l, U)$, where $l$ is a totally ordered finite set and $U$ a finite set, produce a finite weighted set $\mathbb{F}[l, U]$,

2. for each $(\sigma, \tau) : l \times U \to l' \times V$, where $\sigma : l \to l'$ is an increasing bijection and $\tau : U \to V$ a bijection, associate a function $\mathbb{F}[\sigma, \tau] : \mathbb{F}[l \times U] \to \mathbb{F}[l' \times V]$, satisfying the following properties:

a) for all $(\sigma, \tau) : l \times U \to l' \times V$ and $(\sigma', \tau') : l' \times V \to l'' \times W$, we have:

$$ \mathbb{F}[(\sigma', \tau') \circ (\sigma, \tau)] = \mathbb{F}[\sigma', \tau'] \circ \mathbb{F}[\sigma, \tau], $$

b) $\mathbb{F}[\mathrm{Id}_l, \mathrm{Id}_U] = \mathrm{Id}_{\mathbb{F}[l, U]}$.

Let $\mathbb{F}$ a mixed species. The integral of $\mathbb{F}$ is the mixed species defined by $(\int \mathbb{F})[l, U] = \emptyset$ if $l = \emptyset$ and $(\int \mathbb{F})[l, U] = \mathbb{F}([\min l], U)$ if $l \neq \emptyset$. In the other hand, if $s \in \mathbb{F}[l \times U]$, then the type of $s$ with respect to $X$ is the class of $s$ for the equivalence $s \sim s'$ if there exists a bijection $\sigma : U \to U$ such that $s' = \mathbb{F}(\mathrm{Id}_l, \sigma)(s)$. The $\mathbb{L}$-specie $T_{X=x}\mathbb{F}$ of types with respect to $X$ is defined by $(T_{X=x}\mathbb{F})[l] = \cup_{k \in \mathbb{N}} \mathbb{F}[l, [k]]/\sim$. It is weighted by $w(\bar{s}) = v(s)x^k$, if $s \in \mathbb{F}[l \times [k]]$.

Now, let $\mathbb{G}_v$ be a weighted $\mathbb{B}$-species and $\mathbb{F} = \mathbb{F}_w$ a mixed species. The composition $(\mathbb{G} \circ \mathbb{F})_u$ is the mixed species defined by:

$$ (\mathbb{G} \circ \mathbb{F})[l \times U] = \sum_{\pi \in \mathrm{Par}(l \cup U)} \mathbb{G}[\pi] \times \prod_{c \in \pi} \mathbb{F}[l \cap c, U \cap c] $$

with $u(f, (s_c)_{c \in \pi}) = v(f) \prod_{c \in \pi} w(s_c)$. We have the theorem ([23] corollary 4.11):

**Theorem 1** If $\mathbb{F}_w = \mathbb{F}_w(T, X)$ is a mixed species such that $\mathbb{F}(0, X) = X$ and $\mathbb{G}_v = \mathbb{G}_v(X)$ a $\mathbb{B}$-species, then:

$$ T_{X=x}(\mathbb{G}_v \circ \mathbb{F}_w)(t) = Z_{\mathbb{G}}(T_{X=x}\mathbb{F}_w(t); x^2, x^3, \dots) \quad (1) $$

where $Z_{\mathbb{G}}$ is the cycle index series of $\mathbb{G}$. If $\mathbb{G}$ is asymmetric, then:

$$ T_{X=x}(\mathbb{G}_v \circ \mathbb{F}_w)(t) = \mathbb{G}_v(T_{X=x}\mathbb{F}_w(t)) \quad (2) $$

For more information on $\mathbb{B}$-species, see [1], on $\mathbb{L}$-species see [1], chapter 5, or [23] or [22], and on mixed species see [23] or [22].

# 3 Leroux-Viennot's methods

Consider the combinatorial differential equation:

$$ Y' = \mathbb{F}(Y), \quad Y(0) = X \quad (3) $$

where $Y$ is the unknown species, $\mathbb{F}$ a given species, and $X$ a type of points representing the initial conditions. This equation is written in the form $\frac{\partial Y}{\partial T} = \mathbb{F}(Y(T, X))$, $Y(0, X) = X$ and in integral form as:

$$ Y(T, X) = X + \int_{0}^{T} \mathbb{F}(Y(U, X))dU \quad (4) $$
<figure><img src="image_4.png" /><figcaption>Figure 2: Integral Equation</figcaption></figure>

This integral equation, represented by Figure 2, is an iterative process allowing the construction of the combinatorial solution. We obtain the species $A_F(T, X) = e^{TD}(X) = \sum_{n \ge 0} \frac{(TD)^n}{n!} (X)$ of $\mathbb{F}$-enriched rooted trees, where $D = \mathbb{F}(X) \frac{\partial}{\partial X}$ is the combinatorial differential operator associated with the equation (3), and $\frac{(TD)^n}{n!} (X)$ is the set of structures obtained by iterating this process $n$ times. Note that $A_F(T, X)$ is an $\mathbb{L}$-species of two kinds if $\mathbb{F}$ is an $\mathbb{L}$-species and a mixed species if $\mathbb{F}$ is a $\mathbb{B}$-species. An example of a generic $A_F(T, X)$-structure on $l \times U$, where $l = [6]$ and $U = \{a, b, c, d, e, f\}$ is given by Figure 3(A).

<figure><img src="image_5.png" /><figcaption>Figure 3: An $A_F$-structure (A), his isomorphism type (B)</figcaption></figure>

An analytical initial condition of the form $y(0) = x$ is combinatorially translated as $Y(0) = 1_x$, where $1_x$ is the species of the empty set, weighted by $x$. If $\mathbb{F}$ is a $\mathbb{B}$-species, the combinatorial differential equation $Y' = \mathbb{F}(Y)$, $Y(0) = 1_x$ makes sense and its solution is the weighted $\mathbb{L}$-species $A_F(T) = T_{X=x}(A_F(T, X))$ of the types with respect to the variable $X$ of $A_F(T, X)$ ([23], theorem 6.3). Its generating series $y(t) = A_F(t)$ is generally the solution of the differential equation:

$$y'(t) = Z_{\mathbb{F}}(y(t); x, x^2, \dots), \quad y(0) = x. \qquad (5)$$

If $\mathbb{F}$ is asymmetric, this equation becomes:

$$y'(t) = \mathbb{F}(y), \quad y(0) = x, \qquad (6)$$

where $\mathbb{F}(t)$ is the exponential generating series of $\mathbb{F}$. An example of an $A_F$-structure is given by Figure 3(B).

**Example 1** Let us consider combinatorial differential equation:

$$Y' = Y^{m+1}, \quad Y(0) = X \qquad (7)$$

The solution of (7) is the mixed species of $(m+1)$-ary complete rooted trees $e^{TG}(T, X) = A_{m+1}(T, X)$, where the leaves are of type $X$. The isomorphism types with respect to $X$ are
<figure><img src="image_6.png" /><figcaption>Figure 4: A₂-structure, for $n = 0, n = 1$ and $n = 2$</figcaption></figure>

the L-species $A_{m+1,\alpha}(T)$ of $m+1$-ary increasing rooted trees weighted by $\alpha(b) = x^{mn+1}$ if $b \in A_{m+1}[n]$. Figure 4 represents A₂-structure for $n = 0, n = 1$ and $n = 2$. Moreover, the exponential generating series, solution of the associated analytical differential equation, $y'(t) = y^{n+1}(t)$, $y(0) = x$, is:

$$A_{m+1,\alpha}(t) = \frac{x}{(1 - m x^m t)^{\frac{1}{m}}} \quad \text{si } m \neq 0 \text{ et } A_{1,\alpha}(t) = x e^t. \qquad (8)$$

**Remark: 1** The species $A_{1,\alpha}$ is the L-species $\mathbb{E}$ of sets weighted by $\alpha(U) = x$, and it will be denoted by $x\mathbb{E}$. The species $A_{2,\alpha}$ is the L-species of increasing binary trees weighted by $\alpha(b) = x^{n+1}$ if $b$ contains $n$ internal vertices, isomorphic to the L-species of permutations, weighted by $\alpha(\sigma) = x^{n+1}$ if $\sigma \in S_n$, or the L-species of lists weighted in the same way. ◇

These results can be generalized to the system of combinatorial differential equations:

$$\{Y'_{i} = \mathbb{F}_{i}(Y_{1}, Y_{2}, \dots, Y_{k}), Y_{i}(0) = X_{i}, 1 \le i \le k\}. \qquad (9)$$

One can associate with this system the combinatorial differential operator $\mathcal{D} = \sum_{i=1}^{k} \mathbb{F}_{i}(X_{1}, \dots, X_{k}) \frac{\partial}{\partial X_{i}}$. which, by extending the previously described method to the case of species with several variables, allows for the construction of combinatorial solutions. We have the following theorem ([15] or [1] chapter 5, theorem 9):

**Theorem 2** Let $A_{\vec{\mathbb{F}},i}(T, \vec{X}) = e^{T\mathcal{D}}(X_i)$ be the species of $\vec{\mathbb{F}}$-enriched rooted trees, solution of the differential equation $Y'_i = \mathbb{F}_i(Y_1, \dots, Y_k)$, $Y_i(0) = X_i$. Then the k-tuple of $\vec{\mathbb{F}}$-enriched rooted trees $\vec{A}_{\vec{\mathbb{F}}} = (A_{\vec{\mathbb{F}},1}, \dots, A_{\vec{\mathbb{F}},k})$ is, up to isomorphism, the unique solution of the system (9).

Moreover, for any species $\mathcal{G} = \mathcal{G}(X_1, \dots, X_k)$, one has:

$$\mathcal{G}(\vec{A}_{\vec{\mathbb{F}}}) = e^{T\mathcal{D}}(\mathcal{G}(X_1, \dots, X_k)). \qquad (10)$$

Note that the species $A_{\vec{\mathbb{F}},i}$ are L-species if the $\mathbb{F}_i$ are L-species and mixed species if the $\mathbb{F}_i$ are B-species. If the $\mathbb{F}_i$ are B-species then the unique solution of the system of combinatorial differential equations (see [22] or [23]):

$$\{Y'_{i} = \mathbb{F}_{i}(Y_{1}, \dots, Y_{k}), Y_{i}(0) = 1_{x_{i}}, 1 \le i \le k\} \qquad (11)$$

is the k-tuple $\vec{A}_{\vec{\mathbb{F}}} = (A_{\vec{\mathbb{F}},1}, \dots, A_{\vec{\mathbb{F}},k})$, where $A_{\vec{\mathbb{F}},i} = T_{\vec{X}=\vec{x}} A_{\vec{\mathbb{F}},i}(T, \vec{X})$. And if the $\mathbb{F}_i$ are asymmetric, her exponential generating series are the solutions of the system of analytical differential equations:

$$\{y'_{i}(t) = \mathbb{F}_{i}(y_{1}(t), \dots, y_{k}(t)), y_{i}(0) = x_{i}, 1 \le i \le k\}. \qquad (12)$$
**Example 2** Let us consider the system of differential equations:

$$ \begin{cases} U' = UV, & U(0) = Z \\ V' = V, & V(0) = X \end{cases} \qquad (13) $$

Example 1 shows that $V(T, X) = X\mathbb{E}(T)$. So the isomorphism type is $V = x\mathbb{E}$. Figure 5(A) represent the integral equation for $U$, and (B) one solution on [6], that corresponds to the partition $\{\{1, 4\}, \{2\}, \{3, 5, 6\}\}$ whose weight is $zx^3$. So $U = \mathbb{P}\mathrm{ar}_\omega$ is the specie of partition weighted by $\omega(\pi) = zx^{[\pi]}$.

<figure><img src="image_7.png" /><figcaption>Figure 5: (A) Integral equation for $U$; (B) A solution with $n = 6$</figcaption></figure>

Theorems 1 and 2 show that:

**Corollary 3** Given an asymmetric $\mathbb{B}$-species $\mathbb{G}_v = \mathbb{G}_v(\vec{X})$, one has:

$$ T_{\vec{X}=\vec{x}}(e^{\mathrm{TD}}(\mathbb{G}_v(\vec{X}))) = \mathbb{G}_v(A_{\vec{F},1}, \dots, A_{\vec{F},k}). \qquad (14) $$

Moreover, the exponential generating series satisfies:

$$ T_{\vec{X}=\vec{x}}(e^{\mathrm{TD}}(\mathbb{G}_v(\vec{X}))) (t) = \mathbb{G}_v(A_{\vec{F},1}(t), \dots, A_{\vec{F},k}(t)). \qquad (15) $$

We also note that the operator $e^{\mathrm{TD}} = \sum_{n \ge 0} \frac{(\mathrm{TD})^n}{n!}$, called the multiple eclosion operator associated with $\mathcal{D}$ by G. Labelle ([12]), satisfies, for any species $\mathbb{G}_1$ and $\mathbb{G}_2$:

$$ e^{\mathrm{TD}}(\mathbb{G}_1\mathbb{G}_2) = e^{\mathrm{TD}}(\mathbb{G}_1)e^{\mathrm{TD}}(\mathbb{G}_2) \qquad (16) $$

# 4 Leroux-Viennot's methods v.s. Chen's grammar

According to Chen in [5], a context-free grammar $G$ over an alphabet $A$ is defined as a set of substitution rules replacing a letter in $A$ by a formal function over $A$. Here, a Chen's grammar is an function $G: A \to \mathbb{Z}[[A]]$: it allows replacing a letter $x \in A$ with its image $G(x)$. To the grammar $G$ one can associate the differential operator $\mathcal{G} = \sum_{x \in A} G(x) \frac{\partial}{\partial x}$ defined on $\mathbb{Z}[[A]]$, satisfying for all $x \in A$, $\mathcal{G}(x) = G(x)$ and for all $u, v \in \mathbb{Z}[[A]]$, $\mathcal{G}(u + v) = \mathcal{G}(u) + \mathcal{G}(v)$ and $\mathcal{G}(uv) = \mathcal{G}(u)v + u\mathcal{G}(v)$. More generally it satisfies the Leibnitz rule: $\mathcal{G}^n(uv) = \sum_{k=0}^{n} \binom{n}{k} \mathcal{G}^k(u)\mathcal{G}^{n-k}(v)$.

We are interested in the generating series $\mathcal{G}(u, t) = \sum_{n \ge 0} \mathcal{G}^n(u) \frac{t^n}{n!}$, with $\mathcal{G}^0(u) = u$, for $u \in \mathbb{Z}[[A]]$. It verifies, for all $u, v \in \mathbb{R}[[A]]$, $\mathcal{G}(u + v, t) = \mathcal{G}(u, t) + \mathcal{G}(v, t)$ et $\mathcal{G}(uv, t) = \mathcal{G}(u, t)\mathcal{G}(v, t)$.

In this article, a grammar is an a map $G: A \to \mathbb{Z}[[A]]$ that allows replacing a variable $x_i$ with its image $G(x_i)$. We assume that $G(x_i) = f_i(x_1, \dots, x_n)$ is the generating series of a asymmetric $\mathbb{B}$-species $\mathbb{F}_i(X_1, \dots, X_n)$, $1 \le i \le n$. In this case, we can associate to a grammar $G$:
1. a combinatorial differential operator:

$$ \mathcal{G} = \sum_{i=1}^{n} \mathbb{F}_i(X_1, \dots, X_n) \frac{\partial}{\partial X_i} \qquad (17) $$

2. a combinatorial system of differential equations:

$$ \{Y'_{i} = \mathbb{F}_{i}(Y_{1}, \dots, Y_{n}), Y_{i}(0) = X_{i}, 1 \le i \le n\} \qquad (18) $$

3. An analytical system of differential equations

$$ \{Y'_{i}(t) = \mathbb{F}_{i}(Y_{1}(t), \dots, Y_{n}(t)), Y_{i}(0) = x_{i}, 1 \le i \le n\} \qquad (19) $$

It was shown in [22] (see also [23]) that the solution of combinatorial system of differential equations (18) is the n-tuple $\vec{A}_{\vec{F}} = ((A_{\vec{F},i})_{i \in [n]})$, of mixed species of $\vec{F}$-enriched rooted trees, where $A_{\vec{F},i} = e^{\mathcal{G}}(X_i)$. And the generating series of the isomorphism types $A_{\vec{F},i} = T_{\vec{X}=\vec{x}}(A_{\vec{F},i})(1 \le i \le n)$, of these solutions are the solutions of the analytical system of differential equations (19), and verify:

$$ A_{\vec{F},i}(t) = \mathcal{G}(x_i, t) = \sum_{n \ge 0} \mathcal{G}^n(x_i) \frac{t^n}{n!} \qquad (20) $$

$\vec{A}_{\vec{F}} = \{A_{\vec{F},i}, 1 \le i \le k\}$ is called the family of L-species associated with the grammar G.

**Example 3** The grammar associated with the differential equation of the example 1 is the grammar $G = \{x \to x^{n+1}\}$. And the grammar associated with the system of differential equations of the example 2 is the grammar $H = \{z \to zx, x \to x\}$. By solving the system $\{z'(t) = z(t)x(t), x'(t) = x(t), z(0) = z, x(0) = x\}$, we obtain the exponential generating functions of the isomorphism type U and V, of the solution.

$$ U(t) = z(t) = \sum_{n \ge 0} \mathcal{H}^n(z) \frac{t^n}{n!} = ze^{x(e^{t}-1)} \quad \text{and} \quad V(t) = x(t) = \sum_{n \ge 0} \mathcal{H}^n(x) \frac{t^n}{n!} = xe^t $$

# 5 Composition of grammar vs. composition of L-species

In the following, the combinatorial differential operator and the analytical differential operator associated to the grammar G will be denoted by the same letter G. Furthermore, we will only consider asymmetric B-species.

Let H and K be two grammars on two disjoint alphabets A and B, whose associated differential operators are H and K, and $g \in \mathbb{Z}[[B]]$. Let $Hg$ denote the grammar on $A \cup B$ obtained by replacing each rule $u \to v$ of H by $u \to vg$. According to Chen (see [5], definition 3.6), the grammar $H_{K,g}^* = HK(g) \cup K$ on $A \cup B$ is called the composition of H and K in g. Proposition 3.7 of [5] say that for all $f \in \mathbb{Z}[[A]]$, $H_{K,g}^*(f,t) = H(f, K^+(g,t))$, where $H_{K,g}^*$ is the differential operator associated with the grammar $H_{K,g}^*$, and $K^+(g,t) = \sum_{n \ge 1} K^n(g) \frac{t^n}{n!}$.

We modify Chen's definition as follows:

**Definition 2** The grammar $H_{K,g} = Hg \cup K$ is called the composition of H and K in g.
Let {$\mathbb{H}_i(Z_1, \dots, Z_k), i \in [k]$}, {$\mathbb{K}_j(X_1, \dots, X_l), j \in [l]$} and $\mathbb{G} = G(X_1, \dots, X_l)$ be an asymmetric $\mathbb{B}$-species whose exponential generating series are $h_i = \mathbb{H}_i(\vec{z})$, $k_j = \mathbb{K}_j(\vec{x})$ and $g = \mathbb{G}(\vec{x})$. Consider the grammars $H = \{z_i \to h_i, i \in [k]\}$, $K = \{x_j \to k_j, j \in [l]\}$ and $H_{K,g} = Hg \cup K$. We aim to study the solutions $\vec{\mathcal{A}} = \{e^{\mathcal{H}_{K,g}}(Z_i), e^{\mathcal{H}_{K,g}}(X_j), i \in [k], j \in [l]\}$ of the system of combinatorial differential equations associated with $H_{K,g}$. We define $A_{\vec{\mathbb{H}},i} = e^{\mathcal{H}}(Z_i)$, $A_{\vec{\mathbb{K}},j} = e^{\mathcal{K}}(X_j)$, $\vec{\mathcal{A}}_{\vec{\mathbb{H}}} = ((A_{\vec{\mathbb{H}},i})_{i \in [k]})$ et $\vec{\mathcal{A}}_{\vec{\mathbb{K}}} = ((A_{\vec{\mathbb{K}},j})_{j \in [l]})$. We have the following fundamental theorem:

**Theorem 4** For $1 \le i \le k$ and $1 \le j \le l$, we have:

$$e^{\mathcal{H}_{K,g}}(Z_i) = A_{\vec{\mathbb{H}},i} \circ \int \mathbb{G}(A_{\vec{\mathbb{K}},1}, \dots, A_{\vec{\mathbb{K}},l}), \qquad (21)$$

$$e^{\mathcal{H}_{K,g}}(X_j) = A_{\vec{\mathbb{K}},j}. \qquad (22)$$

More generally, for any $\mathbb{B}$-species $\mathbb{F} = \mathbb{F}_1(\vec{Z})\mathbb{F}_2(\vec{X})$, we have:

$$e^{\mathcal{H}_{K,g}}(\mathbb{F}) = \left[ (\mathbb{F}_1 \circ \vec{\mathcal{A}}_{\vec{\mathbb{H}}}) \circ (\int \mathbb{G}(\vec{\mathcal{A}}_{\vec{\mathbb{K}}})) \right] \cdot \left[ \mathbb{F}_2 \circ \vec{\mathcal{A}}_{\vec{\mathbb{K}}} \right]. \qquad (23)$$

with $\mathbb{F}_1 \circ \vec{\mathcal{A}}_{\vec{\mathbb{H}}} = \mathbb{F}_1(A_{\vec{\mathbb{H}},1}, \dots, A_{\vec{\mathbb{H}},k}) = e^{\mathcal{H}}(\mathbb{F}_1)$ and $\mathbb{F}_2 \circ \vec{\mathcal{A}}_{\vec{\mathbb{K}}} = \mathbb{F}_2(A_{\vec{\mathbb{K}},1}, \dots, A_{\vec{\mathbb{K}},l}) = e^{\mathcal{K}}(\mathbb{F}_2)$.

*Proof:* : For $1 \le i \le k$ and $n = 1$, $\mathcal{TH}_{K,g}(Z_i) = \mathcal{TH}_i(\vec{Z})\mathbb{G}(\vec{X})$. A generic $\mathcal{TH}_{K,g}(Z_i)$-structure is given in Figure 6. For $n \ge 2$, we obtain a $\frac{(\mathcal{TH}_{K,g})^{n}(Z_i)}{n!}$-structure by applying

<figure><img src="image_8.png" /><figcaption>Figure 6: An generic $(\mathcal{TH}_{K,g})(Z_i)$-structure</figcaption></figure>

the operator $(\mathcal{TH}_{K,g})$ to a $\frac{(\mathcal{TH}_{K,g})^{n-1}(Z_i)}{(n-1)!}$-structure, i.e., either by replacing a point $Z_s$ ($1 \le s \le k$) with a point $T$ labeled by $n$ followed by an $\mathbb{H}_s(\vec{Z})\mathbb{G}(\vec{X})$-structure, or by replacing a point $X_j$ with a point $T$ labeled by $n$ followed by a $\mathbb{K}_j(\vec{X})$-structure. The figure 7(A), in which each $A_K$, is a $A_{\vec{\mathbb{K}},j}$-structure represents a generic $e^{\mathcal{H}_{K,g}}$-structure. Its structure can be identified with the structure in Figure 7(B), which represents a $A_{\mathbb{H}_i} \circ \int \mathbb{G}(A_{\vec{\mathbb{K}},1}, \dots, A_{\vec{\mathbb{K}},l})$-structure. Indeed, figure 8 shows that it can be decomposed into a pair $(s_1, s_2)$, where $s_1$ is an $A_{\mathbb{H}_i}$-structure and $s_2$ is an $\mathbb{E} \circ \int \mathbb{G}(A_{\vec{\mathbb{K}},1}, \dots, A_{\vec{\mathbb{K}},l})$-structure. Using Lemma 1, we obtain the result.

The equation (22) is obvious. Since $e^{\mathcal{H}_{K,g}}(\mathbb{F}) = e^{\mathcal{H}_{K,g}}(\mathbb{F}_1)e^{\mathcal{H}_{K,g}}(\mathbb{F}_2)$, using (10) we obtain (23). ◇

Corollary 3 prove that:
<figure><img src="image_9.png" /><figcaption>Figure 7: A generic $(e^{TH_{K,g}}(Z_i)$-structure</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 8: Decomposition of a $e^{TH_{K,g}}(Z_i)$-structure</figcaption></figure>

**Corollary 5** The L-species of types $\mathbb{H}_{K,g,z_i} = T_{\vec{Z}=\vec{z}, \vec{X}=\vec{x}} e^{TH_{K,g}}(Z_i)$,
$\mathbb{H}_{K,g,x_j} = T_{\vec{Z}=\vec{z}, \vec{X}=\vec{x}} e^{TH_{K,g}}(X_j)$ and $\mathbb{H}_{K,g}(\mathbb{F}) = T_{\vec{Z}=\vec{z}, \vec{X}=\vec{x}} e^{TH_{K,g}}(\mathbb{F})$ satisfy:

$$ \mathbb{H}_{K,g,z_i} = A_{\vec{H},i} \circ \left( \int \mathbb{G}(\vec{A}_{\vec{K}}) \right), \quad \mathbb{H}_{K,g,x_j} = A_{\vec{K},j}. \qquad (24) $$

and

$$ \mathbb{H}_{K,g}(\mathbb{F}) = \left[ (\mathbb{F}_1 \circ \vec{A}_{\vec{H}}) \circ \left( \int \mathbb{G}(\vec{A}_{\vec{K}}) \right) \right] \cdot \left[ \mathbb{F}_2 \circ \vec{A}_{\vec{K}} \right]. \qquad (25) $$

where $A_{\vec{H},i} = T_{\vec{Z}=\vec{z}, \vec{X}=\vec{x}} e^{TH}(Z_i)$, $A_{\vec{K},j} = T_{\vec{X}=\vec{x}} e^{TK}(X_j)$, $\vec{A}_{\vec{K}} = (\vec{A}_{\vec{K},1}, \dots, \vec{A}_{\vec{K},l})$ and $\vec{A}_{\vec{H}} = (\vec{A}_{\vec{H},1}, \dots, \vec{A}_{\vec{H},k})$.

**Corollary 6** For any B-species $\mathbb{F} = \mathbb{F}_1(\vec{Z})\mathbb{F}_2(\vec{X})$, we have:

$$ e^{TH_{K,g}^*}(\mathbb{F}) = \left[ (\mathbb{F}_1 \circ \vec{A}_{\vec{H}}) \circ (\mathbb{G}(\vec{A}_{\vec{K}}))^+ \right] \cdot \left[ \mathbb{F}_2 \circ \vec{A}_{\vec{K}} \right]. \qquad (26) $$

The L-specie of type verify:

$$ \mathbb{H}_{K,g}^*(\mathbb{F}) = \left[ (\mathbb{F}_1 \circ \vec{A}_{\vec{H}}) \circ (\mathbb{G}(\vec{A}_{\vec{K}}))^+ \right] \cdot \left[ \mathbb{F}_2 \circ \vec{A}_{\vec{K}} \right] \qquad (27) $$
**Proof:** It suffices to show that $\int \mathbb{G}(\vec{\mathcal{A}}_{\vec{\mathbb{K}}}) = (\mathbb{G}(\vec{\mathcal{A}}_{\vec{\mathbb{K}}}))^+$. We have $\mathbb{G}(\vec{\mathcal{A}}_{\vec{\mathbb{K}}}) = e^{TK}(\mathcal{K}(\mathbb{G})) = \sum_{n \ge 0} \frac{(TK)^n}{n!} (\mathcal{K}(\mathbb{G})).$ That is $\int \mathbb{G}(\vec{\mathcal{A}}_{\vec{\mathbb{K}}}) = \int \mathcal{K}(\mathbb{G}) + \sum_{n \ge 1} \int \frac{(TK)^n}{n!} \mathcal{K}(\mathbb{G})$. Figure 9(A) represents a $\int \mathcal{K}(\mathbb{G})$-structure on [1]. It can be identified as a $\mathbb{G}(X_1, \dots, T\mathbb{K}_j, \dots, X_l)$-

<figure><img src="image_11.png" /><figcaption>Figure 9: (A) An $\int \mathcal{K}(\mathbb{G})$-structure; (C) An $e^{TK}(\mathcal{K}(\mathbb{G}))$-structure</figcaption></figure>

structure on [1], as illustrated on figure 9(A'). By iterating, we obtain a $\mathbb{G}(A_{\mathbb{K},1}, \dots, A_{\mathbb{K},l})$-structure, as shown in Figure 9(C). It is an $e^{TK}(\mathbb{G})$-structure on a non-empty set. Hence we have $\int e^{TK}(\mathcal{K}(\mathbb{G})) = e^{TK}(\mathbb{G})^+$. ◇

**Theorem 7** If the exponential generating series of $\mathbb{F} = \mathbb{F}_1(\vec{z})\mathbb{F}_2(\vec{x})$ is $f = \mathbb{F}(\vec{z}), \vec{x}) = \mathbb{F}_1(\vec{z})\mathbb{F}_2(\vec{x}) = f_1f_2$, then the exponential generating series of $T_{\{\vec{z}=\vec{z}, \vec{x}=\vec{x}\}}e^{TH_{K,g}}(\mathbb{F})$ satisfies:

$$ \mathcal{H}_{K,g}(f,t) = \mathcal{H}(f_1, \int_0^t \mathcal{K}(g, u)du) \cdot \mathcal{K}(f_2, t) \quad (28) $$

In the same way, the generating series of $T_{\{\vec{z}=\vec{z}, \vec{x}=\vec{x}\}}e^{TH_{K,g}^*}(\mathbb{F})$ satisfies:

$$ \mathcal{H}_{K,g}^*(f,t) = \mathcal{H}(f_1, \mathcal{K}^+(g,t)) \cdot \mathcal{K}(f_2,t) \quad (29) $$

**Proof:** Knowing that composition and integration of $\mathbb{L}$-species are compatible with the transition to exponential generating series, equations 25 and 29 give us results. ◇

Note that Chen's result on composition of grammars is an immediate consequence of (29).

**Notation:** Let $H = \{z \to h(z, \vec{x}), x_j \to k_j(\vec{x}), j \in [l]\}$ a grammar and $\mathbb{F}(X_1, \dots, X_l)$ a species, we set $\mathbb{H} = T_{\{Z=z, \vec{X}=\vec{x}\}}e^{\mathbb{H}}(Z)$ and $\mathbb{H}(z\mathbb{F}) = T_{\{Z=z, \vec{X}=\vec{x}\}}\mathcal{H}(Z\mathbb{F})$.

**Example 4** The grammar $H_{K,g} = \{z \to zx, x \to x\}$ is the composition of the grammars $H = \{z \to z\}$ with $K = \{x \to x\}$ in $g(x) = x$. Since $e^{\mathbb{H}}(Z) = Z\mathbb{E}(T)$ and $e^{TK}(X) = X\mathbb{E}(T)$, we have $e^{TH_{K,g}}(Z) = Z\mathbb{E} \circ (X \int \mathbb{E}(T))$. Thus:

$$ \mathbb{H}_{K,g} = z\mathbb{E} \circ (x\mathbb{E}^+) = \mathrm{Par}_{\omega}, \quad (30) $$

where $\mathrm{Par}_{\omega}$ is the $\mathbb{L}$-species of partitions weighted by $\omega(\pi) = zx^{|\pi|}$ (example 2), whose exponential generating series is $\mathrm{Par}_{\omega}(t) = ze^{x(e^{t-1})}$ (example 3). So $\mathcal{H}_{K,g}^n(z) = z \sum_{k=1}^n S(n, k)x^k$, where $S(n, k)$ are the Stirling numbers of the second kind, A008277 in OEIS [9]. The relation $\mathcal{H}_{K,g}^{n+1}(z) = \mathcal{H}_{K,g}(\mathcal{H}_{K,g}^n(z))$ is equivalent to the classic relation:

$$ S(n+1, k) = S(n, k-1) + kS(n, k). \quad (31) $$
Let $\mathbb{F}(Z, X) = ZX^r$. We have $e^{\mathbb{H}_{K,g}}(\mathbb{F}) = (Z\mathbb{E} \circ (X \int \mathbb{E})) \cdot (X\mathbb{E})^r$. The $\mathbb{L}$-species of types verify:

$$T_{Z=z, X=x} e^{\mathbb{H}_{K,g}}(\mathbb{F}) = \mathbb{H}_{K,g}(\mathbb{F}) = \mathrm{Par}_{\omega} \cdot (x\mathbb{E})^r. \quad (32)$$

A $\mathbb{H}_{K,g}(\mathbb{F})$-structure on $[n]$ is then a pair $(s_1, s_2)$ where $s_1$ is a partition of a subset $A$ of $[n]$ and $s_2$ a $(x\mathbb{E})^r$-structure on $[n] \setminus A$. Its weight is $zx^{k+r}$ if $s_1$ has $k$ blocks. By setting $\mathcal{H}_{K,g}^n(zx^r) = \sum_{k=1}^n S_r(n, r)zx^{k+r}$, we have the recurrence relation:

$$S_r(n+1, k) = S_r(n, k-1) + (k+r)S_r(n, k) \quad (33)$$

with $S_r(0, 0) = 1$, $S_r(n, k) = 0$ if $k \le 0$ or $n < k$. This provides a generalization of Stirling numbers of the second kind, generalization that was studied by A. Broder in [3] and R. Merris in [18]. Knowing that an $\mathbb{E}^r$-structure on $[k]$ can be identified with a map from $[k]$ to $[r]$, the equation (32) shows that:

$$S_r(n, k) = \sum_{j=k}^{n} \binom{n}{j} r^{n-j} S(j, k), \quad (34)$$

and the exponential generating series is $\mathbb{H}_{K,g}(t) = zx^r e^{x(e^{r-1})} e^{rt}$.

**Example 5** The grammar $H_{K,g} = \{z \to \mu zx, x \to x^2\}$, where $\mu$ is a variable that will used as a counter of connected components, is the composition of the grammars $H = \{z \to \mu z\}$ and $K = \{x \to x^2\}$ in $g(x) = x$. Since $e^{\mathbb{H}}(Z) = Z\mathbb{E}_{\beta}(T)$, where $\mathbb{E}_{\beta}$ is the species of sets weighted by $\beta(A) = \mu^{|A|}$, and $e^{\mathbb{K}}(X)$ is the mixed species $A_2(T, X)$ of complete binary trees increasing in $T$ and whose leaves are of type $X$, we have $e^{\mathbb{H}_{K,g}}(Z) = Z\mathbb{E}_{\beta}(\int A_2(T, X))$. Considering the isomorphism types, we have:

$$T_{\{Z=z, X=x\}} e^{\mathbb{H}_{K,g}}(Z) = \mathbb{H}_{K,g} = z\mathbb{E}_{\beta}\left(\int A_{2,\alpha}\right) = z\mathbb{S}_{\beta}, \quad (35)$$

where $\mathbb{S}_{\beta}$ is the species of permutations decomposed into cycles, weighted by $\beta(\sigma) = \mu^k x^n$ if $\sigma \in S_n$, and $\sigma$ contains $k$ cycles. The generating serie is:

$$\mathbb{H}_{K,g}(t) = z(1 - xt)^{-\mu}.$$

We have $\mathcal{H}_{K,g}^n(z) = z \sum_{k=1}^n c(n, k)\mu^k x^n$, where $c(n, k)$ is the number of permutations of $S_n$ having $k$ cycles, or unsigned Stirling numbers of the first kind (A008275 in O.I.E.S. [9]). Writing $\mathcal{H}_{K,g}^{n+1}(z) = \mathcal{H}_{K,g}(\mathcal{H}_{K,g}^n(z))$, we obtain the classic identity:

$$c(n+1, k) = c(n, k-1) + nc(n, k). \quad (36)$$

Taking $\mathbb{F} = ZX^r$, we have $e^{\mathbb{H}_{K,g}}(\mathbb{F}) = (Z\mathbb{E} \circ (\int A_2(T, X))) \cdot (A_2(T, X))^r$. Therefore:

$$\mathbb{H}_{K,g}(\mathbb{F}) = z\mathbb{S}_{\beta} \cdot (\mathbb{S}_{\alpha})^r. \quad (37)$$

An $\mathbb{H}_{K,g}(\mathbb{F})$-structure on $[n]$ is a pair $(s_1, s_2)$ where $s_1 \in \mathbb{S}_{\beta}[A]$ and $s_2 \in (\mathbb{S}_{\alpha})^r([n] \setminus A)$, with $A \subset [n]$. Its weight is $z\mu^k x^{n+r}$ if $s_1$ has $k$ cycles. Setting $\mathcal{H}_{K,g}^n(zx^r) = \sum_{k=1}^n c_r(n, k)z\mu^k x^{n+r}$, we have the recurrence relation:

$$c_r(n+1, k) = c_r(n, k-1) + (n+r)c_r(n, k) \quad (38)$$

with $c_r(0, 0) = 1$, $c_r(n, k) = 0$ if $k < 0$ or $n < k$. We obtain a generalization of the unsigned Stirling numbers of the first kind, studied by R. Merris in [18].
We have $\mathcal{K}^n(x^r) = r(r+1)\cdots(r+n-1)x^{r+n}$. Since the number of $(\mathbb{S}_\alpha)^r$-structures on $[n]$ is $r(r+1)\cdots(r+n-1)$. Using (37), we have:

$$c_r(n, k) = \sum_{j=k}^{n} \binom{n}{j} r(r+1)\cdots(r+n-j-1)c(j, k). \qquad (39)$$

Moreover, the generating series is

$$\mathbb{H}_{K,g}(\mathbb{F})(t) = \frac{zx^r}{(1-xt)^{r+\mu}}.$$

**Example 6** Let's consider the grammar $H_{K,g} = \{z \to z^2x, x \to x\}$, composed of the grammars $H = \{z \to z^2\}$ and $K = \{x \to x\}$ in $g(x) = x$. Since $e^{TH}(Z) = A_2(T, Z)$ and $e^{TK}(X) = X\mathbb{E}(T)$, we have:

$$\mathbb{H}_{k,g} = \mathbb{L}_{\alpha} \circ (x\mathbb{E}^{+}). \qquad (40)$$

A $\mathbb{H}_{k,g}$-structure on $[n]$ can be identified as a pair $s = (s_1, s_2)$, where $s_1$ is a list on $[k]$ whose weight is $\alpha(s_1) = z^{k+1}$ and $s_2$ is a partition of $[n]$ into $k$ blocks whose weight is $x^k$. $s$ can be also identified as a surjection from $[n]$ to $[k]$ if $s_2$ has $k$ blocks. Thus, $\mathbb{H}_{k,g}$ is the $\mathbb{L}$-species of lists of non-empty sets weighted by $\beta(s) = z^{b(s_2)+1}x^{b(s_2)}$, where $b(s_2)$ is the number of blocks of $s_2$. Since, we have $\mathcal{H}_{K,g}^n(z) = \sum_{k=1}^n \sigma(n,k)z^{k+1}x^k$ where $\sigma(n,k) = k!S(n,k)$ is the number of surjection from $[n]$ to $[k]$ (A019538 in O.E.I.S. [9]). Furthermore, the relation $\mathcal{H}_{K,g}^{n+1}(z) = \mathcal{H}_{K,g}(\mathcal{H}_{K,g}^n(z))$ can be translated as:

$$\sigma(n+1, k) = k(\sigma(n, k-1) + \sigma(n, k)), \qquad (41)$$

and the exponential generating series is

$$\mathbb{H}_{k,g}(t) = \frac{z}{1-zx(e^t - 1)}.$$

Let $\mathbb{F}(Z, X) = ZX^r$. We have:

$$\mathbb{H}_{K,g}(\mathbb{F}) = (\mathbb{L}_{\alpha} \circ (x\mathbb{E}^{+})) \cdot (x\mathbb{E})^r \qquad (42)$$

A $\mathbb{H}_{K,g}(\mathbb{F})$-structure on $[n]$ is a couple $s = (s_1, s_2)$ so that $s_1$ is a $\mathbb{H}_{K,g}$-structure on $A \subset [n]$, and $s_2$ a $(x\mathbb{E})^r$-structure on $[n] \setminus A$. If $s_1$ has $k$ blocks, then the weight of $s$ is $z^{k+1}x^{k+r}$. Let $\mathcal{H}_{K,g}^n(zx^r) = \sum_{k=1}^n \sigma_r(n,k)z^{k+1}x^{k+r}$. We have the recurrence relation:

$$\sigma_r(n+1, k) = k\sigma_r(n, k-1) + (k+r)\sigma_r(n, k) \qquad (43)$$

$$c_r(0, 0) = 1, c_r(n, k) = 0 \text{ if } k < 0 \text{ or } n < k.$$

Moreover, equation (42) shows that:

$$\sigma_r(n, k) = k! \sum_{j=k}^{n} \binom{n}{j} r^{n-j} S(j, k), \qquad (44)$$

and the generating series is

$$\mathbb{K}_{H,g}(\mathbb{F})(t) = \frac{zx^r e^{rt}}{1-zx(e^t - 1)}.$$

Note that the $\mathbb{B}$-specie $\mathbb{L} \circ (\mathbb{E}^+)$ of finite sequences of sets, or specie of ordered partitions, was studied by J.B. Priez in [21], in connection with generalized parking functions.
**Example 7** Let's revisit the grammars $H = \{z \to \mu z\}$ and $K = \{x \to x^2\}$ from Example 5. The grammar $H_{K,g}^* = \{z \to \mu z x^2, x \to x^2\}$ is the composition of $H$ and $K$ on $\mathcal{K}(g)$, where $g(x) = x$. Thus, $e^{TK}(Z) = A_2(T, Z)$ et $e^{TH}(X) = X\mathbb{E}(T)$. Therefore:

$$ \mathbb{H}_{K,g}^* = z\mathbb{E}_{\beta} \circ \mathbb{A}_{2,\alpha}^+ = z\mathbb{E}_{\beta} \circ \mathbb{L}_{\alpha}^+. \qquad (45) $$

Thus, $\mathbb{H}_{K,g}^*$ is the species of sets of lists, weighted by $\mu(s) = z\mu^k x^{n+k}$, if $s$ has $k$ connected components. The generating series is

$$ \mathbb{H}_{K,g}^*(t) = z \exp\left(\mu \frac{xt}{1-xt}\right). $$

Setting $(\mathbb{H}_{K,g}^*)^n(z) = z \sum_{k=1}^n L(n,k)\mu^k x^{n+k}$, we have:

$$ L(n+1, k) = L(n, k-1) + (n+k)L(n, k) \qquad (46) $$

The numbers $L(n,k)$ are the (unsigned) Lah-numbers, defined by Ivo Lah in [13](A008297 in O.E.I.S. [9]), and (45) is its classical combinatorial interpretation (See, for example, [20]).

Let $\mathbb{F} = ZX^r$. We have:

$$ \mathbb{H}_{K,g}^*(\mathbb{F}) = (\mathbb{E}_{\beta} \circ \mathbb{L}_{\alpha}^+) \cdot (\mathbb{S}_{\alpha})^r \qquad (47) $$

and the generating series is

$$ \mathbb{H}_{K,g}^*(\mathbb{F})(t) = z \exp\left(\frac{\mu x t}{1-x t}\right) \frac{x^r}{(1-x t)^r}. $$

An $\mathbb{H}_{K,g}^*(\mathbb{F})$-structure on $[n]$ is a pair $(s_1, s_2)$ where $s_1 \in \mathbb{H}_{K,g}[A]$ and $s_2 \in (\mathbb{S}_{\alpha})^r[n] \setminus A$, weighted by $z\mu^k x^{n+k+r}$ si $s_1$ has $k$ connected components. Setting $(\mathbb{H}_{K,g}^*)^n(zx^r) = z \sum_{k=0}^n L_r(n,k)\mu^k x^{n+k+r}$, we have:

$$ L_r(n+1, k) = L_r(n, k-1) + (n+k+r)L_r(n, k), \qquad (48) $$

with $L_r(0,0) = 1$, $L_r(n,k) = 0$ if $k < 0$ or $n > k$, Equation (47) show that:

$$ L_r(n, k) = \sum_{j=k}^{n} \binom{n}{j} r(r+1) \cdots (r+n-j) L(j, k). \qquad (49) $$

We have also:

$$ (x+r)^{(n)} = \sum_{k=0}^{n} L_r(n,k) x_{(k)}, \qquad (50) $$

where $x^{(n)} = x(x+1)\cdots(x+n-1)$ and $x_{(k)} = x(x-1)\cdots(x-k+1)$.

The numbers $L_{2r}(n,k)$, called $r$-Lah numbers, was studied by G. Nyul and G. Rácz in [19] and by M Shattuck in [24]).
# 6 Grammars of types (E) and associated Matrices

Let $\vec{x} = (x_1, \dots, x_k)$ be a family of formal variables, $\{h_i(\vec{x}), 1 \le i \le k\}$ and $g(\vec{x})$ the exponential generating series of a family of asymmetric B-species $\{H_i(\vec{X}), 1 \le i \le k\}$ and of $\mathbb{G}(\vec{X})$.

**Definition 3** We call a grammar of type (E) any grammar of the form: $H_g = \{z \to zg(\vec{x}), x_i \to h_i(\vec{x}), 1 \le i \le k\}$, which is the composition of $H = \{z \to z\}$ with $K = \{x_i \to h_i(\vec{x})\}$ in $g(\vec{x})$.

Theorem 4 shows that $e^{TH_g}(Z) = Z\mathbb{E} \circ \int \mathbb{G}(A_{\vec{K},1}, \dots, A_{\vec{K},k})$ where $A_{\vec{K},i} = e^{TK}(X_i)$. Since:

$$ \mathbb{H}_g = T_{Z=z, \vec{X}=\vec{x}} e^{TH_g}(Z) = z\mathbb{E} \circ \int \mathbb{G}(A_{\vec{K},1}, \dots, A_{\vec{K},k}) \quad (51) $$

According to definition 1, the matrix of $\mathbb{H}_g$ will be denoted as $M_H$.

Let $\mathbb{F} = \mathbb{F}(\vec{X})$ a B-species. We have $\mathbb{H}_g(z\mathbb{F}) = T_{Z=z, \vec{X}=\vec{x}} e^{TH_g}(z\mathbb{F}) = \mathbb{H}_g \cdot \mathbb{K}(\mathbb{F})$. An element of $\mathbb{H}_g(z\mathbb{F})$ is a couple $s = (s_1, s_2)$, where $s_1 \in \mathbb{H}_g[A]$ and $s_2 \in \mathbb{K}(\mathbb{F})[[n] \setminus A]$.

**Definition 4** The matrix $M_{H(z\mathbb{F})} = (a_{\mathbb{F}}(n,k))_{n,k}$ where $a_{\mathbb{F}}(n,k)$ is the number of structures $s = (s_1, s_2) \in \mathbb{H}_g(z\mathbb{F})[n]$ such that $s_1$ has $k$ connected components is called the matrix of $\mathbb{H}_g(z\mathbb{F})$.

Let $H_g = \{z \to zg(\vec{x}), x_i \to h_i(\vec{x}), 1 \le i \le k\}$ and $K_{g_1} = \{v \to v g_1(\vec{u}), u_j \to k_j(\vec{u}), 1 \le j \le l\}$ be two grammars of type (E). The grammar $P_{\bar{g}} = \{v \to v g_1(\vec{u}) g(\vec{x}), u_j \to k_j(\vec{u}) g(\vec{x}), x_i \to h_i(\vec{x}), 1 \le i \le k, 1 \le j \le l\}$ is of type (E): it is the composition of $H_1 = \{v \to v\}$ with $K_1 = \{u_j \to k_j(\vec{u}) g(\vec{x}), x_i \to h_i(\vec{x}), 1 \le i \le k, 1 \le j \le l\}$ in $\bar{g}(\vec{u}, \vec{x}) = g_1(\vec{u}) g(\vec{x})$.

We have $\mathbb{H}_g = z\mathbb{E} \circ (\int \mathbb{G}(T_{\vec{X}=\vec{x}} \vec{A} \vec{H}))$, $K_{g_1} = v\mathbb{E} \circ (\int \mathbb{G}_1(T_{\vec{U}=\vec{u}} \vec{A} \vec{K}))$, and $P_{\bar{g}} = v\mathbb{E} \circ (\int \mathbb{G}_1(T_{\vec{U}=\vec{u}} \vec{A} \vec{K}) \circ \int \mathbb{G}(T_{\vec{X}=\vec{x}} \vec{A} \vec{H}))$. Figure 10 represents a generic $P_{\bar{g}}$-structure on $[n]$, with $n \ge 17$, having 3 connected components.

<figure><img src="image_12.png" /><figcaption>Figure 10: A generic $P_{\bar{g}}$-structure</figcaption></figure>

**Theorem 8** Let $M_H = (a(n,k))_{n,k \in \mathbb{N}}$, $N_K = (b(n,k))_{n,k \in \mathbb{N}}$ and $\Lambda_P = (\lambda(n,k))_{n,k \in \mathbb{N}}$ be the respective matrices of $\mathbb{H}_g$, $K_{g_1}$ and $P_{\bar{g}}$. Then,

$$ \Lambda_P = M_H N_K \quad (52) $$
More generally, if $\mathbb{F} = \mathbb{F}_1(X)\mathbb{F}_2(U)$ is a $\mathbb{B}$-species, and $\Lambda_{\mathbb{F}} = (\lambda_{\mathbb{F}}(n, k))$, $\Lambda_{\mathbb{F}_1} = (\lambda_{\mathbb{F}_1}(n, k))$ and $\Lambda_{\mathbb{F}_2} = (\lambda_{\mathbb{F}_2}(n, k))$ are the respective matrices of $\mathbb{P}_{\bar{\mathbb{F}}}(v\mathbb{F})$, $\mathbb{H}_g(z\mathbb{F}_1)$, and $\mathbb{K}_{g_1}(v\mathbb{F}_2)$, then

$$ \Lambda_{\mathbb{F}} = \Lambda_{\mathbb{F}_1} \Lambda_{\mathbb{F}_2} \qquad (53) $$

*Proof:* As shown in Figure 11, which is a decomposition of the $\mathbb{P}_{\bar{\mathbb{F}}}$-structure in Figure 10, any $\mathbb{P}_{\bar{\mathbb{F}}}$-structure on $[n]$ with $k$ connected components can be identified with a pair $(s_1, s_2)$, where $s_1 \in \mathbb{K}_{g_1}[i]$, $s_1$ has $k$ connected components and $s_2 \in \mathbb{H}_g[n]$, $s_2$ having $i$ connected components, so that $\lambda(n, k) = \sum_i a(n, i)b(i, k)$.

<figure><img src="image_13.png" /><figcaption>Figure 11: Decomposition of an $\mathbb{P}_{\bar{\mathbb{F}}}$-structure</figcaption></figure>

In the other hand, we have $e^{\mathbb{P}_{\bar{\mathbb{F}}}}(v\mathbb{F}) = e^{\mathbb{P}_{\bar{\mathbb{F}}}}(V)e^{\mathbb{P}_{\bar{\mathbb{F}}}}(\mathbb{F}_2)e^{\mathbb{H}_g}(\mathbb{F}_1)$. Thus:

$$ \mathbb{P}_{\bar{\mathbb{F}}}(v\mathbb{F}) = \mathbb{P}_{\bar{\mathbb{F}}} \cdot \mathbb{P}_{\bar{\mathbb{F}}}(\mathbb{F}_2) \cdot \mathbb{H}_g(\mathbb{F}_1). \qquad (54) $$

A generic $\mathbb{P}_{\bar{\mathbb{F}}}(v\mathbb{F})$-structure is given in Figure 12: it is a triplet $s = (s_1, s_2, s_3)$, where $s_1$

<figure><img src="image_14.png" /><figcaption>Figure 12: An $\mathbb{P}_{\bar{\mathbb{F}}}(v\mathbb{F})$-structure</figcaption></figure>

is a $\mathbb{P}_{\bar{\mathbb{F}}}$-structure on a subset $A$ of $[n]$, $s_2$ is a $\mathbb{P}_{\bar{\mathbb{F}}}(\mathbb{F}_2)$-structure on a subset $B$ such that $A \cap B = \emptyset$, and $s_3$ is a $\mathbb{H}_g(\mathbb{F}_1)$-structure on $[n] \setminus (A \cup B)$. Then, $s_1$ can be identified with a pair $(s_{11}, s_{12})$, where $s_{11}$ is an $\mathbb{K}_{g_1}$-structure on a subset $A_1$ of $A$, and $s_{12}$ is an $\mathbb{H}_g$-structure on $A$. Similarly, $s_2$ can be identified with a pair $(s_{21}, s_{22})$, where $s_{21}$ is a $\mathbb{K}_{g_1}$-structure on a subset $B_1$ of $B$, and $s_{22}$ is an $\mathbb{H}_g$-structure on $B$. Thus, $s_{11} \cup s_{21}$ is a $\mathbb{K}_{g_1}(v\mathbb{F}_2)$-structure on $A_1 \cup B_1$ which is identified as a $\mathbb{K}_{g_1}(v\mathbb{F}_2)$-structure on $[i]$, where $i = |A_1 \cup B_1|$. On the other hand, $s_{12} \cup s_{22} \cup s_3$ is an $\mathbb{H}_g(z\mathbb{F}_1)$-structure on $[n]$.

Therefore, $s$ can be identified with a pair $(\tilde{s}_1, \tilde{s}_2)$, where $\tilde{s}_1$ is a $\mathbb{K}_{g_1}(v\mathbb{F}_2)$-structure on $[i]$, and $\tilde{s}_2$ is an $\mathbb{H}_g(z\mathbb{F}_1)$-structure on $[n]$ whose associated $\mathbb{H}_g$-structure $s_{12} \cup s_{22}$ has $i$ connected components. Figure 13 shows a decomposition of the $\mathbb{P}_{\bar{\mathbb{F}}}(v\mathbb{F})$-structure from Figure 12. ◇
<figure><img src="image_15.png" /><figcaption>Figure 13: Decomposition of the $\mathbb{P}_{\bar{g}}(v\mathbb{F})$-structure</figcaption></figure>

**Example 8** Examples 4 and 5 show that the matrices associated with the grammars $H_g = \{z \to \mu zx, x \to x^2\}$ and $K_{g_1} = \{v \to vu, u \to u\}$ are respectively the matrices $C = (c(n,k))$ and $S = (S(n,k))$ where $c(n,k)$ is the unsigned Stirling number of the first kind and $S(n,k)$ the Stirling number of the second kind. Theorem 8 say that the matrix $\Pi = (\pi(n,k))_{n,k}$ associated with the grammar $P_{\bar{g}} = \{v \to vux, u \to ux, x \to x^2\}$ is $\Pi = CS$. It is easy to verify that:

$$ \mathbb{P}_{\bar{g}} = v\mathbb{E} \circ \left( u\mathbb{E}^{+} \circ \int \mathbb{A}_{2\alpha} \right) = v\mathbb{E} \circ \mathbb{L}_{\gamma}^{+}, \qquad (55) $$

where $\mathbb{L}_{\gamma}$ is the $\mathbb{L}$-species of lists weighted by $\gamma(\sigma) = ux^n$ if $\sigma \in \mathbb{L}[n]$. $\mathbb{P}_{\bar{g}}$ is therefore the species of sets of lists, weighted by $vu^kx^n$ if the considered $P_{\bar{g}}$-structure has $k$ connected components. The exponential generating series is

$$ \mathbb{P}_{\bar{g}}(t) = v \exp\left(\frac{u \, xt}{1 - xt}\right). $$

Setting $\mathcal{P}_{\bar{g}}^n(v) = v \sum_{k=0}^n \pi(n,k)u^kx^n$, we have $\pi(n+1,k) = \pi(n,k-1) + (n+k)\pi(n,k)$. That is $\pi(n,k) = L(n,k)$. We obtain the following well-known identity:

$$ L(n,k) = \sum_{i=k}^{n} c(n,i)S(i,k) \qquad (56) $$

Let $\mathbb{F} = \mathbb{F}_1(U)\mathbb{F}_2(X)$, with $\mathbb{F}_1(U) = U^r$ and $\mathbb{F}_2(X) = X^s$. Theorem 8 say also that the matrix $\lambda_{\mathbb{F}} = (\lambda_{r,s}(n,k))_{n,k}$ of $\mathbb{P}_{\bar{g}}(v\mathbb{F})$ verify $\lambda_{\mathbb{F}} = \lambda_{\mathbb{F}_2}\lambda_{\mathbb{F}_1}$, where $\lambda_{\mathbb{F}_2}$ and $\lambda_{\mathbb{F}_1}$ are the respective matrices of $\mathbb{H}_g(z\mathbb{F}_2)$, and $\mathbb{K}_{g_1}(v\mathbb{F}_1)$. Example 5 say that $\lambda_{\mathbb{F}_2} = (c_s(n,k))_{n,k}$, and the example 4 say that $\lambda_{\mathbb{F}_1} = (S_r(n,k))_{n,k}$. Since

$$ \lambda_{r,s}(n,k) = \sum_{i=k}^{n} c_s(n,i)S_r(i,k) \qquad (57) $$

Using equation (34) and (39), we have

$$ \lambda_{r,s}(n,k) = \sum_{k \le l \le i \le j \le n} \binom{n}{j} \binom{i}{l} s(s+1) \cdots (s+n-j) r^{i-l} c(j,i) S(l,k) \qquad (58) $$

We have also $\mathbb{P}_{\bar{g}} = v\mathbb{E} \circ \mathbb{L}_{\gamma}^{+}$, $\mathbb{P}_{\bar{g}}(\mathbb{F}_1) = (v\mathbb{E} \circ \int \mathbb{L}_{\alpha})^r = (\mathbb{L}_{\gamma})^r$ and $\mathbb{H}_g(\mathbb{F}_2) = \mathbb{A}_{2,\alpha}^s = (\mathbb{L}_{\alpha})^s$. Therefore:

$$ \mathbb{P}_{\bar{g}}(v\mathbb{F}) = (v\mathbb{E} \circ \mathbb{L}_{\gamma}^{+}) \cdot (\mathbb{L}_{\gamma})^{r} \cdot (\mathbb{L}_{\alpha})^{s}, \qquad (59) $$

and the generating series is
$$ \mathbb{P}_{\bar{g}}(v\mathbb{F})(t) = vu^r x^s \exp\left(\frac{uxt}{1-xt}\right) \frac{1}{(1-xt)^{r+s}} $$

The weight of an $\mathbb{P}_{\bar{g}}(v\mathbb{F})$-structure on $[n]$ is $vu^{k+r}x^{n+s}$ if the associated $\mathbb{L}_{\bar{g}}$-structure has $k$ connected components, then $\mathcal{P}_{\bar{g}}^n(vu^r x^s) = \sum_{k=0}^n \pi_{r,s}(n,k)vu^{k+r}x^{n+s}$. We have:

$$ \lambda_{r,s}(n+1,k) = \lambda_{r,s}(n,k-1) + (n+k+r+s)\lambda_{r,s}(n,k) \quad (60) $$

with $\lambda_{r,s}(0,0) = 1$, and $\lambda_{r,s}(n,k) = 0$, if $k < 0$ or $k > n$. Note that $\lambda_{r,s}(n,k) = L_{r+s}(n,k)$ (example 7). $\diamond$

**Example 9** Consider the grammars $H_g = \{z \to zx, x \to x\}$ and $K_{g_1} = \{v \to \mu vu, u \to u^2\}$ et $M_{\bar{g}} = \{v \to \mu vux, u \to u^2x, x \to x\}$. Theorem 8 say that the matrix $\Pi = (\pi(n,k))_{n,k}$ associated with the grammar $M_{\bar{g}}$ verify $\Pi = SC$, in other words, $\pi(n,k) = \sum_{i=k}^n S(n,i)c(i,k)$. This matrix, A079641 in O.E.I.S. [9], is studied by Knuth in [11] and by Nick Early in [7]. We have:

$$ \mathbb{M}_{\bar{g}} = v\mathbb{E}_{\beta} \circ \left( \left( \int \mathbb{L}_{\alpha} \right) \circ \int x\mathbb{E} \right) = v\mathbb{S}_{\beta} \circ (x\mathbb{E}^{+}), \quad (61) $$

and the generating series is:

$$ \mathbb{M}_{\bar{g}}(t) = v(1 + u - uxe^t)^{-\mu} $$

An $\mathbb{M}_{\bar{g}}$-structure on $[n]$ with $k$ connected components (k cycles) can be identified with a pair $s = (s_1, s_2)$, where $s_1$ is a permutation of $[i]$ with $k$ cycles, and $s_2$ is a partition of $[n]$ into $i$ blocks. Its weight is $v\mu^k u^i x^i$. So, setting $\mathcal{M}_{\bar{g}}^n(v) = \sum_{k=1}^n \sum_{i=k}^n \pi(n, i, k)v\mu^k u^i x^i$, we have $\pi(n, i, k) = S(n, i)c(i, k)$, we have:

$$ \pi(n+1, i, k) = \pi(n, i-1, k-1) + (i-1)\pi(n, i-1, k) + i\pi(n, i, k), \quad (62) $$

recurrence relation that can be obtained either by using the recurrence relations of the numbers $c(n,k)$ and $S(n,k)$, or by using the relation $\mathcal{M}_{\bar{g}}^{n+1}(v) = \mathcal{M}_{\bar{g}}(\mathcal{M}_{\bar{g}}^n)(v)$.

Now, lets consider the $\mathbb{B}$-species $\mathbb{F} = \mathbb{F}_1\mathbb{F}_2$, with $\mathbb{F}_1(U) = U^r$ and $\mathbb{F}_2(X) = X^s$ from example 8. We have $\mathbb{M}_{\bar{g}}(\mathbb{F}_1) = (\mathbb{S}_{\alpha} \circ (x\mathbb{E}))^r$ and $\mathbb{H}_g(\mathbb{F}_2) = (x\mathbb{E})^s$. Therefore:

$$ \mathbb{M}_{\bar{g}}(v\mathbb{F}) = (v\mathbb{S}_{\beta} \circ (x\mathbb{E}^{+})) \cdot (\mathbb{S}_{\alpha} \circ (x\mathbb{E}))^{r} \cdot (x\mathbb{E})^{s}. \quad (63) $$

The exponential generating series is:

$$ \mathbb{M}_{\bar{g}}(v\mathbb{F})(t) = vu^r x^s (1 + u - uxe^t)^{-\mu} (1 - x(e^t - 1))^{-r} (x^s e^{st}) \quad (64) $$

An $\mathbb{M}_{\bar{g}}(v\mathbb{F})$-structure on $[n]$ is a triplet $s = (s_1, s_2, s_3)$, which can be identified as a pair $\tilde{s} = (\tilde{s}_1, \tilde{s}_2)$ where $\tilde{s}_1$ is a $K_{g_1}(v\mathbb{F}_1)$-structure on $[i]$ and $\tilde{s}_2$ is an $\mathbb{H}_g(\mathbb{F}_2)$-structure on $[n]$, where the associated $\mathbb{H}_g$-structure have $i$ connected components. Its weight is $\mu^k vu^{i+r}x^{i+s}$ if the $K_{g_1}$-structure associated with $\tilde{s}_1$ has $k$ connected components. Denoting by $\pi_{r,s}(n, i, k)$ the number of $\mathbb{M}_{\bar{g}}(v\mathbb{F})$-structures on $[n]$ such that the $K_{g_1}$-structure associated wit $K_{g_1}$ has $k$ connected components and the associated $\mathbb{H}_g$-structure has $i$ connected components, we have the recurrence:

$$ \pi_{r,s}(n+1, i, k) = \pi_{\mathbb{F}}(n, i-1, k-1) + (r+i-1)\pi_{\mathbb{F}}(n, i-1, k) + (s+i)\pi_{\mathbb{F}}(n, i, k) \quad (65) $$
**Example 10** In this example, we provide a bijective proof of the identity $S\Sigma = \Sigma S = I$, where $S = (S(n,k))$ is the matrix of Stirling numbers of the second kind, and $\Sigma = (s(n,k))$, where $s(n,k) = (-1)^{n-k}c(n,k)$ are the Stirling numbers of the first kind, and $I$ is the identity matrix. We use the involution's principle of Garcia-Milne ([8] or [25]).

Using Example 5, we can verify that the grammar associated with $\Sigma$ is the grammar $H'_g = \{v \to \mu v u, u \to -u^2\}$. The matrix associated with the grammar $P_{\bar{g}} = \{v \to \mu v u x, u \to -u^2 x, x \to x\}$ is the matrix $S\Sigma$, and the matrix associated with the grammar $P'_{\bar{g}} = \{v \to \mu v u x, u \to u x, x \to -x^2\}$ is therefore the product matrix $\Sigma S$. Figure 14(A)

<figure><img src="image_16.png" /><figcaption>Figure 14: (A) a $\mathbb{P}_{\bar{g}}$-structure $s$, (B) a $\mathbb{P}'_{\bar{g}}$-structure $s_1$</figcaption></figure>

represents an $\mathbb{P}_{\bar{g}}$-structure $s$ on [11] with 3 connected components, and Figure 14(B) a $\mathbb{P}'_{\bar{g}}$-structure $s_1$ on [13]. Using the isomorphisms $A_2 = \mathbb{L} = \mathbb{S}$, $C = \int \mathbb{S} = \int \mathbb{L}$ and $\mathbb{S} = \mathbb{E} \circ C$, we can verify that:

$$ \mathbb{P}_{\bar{g}} = v\mathbb{E} \circ \left( \int \mathbb{L}_{\delta} \circ (x\mathbb{E}) \right) = v\mathbb{S}_{\delta} \circ (x\mathbb{E}), \qquad (66) $$

where $\mathbb{L}_{\delta}$ and $\mathbb{S}_{\delta}$ are the $\mathbb{L}$-species of lists weighted by $\delta(\sigma) = (-1)^n u^n$ if $\sigma \in \mathbb{L}[n]$. In the same way, we have:

$$ \mathbb{P}'_{\bar{g}} = v\mathbb{E} \circ ((u\mathbb{E}) \circ \int \mathbb{L}_{\delta}) = v\mathbb{E} \circ (u\mathbb{S}_{\delta}) \qquad (67) $$

## 6.1 Case of the identity $S\Sigma = I$

For all $n$, we construct a weighted involution $\Phi_n$ on $\mathbb{P}_{\bar{g}}[n]$ as follows.

Note that the number of leaves of type $u$ is equal to the number of leaves of type $x$.

1. Suppose that the connected component of $n$ is not reduced to a singleton. Consider the tree $s'$ of size $n-1$, obtained by removing vertex $n$. A labeling $u_1, u_2, \dots, u_l$ and $x_1, x_2, \dots, x_l$ of the leaves of type $u$ and leaves of type $x$, by depth-first search, establishes a bijection $u_i \to x_i$. If $n$ was placed on $u_i$, then we set $\Phi_n(s) = s_1$, where $s_1$ is the tree obtained by placing $n$ on $x_i$. Conversely, if $n$ was placed on $x_i$, then $\Phi(s) = s_1$, where $s_1$ is the tree obtained by placing $n$ on $u_i$. Figure 15 (A) represents the tree $s'$ associated with $\mathbb{P}_{\bar{g}}$-structure $s$ in figure 14, and figure 15 (B) is its image.

2. If the connected component of $n$ is reduced to a singleton, then we apply the previous procedure to the largest integer $k$ whose connected component is not a singleton.

3. Otherwise, the connected component of every integer $k \in [n]$ is reduced to a singleton, we set $\Phi_n(s) = s$.
<figure><img src="image_17.png" /><figcaption>Figure 15: (A) Labeling of leaves of $s'$ (B) Image $\Phi_{11}(s)$</figcaption></figure>

We set $v = u = x = 1$. Then it is clear that $\Phi_n$ is a weighted involution on $\mathbb{P}_{\bar{g}}[n]$. Its restriction to the set of trees of size $n$ is a weighted involution whose unique fixed point is the tree in which all connected component are reduced to a singleton. Its weight is equal to 1.

## 6.2 Case of the identity $\Sigma S = I$

1. If the connected component of $n$ is not reduced to a singleton, consider this connected component.

<figure><img src="image_18.png" /><figcaption>Figure 16: Construction of a weighted $\Psi_n$ for $\mathbb{P}_{\bar{g}}[n]$</figcaption></figure>

As shown in figure 16, we compare the last point on the left branch with the last point on the right branch of this connected component. We move the larger of this and change its sign. This gives us $\Psi_n(s_1)$.

2. If the connected component of $n$ is reduced to a point, we apply the previous procedure to the largest integer $k$ whose connected component is not reduced to a point."

3. Otherwise, the connected component of all the points in $[n]$ is reduced to a point, we set $\Psi_n(s_1) = s_1$.

[15]

**Acknowledgment:** Thanks to Professor Gilbert Labelle, from the Laboratoire d'Algèbre, de Combinatoire et d'Informatique Mathematiques (LACIM), UQàM, Canada, for his advice.
References

[1] François Bergeron, Gilbert Labelle, and Pierre Leroux. *Combinatorial Species and Tree-likes Structures*, volume 57. Encyclopedia of Mathematics and its applications, Cambrides University Press, 1998.

[2] Khristo N. Boyadzhiev. Convolutions for stirling numbers, lah numbers, and binomial coefficients. arXiv:2103.15644v1, https://api.semanticscholar.org/CorpusID:232404054, 2021.

[3] Andrey Z. Broder. The r-stirling numbers. *Discrete Mathematics*, 49, (1984).

[4] William Y.C. Chen and Amy M. Fu. Context-free grammars for permutations and increasing trees. *Adv. in Appl. Math.*, Vol. 82:58–82, 2017.

[5] William.Y.C. Chen. Context-free grammars, differential operators and formal power series. *Theoretical Computer Sciences*, Vol 117:pp. 113–129, (1993).

[6] Dominique Dumont. Grammaires de william chen et dérivations dans les arbres et arborescences. *Sémin. Lothar. Combin.*, Vol. 37(n° B 31a):21 p., (1996).

[7] Nick Early. Can onical bases for permutohedral plates. arXiv:1712.08520v3 [math.CO], Available at https://arxiv.org/pdf/1712.08520, FEB 2018.

[8] Adriano M. Garcia, A., and James S. Milne. Methods for constructing bijections for classical partitionn identities. *Proc. Nat. Acad. SCi. U.S.A.*, 78, (1981) 2026-2028.

[9] OEIS Foundation Inc. The on-line encyclopedia of integer sequences, available at https://oeis.org.

[10] André Joyal. Une théorie combinatoire des séries formelles. *Advanced in Mathematics*, Vol. 42:1–82, 1981.

[11] Donald E. Knuth. Convolution polynomials. arXiv:math/9207221v1 [math.CA], Available at https://arxiv.org/abs/math/9207221v1, 1992.

[12] Gilbert Labelle. éclosions combinatoire appliquées à l'inversion multidimensionnelle des séries formelles. *Journal of Combinatotial Theory, Serie A*, 39(1), (1985).

[13] Ivo Lah. A new kind of numbers and its application in the actuarial mathematics. *Boletim do Instituto dos Actuários Portugueses, Lisbonne*, vol. 9:7–15, 1954.

[14] Pierre Leroux and Gerag X. Viennot. Combinatorial resolution of systems of differential equations iv: Separation of variables. *Discrete Mathematics*, Vol. 72:237–280, 1988.

[15] Pierre Leroux and Gérard X. Viennot. Combinatorial resolution of systems of differential equations, i. ordinary differential equations. In Gilbert Labelle and Pierre Leroux, editors, *Combinatoire énumérative*, pages 210–245, Berlin, Heidelberg, (1986). Springer Berlin Heidelberg.

[16] Pierre Leroux and Gérard X. Viennot. Résolution combinatoire des équations différentielles ii: Calcul intégral combinatoire. *Ann. Sci. Math. Québec*, Vol. 12(2):233–253, 1988.
[17] Miguel A. Méndez and José L. Ramírez. A new approach to the r-whitney numbers by using combinatorial differential calculu. *Acta Univ. Sapientiae, Mathematica*, 11, 2, (2019) 387-418.

[18] Russel Merris. The p-stirling numbers. *Turkish J. Math*, 24, 2000.

[19] Gábor Nyul and Gabriella Rácz. The r-lah numbers. *Discrete Mathematics*, 338, (2015).

[20] Marko Petkovesek and Tomaz Pinsanski. Interpretations of unsigned stirling and lah numbers. *Pi Mu Epsilon Journal*, 12(No 7), Fall 2007.

[21] Jean-Baptiste Priez. *Combinatoire des fonctions de parking : espèces, énumération d'automates et algèbres de Hopf*. Combinatoire [math.co]., Université Paris Saclay (COmUE), 2015.

[22] Benjamin Randrianirina. Combinatoire des systèmes d'équations différentielles et aux dérivées partielles, Thèse de doctorat, Publication du LaCIM, Université du Québec à Montréal, (available online at https://lacim.uqam.ca/fr/publications.html), Vol. 23, 2000.

[23] Benjamin Randrianirina. Espèces mixtes et système d'équations différentielles. *Annale des Sciences Mathématiques du Québec*, (available online at https://www.labmath.uqam.ca/annales/indexgeneral.html), Vol. 24(2):79-211, 2000.

[24] Mark Shattuck. Ge generalized r-lah numbers. Proc. Acad. Sci. (Math. Sci.), 126, November 2016.

[25] Denis Staton and Denis White. *Constructive combinatorics*, volume 23. Undergraduate Texts in Mathematics, Springer-Verla, New-York, 1986.