Séminaire Lotharingien de Combinatoire 61A (2009), Article B61Ag

GENERAL COMBINATORIAL DIFFERENTIAL OPERATORS

Gilbert Labelle and Cédric Lamathe

LaCIM, Département de Mathématiques, UQÀM

A la mémoire de notre collègue et ami, Pierre Leroux

Abstract. Let D = d/dX. We develop a theory of combinatorial differential operators of the form Ω(X, D) where Ω(X, T) is a species of structures built on two sorts, X and T, of underlying elements. These operators act on species, F (X), instead of functions. We show how to compose these operators, how to compute their adjoints and their counterparts in the context of underlying symmetric functions and power series. We also analyze how these operators behave when applied to products of species (generalized Leibniz rule) and other combinatorial operations. Special instances of these operators include: combinatorial finite difference operators, Φ(X, Δ), corresponding the species Ω(X, T) = Φ(X, E_{+}(T)), where E_{+} is the species of nonempty finite sets; pointing operators Λ(XD), which are self-adjoint and correspond to the species Ω(X, T) = Λ(XT); and combinatorial Hammond differential operators, Θ(D), corresponding to the species Ω(X, T) = Θ(T). We also give a table of all atomic differential operators X^{m}D^{k}/K where K is a subgroup of 𝕊_{m} × 𝕊_{k} and m + k ≤ 7.

Résumé. Soit D = d/dX. Nous développons une théorie d’opérateurs différentiels combinatoires de la forme Ω(X, D) où Ω(X, T) est une espèce de structures construite sur deux sortes, X et T, d’éléments sous-jacents. Ces opérateurs agissent sur des espèces, F (X), plutôt que sur des fonctions. Nous montrons comment composer ces opérateurs, comment calculer leurs adjoints et les opérateurs qui leur correspondent dans le contexte des fonctions symétriques et des séries génératrices. Nous analysons aussi le comportement de ces opérateurs lorsqu’ils sont appliqués au produit d’espèces (règle de Leibniz) ainsi qu’à d’autres opérateurs combinatoires. Ces opérateurs incluent les opérateurs combinatoires de différences finies, Φ(X, Δ), correspondant aux espèces Ω(X, T) = Φ(X, E_{+}(T)), où E_{+} est l’espèce des ensembles finis non-vides, les opérateurs de pointage, Λ(XD), qui sont auto-adjoints et les opérateurs différentiels combinatoires de Hammond, Θ(D), qui correspondent aux espèces Ω(X, T) = Θ(T). Nous donnons également une table de tous les opérateurs différentiels atomiques X^{m}D^{k}/K où K est un sous-groupe de 𝕊_{m} × 𝕊_{k} et m + k ≤ 7.

With the support of NSERC (Canada).

Contents

1. Introduction 2 1.1. The goal of this paper 2 1.2. Preliminary notions about species 3 2. General combinatorial differential operators 6 2.1. Basic definitions 6 2.2. Bilinear form and adjoint operators 12 3. Special cases 13 3.1. Combinatorial Hammond differential operators 13 3.2. Self-adjoint and pointing operators 14 3.3. Finite differences operators 14 3.4. Handle operators 15 3.5. Splittable and classical operators 15 3.6. Computations with molecular and atomic differential operators 16 3.7. Further extensions of the theory 17 References 23

1. Introduction

1.1. The goal of this paper. Let D = d/dX denote the classical analytical derivation operator defined by

DF (X) = \frac{d}{dX} F (X) = F′(X).

Higher order derivations D^{n} = d^{n}/dX^{n} are obtained by iterating D. Alternatively, they can be visualized as lists of D’s of the form

\underbrace{DDD ⋯ D}_{n times} .

But, a natural question is: what meaning can be given to circular arrangements or graphical arrangements of D’s as in Figure 1?

Figure 1. Circular and graphical arrangements of D’s

More generally, what meaning can be given to circular or graphical arrangements of D’s and X’s as in Figure 2 where X is interpreted as the “multiplication by X” operator defined by F (X) ↦ XF (X)? The purpose of this paper is to give an answer to these questions in the realm of species.

Figure 2. Circular and graphical arrangements of D’s and X’s

To achieve this goal, we will make use of partial cartesian products and substitutions of the form T := 1 to introduce general differential operators of the form Ω(X, D), where Ω(X, T) is an arbitrary two-sort species. These operators Ω(X, D) will transform species into species. For the benefit of the reader, we first recall some basic notions about species.

1.2. Preliminary notions about species. Informally, a combinatorial species of structures is a class of labelled structures which is closed under relabellings along bijections.^{1} A structure belonging to a species F is called an F -structure. The set of F -structures on a finite underlying set U is assumed to be finite and is denoted by F [U]. Hence, s ∈ F [U] means that s is an F -structure on U. Two F -structures s and t are said isomorphic if one can be obtained from the other one by a relabelling induced by a bijection between their underlying sets. More precisely, if β : U → V is such a bijection, the induced relabelling is denoted by F [β] : F [U] → F [V]. An isomorphism class of F -structures is called an unlabelled F -structure. Two species F and G are equal (isomorphic), and we write F = G, if there exists a natural isomorphism (in the sense of theory of category) between them. This means that for each U, there exists a bijection α_{U} : F [U] → G[U] such that G[β]α_{U} = α_{V} F [β] for each bijection β : U → V.

Several enumerative formal series can be associated to any species F. The most important one is the cycle index series, denoted Z_{F} (x_{1}, x_{2}, x_{3}, …), and is defined by

Z_{F} (x_{1}, x_{2}, x_{3}, …) = ∑_{n≥0} \frac{1}{n!} ∑_{σ∈𝕊_{n}} fixF [σ] x_{1}^{σ_{1}}x_{2}^{σ_{2}}x_{3}^{σ_{3}} ⋯ = ∑_{n_{1},n_{2},...} f_{n_{1},n_{2},...} \frac{x_{1}^{n_{1}}x_{2}^{n_{2}} ⋯}{1^{n_{1}}n_{1}!2^{n_{2}}n_{2}! ⋯}

(1)

where 𝕊_{n} denotes the symmetric group of order n, fixF [σ], the number of F -structures on [n] left fixed under the action of the permutation σ ∈ 𝕊_{n}, σ_{i}, i ∈ ℕ^{∗}, is the number of cycles of length i of the permutation σ ∈ 𝕊_{n} and f_{n_{1},n_{2},...} = fixF [σ] if σ is of type 1^{n_{1}}2^{n_{2}} · · ·. Other classical enumerative formal series, that is, the exponential generating series F (x), which counts labeled F -structures, and the tilda generating series F̃(x), which counts the unlabeled F -structures. These series are obtained specializing the series Z_{F},

F (x) = Z_{F} (x, 0, 0, …) and F̃(x) = Z_{F} (x, x^{2}, x^{3}, …).  (2)

1Formally, a species of structures is a functor from the category of finite sets and bijections to the category of finite sets and functions, see [8].

Many combinatorial operations can be performed in the framework of the theory of species. The main ones are addition, product, substitution, pointing, cartesian product and derivation. For precise definitions of these operations, see [2]. However, in this paper we make an extensive use of the cartesian product and the derivation and we briefly recall their definitions. Let F and G be any species and U a finite set. The derivative species F′ or DF of a species F is given by F′[U] = F [U + {∗_{U}}], where ∗_{U} is an element chosen outside of the underlying set U. The cartesian product of F and G, denoted F × G, is defined by (F × G)[U] = F [U] × G[U].

The behaviour of the cycle index series according to the operations of derivation and of cartesian product is well known; see [2]. In particular, we have

Z_{F′}(x_{1}, x_{2}, x_{3}, …) = \frac{∂}{∂x_{1}} Z_{F} (x_{1}, x_{2}, x_{3}, …),  (3)
Z_{F ×G}(x_{1}, x_{2}, x_{3}, …) = (Z_{F} × Z_{G})(x_{1}, x_{2}, x_{3}, …),  (4)

where Z_{F} × Z_{G} means the Hadamard (coefficient by coefficient) product of the series Z_{F} and Z_{G}.

A molecular species M is a species possessing only one isomorphism type. This means that any two M-structures are always isomorphic. Such a species is characterized by the fact that it is indecomposable under the combinatorial sum:

M is molecular ⟺ (M = F + G ⟹ F = 0 or G = 0).

Any molecular species M can be written under the form of a quotient species M = X^{n}/H, where X^{n} represents the species of linear orders of length n and H ≤ 𝕊_{n} is a subgroup of the symmetric group of order n. In fact, H is the stabilizer of any Mstructure. Two molecular species X^{n}/H and X^{m}/K are equal (that is, isomorphic as species) if and only if n = m and H and K are conjugate subgroups of 𝕊_{n}. Furthermore, any species F can be uniquely expanded in terms of molecular species as follows:

F = ∑_{M∈M} f_{M}M,

where M denotes the set of all molecular species and f_{M} ∈ ℕ is the number of subspecies of F isomorphic to M. This expansion is unique and called the molecular expansion of the species F.

It is also possible to extend the notion of molecular species to the case of multi-sort species. For instance, for two-sort species, where the two sorts of elements of underlying sets are denoted X and T, each molecular species M = M(X, T) can be written in the form M(X, T) = X^{n}T^{k}/H, where H ≤ 𝕊_{n}^{X} × 𝕊_{k}^{T} is the stabilizer of any M-structure and 𝕊_{n}^{X} is the symmetric group of order n acting on points of sort X. The exponents n and k are called degree of M in X and T. The cycle index series of a two-sort molecular species M(X, T) = X^{n}T^{k}/H is given by the expression

Z_{M}(x_{1}, x_{2}, …; t_{1}, t_{2}, …) = \frac{1}{|H|} ∑_{h∈H} x_{1}^{c_{1}(h)}x_{2}^{c_{2}(h)} ⋯ t_{1}^{d_{1}(h)}t_{2}^{d_{2}(h)} ⋯,

where c_{i}(h) (respectively d_{i}(h)), for i ≥ 1, denotes the number of cycles of length i of the permutation on points of sort X (respectively T) induced by the element h ∈ H and |H| is the cardinality of H. Note that 𝕊_{n}^{X} ×𝕊_{k}^{T} is isomorphic to the Young subgroup 𝕊_{n,k} ≤ 𝕊_{n+k} permuting independently {1, 2, …, n} and {n + 1, n + 2, …, n + k}.

It is important to notice that in the series Z_{M} above, the monomials in the x_{i}’s always appear before the ones in the t_{i}’s.

In this paper, we use the following graphical conventions:

1) for any species F = F (X), we find appropriate to represent a F -structure by a drawing of the form of Figure 3 a) where black dots stand for the distinct elements (of sort X) of the underlying set;

2) for two-sort species Ω = Ω(X, T), Figure 3 b) shows a convention used to represent an Ω-structure, where black dots (respectively black squares) are elements of sort X (respectively of sort T);

3) setting T := 1 in a species Ω(X, T), we obtain the species Ω(X, 1) where points of sort T are unlabelled. Notice that white squares represent indistinguishable unlabelled elements of sort T; see Figure 3 c) and the substitution is possible if Ω(X, T) is “finitary in T ”. This means that for every finite set U of points of sort X there is no Ω-structure on the pair of sets (U, V) for every sufficiently large finite set V of points of sort T. The cycle index series Z_{Ω(X,1)} of Ω(X, 1) is computed as follows:

Z_{Ω(X,1)}(x_{1}, x_{2}, …) = Z_{Ω(X,T)}(x_{1}, x_{2}, …; t_{1}, t_{2}, …)|_{t_{i}:=1} = Z_{Ω(X,T)}(x_{1}, x_{2}, …; 1, 1, …). (5)

Figure 3. a) F (X)-structure; b) Ω(X, T)-structure; c) Ω(X, 1)-structure

Using these kinds of graphical conventions, the structures belonging, for example, to the cartesian product Ω_{1}(X, T) × Ω_{2}(X, T) of two-sort species can be represented by Figure 4 a) and a structure belonging ot the species F′(X) can be represented by Figure 4 b).

Figure 4. a) Ω_{1}(X, T) × Ω_{2}(X, T)-structure; b) F′(X)-structure

Finally, we will make an extensive use in this paper of the so-called partial cartesian product according to a sort. Considering two-sort species Ω_{1}(X, T) and Ω_{2}(X, T), the partial cartesian product with respect to the sort T of Ω_{1} and Ω_{2} is denoted by

Ω_{1}(X, T) ×_{T} Ω_{2}(X, T)  (6)

and is illustrated by Figure 5. Formally, a Ω_{1}(X, T) ×_{T} Ω_{2}(X, T)-structure s on a pair (U, V) of sets of sort X and T, respectively, is a pair s = (s_{1}, s_{2}) where s_{1} ∈ Ω_{1}[U_{1}, V] and s_{2} ∈ Ω_{2}[U_{2}, V] where U_{1} ∪ U_{2} = U and U_{1} ∩ U_{2} = ∅. This operation had been first introduced by Gessel and Labelle in [7] in the context of Lagrange inversion.

The cycle index series Z_{Ω_{1}×_{T} Ω_{2}} is computed in the following way

Z_{Ω_{1}×_{T} Ω_{2}}(x_{1}, x_{2}, …; t_{1}, t_{2}, …)

= ∑_{n_{1},n_{2},...} ω_{1,n_{1},n_{2},...}(x_{1}, x_{2}, …)ω_{2,n_{1},n_{2},...}(x_{1}, x_{2}, …)\frac{t_{1}^{n_{1}}t_{2}^{n_{2}} ⋯}{1^{n_{1}}n_{1}!2^{n_{2}}n_{2}! ⋯}, (7)

where ω_{1,n_{1},n_{2},...}(x_{1}, x_{2}, …) and ω_{2,n_{1},n_{2},...}(x_{1}, x_{2}, …) are defined by

Z_{Ω_{i}}(x_{1}, x_{2}, …; t_{1}, t_{2}) = ∑_{n_{1},n_{2},...} ω_{i,n_{1},n_{2},...}(x_{1}, x_{2}, …)\frac{t_{1}^{n_{1}}t_{2}^{n_{2}} ⋯}{1^{n_{1}}n_{1}!2^{n_{2}}n_{2}! ⋯}, for i = 1, 2.

(8)

The right-hand side of (7) is denoted by Z_{Ω_{1}} ×_{t} Z_{Ω_{2}} and is called the Hadamard product of Z_{Ω_{1}} and Z_{Ω_{2}} relative to t = (t_{1}, t_{2}, …)

It can be checked that ×_{T} can be written in terms of the ordinary cartesian product as Ω_{1}(X, T)E(Y) × Ω_{2}(Y, T)E(X)|_{Y:=X}, where E denotes the species of finite sets.

Figure 5. Representation of an Ω_{1}(X, T) ×_{T} Ω_{2}(X, T)-structure

2. General combinatorial differential operators

2.1. Basic definitions. We are now ready to state our main definition.

Definition 1 (General combinatorial differential operators). Let Ω(X, T) be a two-sort species and F (X) be a species. If Ω(X, T) is finitary in T or F (X) is of finite degree in X, then Ω(X, D)F (X) is the species defined by

Ω(X, D)F (X) := Ω(X, T) ×_{T} F (X + T)|_{T:=1}.  (9)
□

Figure 6 a) describes a typical Ω(X, D)F (X)-structure on a set of 9 elements of sort X. For example, let Ω(X, T) = A(X, T) be the species of rooted trees with internal nodes of sort X and leaves of sort T and F (X) = C_{10}(X) be the species of oriented cycles of length 10, then Figure 6 b) shows a typical A(X, D)C_{10}(X)-structure. Taking Ω(X, D) = E(L_{≥2}(X)D) where E and L_{≥2} are the species of sets and of lists of length ≥ 2, respectively, then the species of octopuses (see Figure 6 c)) can be written as Oct(X) = E(L_{≥2}(X)D)C(X) where C(X) is the species of oriented cycles.

Figure 6. a) Ω(X, D)F (X)-structure, b) A(X, D)C_{10}(X)-structure and

c) an octopus

Another example is given by taking Ω(X, D) = E(P_{≥2}(X)D), where P(X) is any species of the form P(X) = X + P_{≥2}(X). Then, it is easily seen that

E(P_{≥2}(X)D)F (X) = F (P(X))

and formula (13) of Proposition 1 below reduces to the plethystic substitution Z_{F ∘P} = Z_{F} ∘ Z_{P} as the reader can check. The operator P_{≥2}(X)D is similar to an “eclosion” operator in the terminology of [10].

Note that the restrictions on Ω or F in Definition 1 are necessary in order that (9) defines a species. For example, for the species C(X) of oriented cycles (of arbitrary lengths), A(X, D)C(X) is not a species since the number of structures would be infinite on any non-empty finite set U. From now, we will always assume that the restrictions in Definition 1 are satisfied.

Since every two-sort species Ω(X, T) can be written as a linear combination ∑ ω_{K} \frac{X^{n}T^{k}}{K} of molecular species, every differential operator Ω(X, D) is a linear combination of the corresponding molecular linear operators of the form X^{n}D^{k}/K, K ≤ S_{n,k}. We will denote the action of these operators on species F (X) by

(\frac{X^{n}D^{k}}{K} ) F (X) = \frac{X^{n}F^{(k)}(X)}{K}

in conformity with the classical notation X^{n}D^{k}F (X) = X^{n}F^{(k)}(X) corresponding to the degenerate case where K = {id}. With these notations, we have

Theorem 1 (Generalized Leibniz rule). Let F (X) and G(X) be two species. Then,

\frac{X^{n}D^{k}}{K} F (X)G(X) = ∑_{i+j=k} ∑_{L:S_{n,i,j}} \binom{K}{L}\frac{X^{n}F^{(i)}(X)G^{(j)}(X)}{L},  (10)

where L : S_{n,i,j} means that L runs through a complete system of representatives of the conjugacy classes of subgroups of S_{n,i,j} and the coefficients \binom{K}{L} are defined by the “addition formula” [1],

X^{n}(T_{1} + T_{2})^{k}/K = ∑_{i+j=k} ∑_{L:S_{n,i,j}} \binom{K}{L}X^{n}T_{1}^{i}T_{2}^{j}/L.  (11)

Proof. By definition of X^{n}D^{k}/K, we have (see Figure 7)

\frac{X^{n}D^{k}}{K} F (X) · G(X) = \frac{X^{n}T^{k}}{K} ×_{T} (F (X + T) · G(X + T))|_{T:=1}.  (12)

The result then follows immediately from (11) by interpreting the white squares in

Figure 7. Overview of a [X^{n}D^{k}/K]F (X)G(X)-structure

the F -structure (respectively in the G-structure) as unlabelled singletons of sort T_{1} (respectively T_{2}) and using linearity. □

For example, n = 0 and K = {id} corresponds to the classical Leibniz rule

D^{k}F (X)G(X) = ∑_{i+j=k} \binom{k}{i}F^{(i)}(X)G^{(j)}(X),

while, the molecular operator E_{2}(XD), where E_{2} is the species of 2-sets, corresponds to the formula

E_{2}(XD)(F · G) = (E_{2}(XD)F) · G + X^{2}F′ · G′ + F · (E_{2}(XD)G) .

In the context of cycle index series, the combinatorial differential operators behave as follows.

Proposition 1. Let G(X) = Ω(X, D)F (X), then we have

Z_{G}(x_{1}, x_{2}, x_{3}, …) = Z_{Ω}(x_{1}, x_{2}, x_{3}, …; \frac{∂}{∂x_{1}} , 2\frac{∂}{∂x_{2}} , 3\frac{∂}{∂x_{3}} , …)Z_{F} (x_{1}, x_{2}, x_{3}, …). (13)

Proof. Writing Z_{Ω(X,T)} in the form

Z_{Ω(X,T)}(x_{1}, x_{2}, …; t_{1}, t_{2}, …) = ∑_{n_{1},n_{2},...} ω_{n_{1},n_{2},...}(x_{1}, x_{2}, …)\frac{t_{1}^{n_{1}}t_{2}^{n_{2}} ⋯}{1^{n_{1}}n_{1}!2^{n_{2}}n_{2}! ⋯},

we have successively, using (7),

Z_{G}(x_{1}, x_{2}, …) = Z_{Ω}(x_{1}, x_{2}, …; t_{1}, t_{2}, …) ×_{t} Z_{F} (x_{1} + t_{1}, x_{2} + t_{2}, …)|_{t_{i}:=1}

= Z_{Ω}(x_{1}, x_{2}, …; t_{1}, t_{2}, …) ×_{t} e^{t_{1}( \frac{∂}{∂x_{1}} )+t_{2}( \frac{∂}{∂x_{2}} )+···}Z_{F} (x_{1}, x_{2}, …)|_{t_{i}:=1}

= ∑_{n_{1},n_{2},...} ω_{n_{1},n_{2},...}(x_{1}, x_{2}, …)(\frac{∂}{∂x_{1}} )^{n_{1}} (2\frac{∂}{∂x_{2}} )^{n_{2}} ⋯

· Z_{F} (x_{1}, x_{2}, …)\frac{t_{1}^{n_{1}}t_{2}^{n_{2}} ⋯}{1^{n_{1}}n_{1}!2^{n_{2}}n_{2}! ⋯}|_{t_{i}:=1}

= Z_{Ω}(x_{1}, x_{2}, …; \frac{∂}{∂x_{1}} , 2\frac{∂}{∂x_{2}} , …)Z_{F} (x_{1}, x_{2}, …).

□

In Proposition 1, the convention of writing all the t_{j}’s to the right of all the x_{i}’s in Z_{Ω}(x_{1}, x_{2}, …, t_{1}, t_{2}, …) must be applied. For example, taking Ω(X, D) = E(XD), where E is the species sets, we have E(XD)F (X) = F (2X). In this case, we must take

Z_{E(XD)}(x_{1}, x_{2}, …, \frac{∂}{∂x_{1}} , 2\frac{∂}{∂x_{2}} , …) = ∑ \frac{x_{1}^{n_{1}}x_{2}^{n_{2}} ⋯ (\frac{∂}{∂x_{1}} )^{n_{1}}(\frac{∂}{∂x_{2}} )^{n_{2}} ⋯}{n_{1}!n_{2}! ⋯},

not

∑ \frac{(x_{1} \frac{∂}{∂x_{1}} )^{n_{1}}(x_{2} \frac{∂}{∂x_{2}} )^{n_{2}} ⋯}{n_{1}!n_{2}! ⋯}.

Corollary 1. Let G(X) = Ω(X, D)F (X). Then, the exponential generating series G(x) for labelled G-structures and the tilde generating series G̃(x) for unlabelled G-structures are given by

G(x) = ∑_{n_{1},n_{2},...} ω_{n_{1},n_{2},...}(x, 0, 0, …) [\frac{(\frac{∂}{∂x_{1}} )^{n_{1}} (\frac{∂}{∂x_{2}} )^{n_{2}} ⋯}{n_{1}!n_{2}! ⋯}Z_{F} ] (x, 0, 0, …),  (14)

G̃(x) = ∑_{n_{1},n_{2},...} ω_{n_{1},n_{2},...}(x, x^{2}, x^{3}, …) [\frac{(\frac{∂}{∂x_{1}} )^{n_{1}} (\frac{∂}{∂x_{2}} )^{n_{2}} ⋯}{n_{1}!n_{2}! ⋯}Z_{F} ] (x, x^{2}, x^{3}, …), (15)

where ω_{n_{1},n_{2},...}(x_{1}, x_{2}, x_{3}, …) are defined by

Z_{Ω}(x_{1}, x_{2}, …; t_{1}, t_{2}, …) = ∑_{n_{1},n_{2},...} ω_{n_{1},n_{2},...}(x_{1}, x_{2}, x_{3}, …)\frac{t_{1}^{n_{1}}t_{2}^{n_{2}} ⋯}{1^{n_{1}}n_{1}!2^{n_{2}}n_{2}! ⋯}.  (16)

Proof. Immediate from the proof of Proposition 1 and the fact that G(x) = Z_{G}(x, 0, 0, …) and G̃(x) = Z_{G}(x, x^{2}, x^{3}, …). □

Note that, in the particular case Ω(X, D) = D, formulas (14) and (15) reduce to the classical formulas

(DF)(x) = \frac{∂}{∂x}F (x),  F̃′(x) = [\frac{∂}{∂x_{1}} Z_{F} ] (x, x^{2}, x^{3}, …).

However, for a general differential operator Ω(X, D), the computation of [Ω(X, D)F] (x) and { \atop [Ω(X, D)F]}(x) depends on Z_{Ω} and the mixed derivations (\frac{∂}{∂x_{1}} )^{n_{1}} (\frac{∂}{∂x_{2}} )^{n_{2}} ⋯ Z_{F}.

Definition 2 (Composition of differential operators). Let Ω_{1}(X, T) and Ω_{2}(X, T) be two-sort species. Then, we define the composition of Ω_{1}(X, T) by Ω_{2}(X, T) by

Ω_{2}(X, T) ⊙ Ω_{1}(X, T) = Ω_{3}(X, T),  (17)

where

Ω_{3}(X, T) = Ω_{2}(X, T + T_{0}) ×_{T_{0}} Ω_{1}(X + T_{0}, T)|_{T_{0}:=1},  (18)

and T_{0} is an auxiliary extra sort. The differential operator corresponding to Ω_{3}(X, T) is denoted Ω_{2}(X, D) ⊙ Ω_{1}(X, D) and is called the composition of Ω_{1}(X, D) by Ω_{2}(X, D).

Figure 8 illustrates an Ω_{3}(X, T)-structure.

Figure 8. Ω_{2}(X, T + T_{0}) ×_{T_{0}} Ω_{1}(X + T_{0}, T)|_{T_{0}:=1}-structure

The operation ⊙ is noncommutative and associative. For example, (XD)⊙(X^{2}D) = 2X^{2}D + X^{3}D^{2} while (X^{2}D) ⊙ (XD) = X^{2}D + X^{3}D^{2}. The proof of associativity is left to the reader. The next proposition states that the composition Ω_{2}(X, D) ⊙ Ω_{1}(X, D) corresponds to the application of Ω_{1}(X, D) followed by Ω_{2}(X, D).

Proposition 2. For any species F = F (X),

(Ω_{2}(X, D) ⊙ Ω_{1}(X, D)) F (X) = Ω_{2}(X, D) [Ω_{1}(X, D)F (X)] .

Proof. We first write

Ω_{2}(X, D) [Ω_{1}(X, D)F (X)] = Ω_{2}(X, D) [Ω_{1}(X, T_{1}) ×_{T_{1}} F (X + T_{1})|_{T_{1}:=1}]

= {Ω_{2}(X, T_{2}) ×_{T_{2}} [ [Ω_{1}(X, T_{1}) ×_{T_{1}} F (X + T_{1})|_{T_{1}:=1}] ]|_{X:=X+T_{2}}} |_{T_{2}:=1}.

The proof is then established by examining Figure 9. □

For cycle index series, the operation ⊙ has the following counterpart.

Theorem 2. Let Ω_{2}(X, T) and Ω_{1}(X, T) be any two-sort species. Then, we have

Z_{Ω_{2}⊙Ω_{1}} = ∑_{n_{1},n_{2},...} \frac{((\frac{∂}{∂t_{1}} )^{n_{1}}(2\frac{∂}{∂t_{2}} )^{n_{2}} ⋯ Z_{Ω_{1}}) ((\frac{∂}{∂x_{1}} )^{n_{1}}(2\frac{∂}{∂x_{2}} )^{n_{2}} ⋯ Z_{Ω_{2}})}{1^{n_{1}}n_{1}!2^{n_{2}}n_{2}! ⋯}.  (19)

Proof. We have

Z_{Ω_{2}(X,T_{0}+T)} = e^{t_{01} \frac{∂}{∂t_{1}} + \frac{t_{02}}{2} \frac{2∂}{∂t_{2}} + \frac{t_{03}}{3} \frac{3∂}{∂t_{3}} +···}Z_{Ω_{2}(X,T)}(x_{1}, x_{2}, …; t_{1}, t_{2}, …)  (20)
= ∑_{n_{1},n_{2},...} \frac{t_{01}^{n_{1}}t_{02}^{n_{2}} ⋯ (\frac{∂}{∂t_{1}} )^{n_{1}}(2\frac{∂}{∂t_{2}} )^{n_{2}} ⋯}{1^{n_{1}}n_{1}!2^{n_{2}}n_{2}! ⋯}Z_{Ω_{2}(X,T)}(x_{1}, x_{2}, …; t_{1}, t_{2}, …) (21)

Figure 9. a) Ω_{2}(X, D) [Ω_{1}(X, D)F (X)] and b) [Ω_{2}(X, D) ⊙ Ω_{1}(X, D)] F (X)

In a similar way,

Z_{Ω_{1}(X+T_{0},T)} = ∑_{n_{1},n_{2},...} \frac{t_{01}^{n_{1}}t_{02}^{n_{2}} ⋯ (\frac{∂}{∂x_{1}} )^{n_{1}}(2\frac{∂}{∂x_{2}} )^{n_{2}} ⋯}{1^{n_{1}}n_{1}!2^{n_{2}}n_{2}! ⋯}Z_{Ω_{1}(X,T)}(x_{1}, x_{2}, …; t_{1}, t_{2}, …). (22)

The result follows using the Hadamard product according to the sort T_{0} and letting t_{0i} := 1, i = 1, 2, 3, . . .. □

The following example exhibits a curious hidden symmetry involving combinatorial differential operators. Let F = F (X) be a species and consider the combinatorial operator F (X + XD) associated to the two-sort species F (X + XT). For any species G(X), we have the combinatorial equality

F (X + XD)G(X) = G(X + XD)F (X)  (23)

as Figure 10 shows. In this equality, F and G play symmetric roles. We denote the common value in (23) by F ˙×G and call it the “kiss product” of the species F and G for obvious reasons. The two classical products F · G and F × G are subspecies of F ˙×G since they can be respectively interpreted as the “empty kiss product” and the “full kiss product” of the species F and G :

F · G ⊂ F ˙×G and F × G ⊂ F ˙×G  (24)

The computations of the associated series Z_{F ˙×G}(x_{1}, x_{2}, …), (F ˙×G)(x) and { \atop F ˙×G}(x)

Figure 10. F (X + XD)G = F ˙×G = G(X + XD)F

are left to the reader.

Figure 11 shows a C ˙×C-structure, where C is the species of oriented cycles.

Figure 11. A C ˙×C-structure

2.2. Bilinear form and adjoint operators. In [8], Joyal introduced a bilinear form, denoted ⟨ , ⟩, in the realm of species in the following way: given two species F = F (X) and G = G(X), ⟨ F (X), G(X) ⟩ is defined by

⟨ F (X), G(X) ⟩ = F (X) ×_{X} G(X)|_{X:=1} = number of unlabelled F × G − structures,

(25)

provided it is finite (see Figure 12 a)). He showed that, for any species H(X),

⟨ H(D)F (X), G(X) ⟩ = ⟨ F (X), H(X)G(X) ⟩,  (26)

which means that multiplication by H(X) is a right adjoint to H(D).

We have the following more general result:

Proposition 3. Let Ω(X, T) be a two-sort species. Then,

⟨ Ω(X, D)F (X), G(X) ⟩ = ⟨ F (X), Ω(D, X)G(X) ⟩.  (27)

That is (Ω(X, D))^{∗} := Ω(D, X) is the adjoint operator of Ω(X, D).

Proof. See Figure 12 b). □

Figure 12. a) ⟨ F (X), G(X) ⟩ and b) ⟨ Ω(X, D)F (X)), G(X) ⟩ =
⟨ F (X), Ω(D, X)G(X) ⟩

Proposition 4. Let Ω_{1}(X, D) and Ω_{2}(X, D) be two sort-species. Then, we have

(Ω_{2}(X, D) ⊙ Ω_{1}(X, D))^{∗} = Ω_{1}^{∗}(X, D) ⊙ Ω_{2}^{∗}(X, D) = Ω_{1}(D, X) ⊙ Ω_{2}(D, X). (28)
□

3. Special cases

3.1. Combinatorial Hammond differential operators. The special case Ω(X, T) = Θ(T) corresponds to the classical Hammond combinatorial differential operator defined by (see [6, 9])

Θ(D)F (X) = (E(X)Θ(T)) × (F (X + T))|_{T:=1} := Θ(T) ×_{T} F (X + T)|_{T:=1}. (29)

Figure 13 shows a typical Θ(D)F (X)-structure. Note that, contrarily to the general

Figure 13. A typical Ω(D)F (X)-structure

case, the composition Θ(D) ⊙ Ψ(D) of Hammond operators is commutative since it corresponds to ordinary multiplication:

Θ(D) ⊙ Ψ(D) = (Θ · Ψ)(D).  (30)

Example 1. The following relations can be easily established by appropriate drawings and details are left to the reader.

(1) For Θ(T) = E_{2}(T), the species of two-element sets, we have

E_{2}(D)(F · G) = (E_{2}(D)F) · G + F′G′ + (E_{2}(D)G) · F,  (31)
E_{2}(D)(E ∘ F) = (E ∘ F) · (E_{2}(D)F + E_{2}(F′)).  (32)

In particular, for the species F = C of oriented cycles and E ∘ C = S of permutations, the previous equation takes the form

E_{2}(D)S = S · (E_{2}(D)F + E_{2}(L)).

(2) Translation operators. Taking Θ(X) = E(X), the species of sets, we obtain the translation operator denoted E(D), whose action is described by

E(D)F (X) = F (X + 1), E^{n}(D)F (X) = F (X + n).

(3) When Θ(T) = T^{n}, n ≥ 0, then we recover the usual n-th derivatives

Θ(D)F (X) = D^{n}F (X) = \frac{d^{n}F (X)}{dX^{n}}.

(4) Catalan derivative. Let Θ(T) = B(T) be the species of binary trees. It is well known that this species satisfies the functional equation B = 1 + T B^{2}. Since 1/B(T) = 1 − T B(T) we deduce that

B(D)F (X) = G(X) ⟺ F (X) = (1 − DB(D)) G(X).

It is important to notice that the species 1 − T B(T) is virtual, in this case.

(5) We can generalize the preceding example by taking any species B = B(T) with constant term equal to 1 since such a species is invertible under product (in the context of virtual species; see [2, 9]), we have

B(D)F (X) = G(X) ⟺ F (X) = \frac{1}{B(D)}G(X).

□

3.2. Self-adjoint and pointing operators. Since the adjoint of an operator Ω(X, D) is Ω(D, X), self-adjoint operators correspond to symmetric species Ω(X, T) = Ω(T, X). For example, the operator X^{3}D^{3}/K, where K = ⟨ (123)(456) ⟩ ≤ S_{3,3} is self-adjoint and Φ(X + D) is self-adjoint for any species Φ(X).

An important class of self-adjoint operators is the Λ-pointing operators defined by Λ(XD), where Λ = Λ(T) is an arbitrary species. Figure 14 a) shows a typical Λ(XD)F (X)-structure. The special case Λ(T) = T corresponds to the classical oneelement pointing. The composition of pointing operators is commutative and is given by

Λ_{2}(XD) ⊙ Λ_{1}(XD) = (Λ_{2} ˙×Λ_{1})(XD),

where ˙× denotes the kiss product operation.

Figure 14. a) Λ-pointed F -structure, b) (XD)^{2}F -structure and c)

(XD ⊙ XD)F -structure

Taking Λ(T) = T^{2}, we obtain the operator (XD)^{2} which corresponds to point an ordered pair of distinct elements in structures (see Figure 14 b)). Note that

(XD) ⊙ (XD) = XD + X^{2}D^{2} ≠ (XD)^{2} = X^{2}D^{2}

since we can point the same element in two successive pointings (see Figure 14 c)).

Taking Λ(T) = C(T), the species of oriented cycles, we obtain the operator C(XD) of cyclic-pointing. An interesting subspecies of C(XD)F (X) has recently been introduced by Bodirsky et al. [3]. It consists of all unbiased cyclically pointed F -structures. In such structures, the pointed cycle must be one of the cycles of an automorphism of the F - structure. They applied this unbiased pointing to the uniform random generation of classes of unlabelled structures.

3.3. Finite differences operators. We saw in Section 3.1, that E(D) is the translation operator on species (of finite degree): E(D)F (X) = F (X + 1). Hence, we can define the difference operator Δ by the equation

Δ = E_{+}(D),

where E_{+} = E − 1 is the species of non-empty finite sets. We obviously have

ΔF (X) = F (X + 1) − F (X).  (33)

Note that the right-hand side of (33) is not a virtual species since F (X) is always a subspecies of F (X + 1). Conversely, we can write D = E_{+}^{<−1>}(Δ), where E_{+}^{<−1>} is the inverse under substitution of the species E_{+} (see [2] for a description of E_{+}^{<−1>}). This opens the way to a completely new theory of general combinatorial difference operators of the form Φ(X, Δ) = Φ(X, E_{+}(D)) where Φ(X, T) is an arbitrary species.

3.4. Handle operators. Let K be a subgroup of 𝕊_{n,k}. By definition, the number k is called the degree of the molecular differential operator X^{n}D^{k}/K. More generally, the degree of the differential operator Ω(X, D), is the supremum (possibly infinite) of the degrees occurring in its molecular expansion Ω(X, D) = ∑_{K} ω_{K}X^{n}D^{k}/K. If all the degrees involved are k, the operator is said to be homogeneous of degree k. Degree 0 operator are simply the multiplication operators H(X) which are adjoint, as we saw before, to the Hammond operators H(D). Homogeneous operators of degree 1 are easily classified. They are of the form H(X)D, since every species Ω(X, T), homogeneous of degree 1 in T is of the form H(X)T. Homogeneous operator of degree 2 are a little more involved. We call them handle operators for obvious reasons (see Figure 15). The molecular handle operators X^{n}D^{2}/K fall into two classes:

a) the oriented ones, for which the second projection π_{2}(K) is trivial in 𝕊_{2};

b) the unoriented ones, for which π_{2}(K) ≃ 𝕊_{2}. For example, C_{3}(X)D^{2} is oriented and E_{2}(XD) is unoriented.

Figure 15. a) Handle, b) oriented handle and c) unoriented handle

3.5. Splittable and classical operators. Let us say that a molecular operator X^{n}D^{k}/K is splittable if it can be written in the form of a product

\frac{X^{n}D^{k}}{K} = \frac{X^{n}}{K_{1}} · \frac{D^{k}}{K_{2}}

where K_{1} ≤ 𝕊_{n} and K_{2} ≤ 𝕊_{k}. More generally, any linear combination of splittable operators is called splittable. For example, X^{3}D^{2} and C(X)E_{2}(D)+E(D) are splittable but E(XD) and the operator X^{3}D^{3}/K where K = ⟨ (123)(456) ⟩ ≤ 𝕊_{3,3} are not splittable. Of course, the adjoint of a splittable operator is always splittable. In particular, every Hammond operator H(D) is splittable as well as every multiplication H(X). However, splittable operators are not closed under composition ⊙. To see this, consider the composition of the splittable operators C_{4}(D) and C_{4}(X). Some computations gives

C_{4}(D) ⊙ C_{4}(X) = C_{4}(X)C_{4}(D) + X^{3}D^{3} + 4X^{2}D^{2} + E_{2}(XD) + 6XD + 3,

which is not splittable since

E_{2}(XD) = \frac{X^{2}D^{2}}{⟨ (12)(34) ⟩}

is not.

An important subclass of splittable combinatorial operators are those for which K_{2} = {id}. These operators are closed under ⊙ and form an algebra:

(A(X)D^{k}) ⊙ (B(X)D^{ℓ}) = ∑_{i=0}^{k} \binom{k}{i}A(X)B^{(i)}(X)D^{k+ℓ−i}.

Such operators have been used by Mishna to define a notion of holonomic species [11]. When both subgroups K_{1} and K_{2} are trivial, the corresponding operators are said to be classical. They also form an algebra (using complex coefficients in molecular expansions) under + and ⊙ which is isomorphic to the classical Weyl ℂ-algebra generated by X and D.

3.6. Computations with molecular and atomic differential operators. Recall that every species F (X) can be written (uniquely, up to isomorphism [2]) as a ℕ-linear combination of molecular species X^{n}/H,

F (X) = ∑_{H,n} f_{H} \frac{X^{n}}{H} ,  (34)

where, for each n ≥ 0, H runs through a system of representatives of the conjugacy classes of subgroups of 𝕊_{n} (written H : 𝕊_{n}), and, similarly

Ω(X, T) = ∑_{K,m,k} ω_{K} \frac{X^{m}T^{k}}{K} ,  (35)

where K : 𝕊_{m,k} ≃ 𝕊_{m} × 𝕊_{k}. Hence, the computation of Ω(X, D)F (X) can be reduced, by linearity, to the computation of

\frac{X^{m}D^{k}}{K} \frac{X^{n}}{H} .  (36)

We have the following general reduction formulas from which the computation of (36) can be achieved, using, for example, the GAP software [5].

Theorem 3. For any subgroups H ≤ 𝕊_{n} and K ≤ 𝕊_{m,k}, we have

i) \frac{X^{m}D^{k}}{K} \frac{X^{n}}{H} = \frac{X^{m}T^{k}}{K} ×_{T} \frac{(X + T)^{n}}{H} |_{T:=1},

ii) \frac{(X + T)^{n}}{H} = ∑_{k=0}^{n} ∑_{ω\underline{∈}𝕊_{n−k,k}\𝕊_{n}/H} \frac{X^{n−k}T^{k}}{ωHω^{−1} ∩ 𝕊_{n−k,k}},

iii) \frac{X^{a}T^{k}}{A} ×_{T} \frac{X^{b}T^{k}}{B} = ∑_{τ\underline{∈}(π_{2}A)\𝕊_{k}/(π_{2}B)} \frac{X^{a+b}T^{k}}{A} ×_{𝕊_{k}} B^{τ},

iv) [\frac{X^{a}T^{k}}{A} ]_{T:=1} = \frac{X^{a}}{π_{1}A},

where, ω\underline{∈}H_{1}\𝕊_{p}/H_{2} means that ω runs through a system of representatives of the bilateral cosets H_{1}σH_{2}, σ ∈ 𝕊_{p}; π_{i}G = {g_{i} ∈ 𝕊_{n_{i}} | (g_{1}, g_{2}) ∈ G}, G ≤ 𝕊_{n_{1},n_{2}}; B^{τ} = (id_{[b]}, τ)B(id_{[b]}, τ^{−1}); A ×_{𝕊_{k}} B is the fibered product (pullback) of A by B over 𝕊_{k}.

Proof (Sketch). Formula (i) is immediate by definition. Formula (ii) is a classical addition formula (for more details see [2])). Formula (iii) essentially follows form the fact that the stabilizer of a (X^{a}T^{k}/A) ×_{T} (X^{b}T^{k}/B)-structure s = (s_{1}, s_{2}) on [a, b, k], where s_{1} ∈ (X^{a}T^{k}/A)[a, k] and s_{2} ∈ (X^{b}T^{k}/B)[b, k] is of the form

stab(s_{1}, s_{2}) = {(σ_{1}, σ_{2}, τ) | (σ_{1}, τ) ∈ stab(s_{1}) , (σ_{2}, τ) ∈ stab(s_{2})}
= stab(s_{1}) ×_{𝕊_{k}} stab(s_{2}).

Finally, formula (iv) is a consequence of the fact that if A = stab(s), where s is a X^{n}T^{k}/A-structure, then π_{1}A is the stabilizer of s_{1} where s_{1} is the (X^{n}T^{k}/A)|_{T:=1}- structure associated to s by unlabelling all its underlying elements of sort T. □

A molecular species X^{m}T^{k}/K is said to be an atomic species if it is irreducible under the ordinary (Cauchy) product of species. Atomic species behave as prime numbers since Y. N. Yeh [12] has proved that every molecular species can be written in a unique way (up to isomorphism and order) as a product of atomic species. By convention, the degenerate molecular species 1 is not considered as atomic (to preserve unicity as in the case of prime numbers). The notion of atomicity is extended to combinatorial differential operators in the obvious way :

X^{m}D^{k}/K is atomic if and only if X^{m}T^{k}/K is atomic.  (37)

Hence, to generate all combinatorial differential operators, it is sufficient to consider only the atomic ones and to use products and linear combinations.

Using the GAP software [5], we computed in Table 1 below, all “small” atomic differential operators X^{m}D^{k}/K satisfying m + k ≤ 7. In this table, the subgroups K ≤ 𝕊_{m,k} ≃ 𝕊_{m} × 𝕊_{k} are given in terms of generators. For better readability, these generators are permutations of the set \underbrace{1, 2, 3, …}_{m}; \underbrace{A, B, C, …}_{k} written in cyclic notation.

Our table extends the one given by Chiricota in [4] in which he expresses every molecular species of the form X^{m}/K (K ≤ 𝕊_{m}, m ≤ 7) in terms of quotients of simpler species E_{ν}, C_{ν}, . . ..

3.7. Further extensions of the theory. Allowing coefficients ω_{K} in molecular expansions

Ω(X, D) = ∑ ω_{K}X^{m}D^{k}/K  (38)

to be a real or complex numbers, new very curious identities arise. For example, it can be shown that for any real or complex numbers a, b, we have

E(aXD) ⊙ B(bXD) = E((a + b + ab)XD).  (39)

In particular, E(−XD) is ⊙-idempotent,

E(−XD) ⊙ E(−XD) = E(−XD),  (40)

and E(−2XD) is a ⊙-square root of the identity operator 1,

E(−2XD) ⊙ E(−2XD) = 1.  (41)

Furthermore, E(−\frac{1}{2}XD) has no effect on E(−XD)! Indeed,

E(−\frac{1}{2}XD) ⊙ E(−XD) = E(−XD).  (42)

More generally, making use of multisort species, it is easy to further extend the preceding theory to combinatorial partial differential operators as follows. Consider p sorts of singletons X_{1}, X_{2}, …, X_{p} and denote by ∂_{1}, ∂_{2}, …, ∂_{p} the usual combinatorial partial differential operators

∂_{i} = \frac{∂}{∂X_{i}} , i = 1, 2, …, p.

Given p extra sorts T_{1}, T_{2}, …, T_{p} and a multisort species

Ω(X_{1}, X_{2}, …, X_{p}; T_{1}, T_{2}, …, T_{p}),

we define a corresponding combinatorial partial differential operator

Ω(X_{1}, X_{2}, …, X_{p}; ∂_{1}, ∂_{2}, …, ∂_{p})

acting on species F (X_{1}, X_{2}, …, X_{p}) in the obvious manner:

Ω(X_{1}, X_{2}, …, X_{p}; ∂_{1}, ∂_{2}, …, ∂_{p})F (X_{1}, X_{2}, …, X_{p})

:= Ω(X_{1}, X_{2}, …, X_{p}; T_{1}, T_{2}, …, T_{p})

×_{T_{1},T_{2},...,T_{p}} F (X_{1} + T_{1}, X_{2} + T_{2}, …, X_{p} + T_{p})|_{T_{i}:=1, i=1,2,...,p},

where the partial cartesian product ×_{T_{1},T_{2},...,T_{p}} is defined “componentwise”. The composition operator ⊙ is extended by the formula

Ω_{2}(X_{1}, X_{2}, …, X_{p}; T_{1}, T_{2}, …, T_{p}) ⊙ Ω_{1}(X_{1}, X_{2}, …, X_{p}; T_{1}, T_{2}, …, T_{p}) = Ω_{2}(X_{1}, …, X_{p}; T_{1} + T_{10}, …, T_{p} + T_{p0})

×_{T_{10},...,T_{p0}} Ω_{1}(X_{1} + T_{10}, …, X_{p} + T_{p0}; T_{1}, …, T_{p})|_{T_{i0}:=1, i=1,...,p},

where T_{10}, T_{20}, …, T_{p0} are auxiliary extra sorts of singletons. In this multisort context, molecular and atomic differential operators are of the form

\frac{X_{1}^{m_{1}}X_{2}^{m_{2}} ⋯ X_{p}^{m_{p}}∂_{1}^{k_{1}}∂_{2}^{k_{2}} ⋯ ∂_{p}^{k_{p}}}{K} ,

where K ≤ 𝕊_{m_{1},m_{2},...,m_{p};k_{1},k_{2},...,k_{p}} ≃ 𝕊_{m_{1}} × 𝕊_{m_{2}} × ⋯ × 𝕊_{m_{p}} × 𝕊_{k_{1}} × 𝕊_{k_{2}} ⋯ × 𝕊_{k_{p}}. Hence, every combinatorial partial differential operator Ω(X_{1}, X_{2}, …, X_{p}; ∂_{1}, ∂_{2}, …, ∂_{p}) can be written in the form

Ω(X_{1}, X_{2}, …, X_{p}; ∂_{1}, ∂_{2}, …, ∂_{p}) = ∑ ω_{K} \frac{X_{1}^{m_{1}}X_{2}^{m_{2}} ⋯ X_{p}^{m_{p}}∂_{1}^{k_{1}}∂_{2}^{k_{2}} ⋯ ∂_{p}^{k_{p}}}{K} ,

where the summation is taken over m_{1} ≥ 0, m_{2} ≥ 0, …, m_{p} ≥ 0, k_{1} ≥ 0, k_{2} ≥ 0, …, k_{p} ≥ 0, K : 𝕊_{m_{1},m_{2},...,m_{p};k_{1},k_{2},...,k_{p}} and the coefficients ω_{K} are arbitrary complex numbers.

Moreover, allowing weight variables t, u, v, … acting multiplicatively on structures, the coefficients ω_{K} can be taken in the ring ℂ[[t, u, v, …]]. This means that these combinatorial differential operators form a ring (under “+” and the ordinary product “·”) isomorphic to

ℂ[[t, u, v, …, Atomic]],

where Atomic is the set of all atomic combinatorial partial differential operators. This ring is very rich and is equipped with a multitude of extra operations, ⊙, ×, ˙×, … Not only classical differential operators (e.g. Laplacians ∂_{1}^{2} + ∂_{2}^{2} + ⋯ + ∂_{p}^{2} or symmetric Laplacians E_{2}(∂_{1}) + E_{2}(∂_{2}) + ⋯ + E_{2}(∂_{p})) belong to this ring but also entirely new ones. For example,

C((π + iu)E_{2}(X_{1}∂_{2}) − \frac{3}{4}tE(tX_{2} + ∂_{4})) ∈ ℂ[[t, u, v, …, Atomic]]

where C is the species of oriented cycles. This ring contains a great variety of extra tools for a better understanding, generation, enumeration and classification of structures that appear in algebraic combinatorics.

Table 1. The atomic combinatorial differential operators X^{m}D^{k}/K, for K : 𝕊_{m,k}, m + k ≤ 7.

m = 0, k = 0 Empty, since 1 is non atomic.

m = 1, k = 0 X

m = 0, k = 1 D This is the adjoint of X.

m = 2, k = 0 X^{2}/⟨ (1, 2) ⟩

m = 1, k = 1 Empty, since XD factorizes.

m = 0, k = 2 D^{2}/⟨ (A, B) ⟩ This is the adjoint of X^{2}/⟨ (1, 2) ⟩.

m = 3, k = 0 X^{3}/⟨ (123) ⟩ X^{3}/⟨ (132), (12) ⟩

m = 2, k = 1 Empty, since D is a factor of every molecular species X^{2}D/K.

m = 1, k = 2 Empty, since X is a factor of every molecular species XD^{2}/K.

m = 0, k = 3 D^{3}/⟨ (ABC) ⟩ D^{3}/⟨ (ACB), (AB) ⟩ These are the adjoints of the case m = 3, k = 0.

m = 4, k = 0 X^{4}/⟨ (13)(24) ⟩ X^{4}/⟨ (14)(23), (13)(24) ⟩ X^{4}/⟨ (12)(34), (1324) ⟩ X^{4}/⟨ (13)(24), (14)(23), (12) ⟩ X^{4}/⟨ (13)(24), (14)(23), (243) ⟩ X^{4}/⟨ (13)(24), (14)(23), (243), (12) ⟩

m = 3, k = 1 Empty, since D is a factor of every molecular species X^{3}D/K.

m = 2, k = 2 X^{2}D^{2}/⟨ (12)(AB) ⟩ ( self-adjoint )

m = 1, k = 3 Empty, since X is a factor of every molecular species XD^{3}/K.

m = 0, k = 4 Take the adjoints of the case m = 4, k = 0.

m = 5, k = 0 X^{5}/⟨ (12345) ⟩ X^{5}/⟨ (345), (12)(45) ⟩ X^{5}/⟨ (12345), (25)(34) ⟩ X^{5}/⟨ (12345), (25)(34), (2354) ⟩ X^{5}/⟨ (12345), (345) ⟩ X^{5}/⟨ (12345), (12) ⟩

m = 4, k = 1 Empty, since D is a factor of every molecular species X^{4}D/K.

m = 3, k = 2 X^{3}D^{2}/⟨ (132), (12)(AB) ⟩

m = 2, k = 3 X^{2}D^{3}/⟨ (ACB), (AB)(12) ⟩ This is the adjoint of the case m = 3, k = 2.

m = 1, k = 4 Empty, since X is a factor of every molecular species XD^{4}/K.

m = 0, k = 5 Take the adjoints of the case m = 5, k = 0.

m = 6, k = 0 X^{6}/⟨ (12)(34)(56) ⟩ X^{6}/⟨ (123)(456) ⟩ X^{6}/⟨ (34)(56), (12)(56) ⟩ X^{6}/⟨ (34)(56), (12)(3546) ⟩ X^{6}/⟨ (34)(56), (12)(35)(46) ⟩ X^{6}/⟨ (123)(456), (14)(26)(35) ⟩ X^{6}/⟨ (123)(456), (23)(56) ⟩ X^{6}/⟨ (12)(34)(56), (135)(246) ⟩ X^{6}/⟨ (56), (34), (12)(35)(46) ⟩ X^{6}/⟨ (34)(56), (35)(46), (12)(56) ⟩ X^{6}/⟨ (34)(56), (3546), (12)(56) ⟩ X^{6}/⟨ (34)(56), (12)(56), (135)(246) ⟩ X^{6}/⟨ (12)(34)(56), (135)(246), (35)(46) ⟩ X^{6}/⟨ (456), (123), (23)(56) ⟩ X^{6}/⟨ (456), (123), (14)(25)(36) ⟩ X^{6}/⟨ (56), (34), (12), (135)(246) ⟩ X^{6}/⟨ (34)(56), (35)(46), (456), (12)(56) ⟩ X^{6}/⟨ (34)(56), (12)(56), (135)(246), (35)(46) ⟩ X^{6}/⟨ (34)(56), (12)(56), (135)(246), (3546) ⟩ X^{6}/⟨ (456), (123), (23)(56), (14)(25)(36) ⟩ X^{6}/⟨ (456), (123), (23)(56), (14)(2536) ⟩ X^{6}/⟨ (56), (34), (12), (145)(236), (35)(46) ⟩ X^{6}/⟨ (12346), (14)(56) ⟩ X^{6}/⟨ (456), (46), (123), (23), (14)(25)(36) ⟩ X^{6}/⟨ (15364), (16)(24), (3465) ⟩ X^{6}/⟨ (12345), (456) ⟩ X^{6}/⟨ (123456), (12) ⟩

m = 5, k = 1 Empty, since D is a factor of every molecular species X^{5}D/K.

m = 4, k = 2 X^{4}D^{2}/⟨ (13)(24)(AB) ⟩ X^{4}D^{2}/⟨ (13)(24), (14)(23)(AB) ⟩ X^{4}D^{2}/⟨ (12)(34), (34)(AB) ⟩ X^{4}D^{2}/⟨ (12)(34), (1324)(AB) ⟩ X^{4}D^{2}/⟨ (13)(24), (14)(23), (12)(AB) ⟩ X^{4}D^{2}/⟨ (12)(34), (13)(24)(AB), (1324) ⟩ X^{4}D^{2}/⟨ (12)(34), (13)(24)(AB), (34) ⟩ X^{4}D^{2}/⟨ (13)(24), (14)(23), (243), (12)(AB) ⟩

m = 3, k = 3 X^{3}D^{3}/⟨ (132)(ACB) ⟩ ( self-adjoint ) X^{3}D^{3}/⟨ (132)(ACB), (23)(BC) ⟩ ( self-adjoint ) X^{3}D^{3}/⟨ (132), (ACB), (12)(AB) ⟩ ( self-adjoint )

m = 2, k = 4 Take the adjoints of the case m = 4, k = 2.

m = 1, k = 5 Empty, since X is a factor of every molecular species XD^{5}/K.

m = 0, k = 6 Take the adjoints of the case m = 6, k = 0.

m = 7, k = 0 X^{7}/⟨ (567), (12)(34)(67) ⟩ X^{7}/⟨ (1234567) ⟩ X^{7}/⟨ (34567), (12)(47)(56) ⟩ X^{7}/⟨ (45)(67), (46)(57), (123)(567) ⟩ X^{7}/⟨ (567), (34)(67), (12)(67) ⟩ X^{7}/⟨ (567), (12)(34), (13)(24)(67) ⟩ X^{7}/⟨ (567), (12)(34), (1324)(67) ⟩ X^{7}/⟨ (1234567), (27)(36)(45) ⟩ X^{7}/⟨ (34567), (47)(56), (12)(4576) ⟩ X^{7}/⟨ (1234567), (235)(476) ⟩ X^{7}/⟨ (567), (34)(67), (12)(67), (13)(24)(67) ⟩ X^{7}/⟨ (67), (45), (123), (23)(46)(57) ⟩ X^{7}/⟨ (567), (34)(67), (12)(67), (13)(24) ⟩ X^{7}/⟨ (45)(67), (46)(57), (123)(567), (23)(67) ⟩ X^{7}/⟨ (1234567), (235)(476), (27)(36)(45) ⟩ X^{7}/⟨ (567), (14)(23), (12)(34), (234), (34)(67) ⟩ X^{7}/⟨ (12345), (345), (45)(67) ⟩ X^{7}/⟨ (1234567), (12)(36) ⟩ X^{7}/⟨ (1234567), (567) ⟩ X^{7}/⟨ (1234567), (12) ⟩

m = 6, k = 1 Empty, since D is a factor of every molecular species X^{6}D/K.

m = 5, k = 2 X^{5}D^{2}/⟨ (345), (12)(45)(AB) ⟩ X^{5}D^{2}/⟨ (12345), (25)(34)(AB) ⟩ X^{5}D^{2}/⟨ (45)(AB), (123), (23)(AB) ⟩ X^{5}D^{2}/⟨ (12345), (25)(34), (2354)(AB) ⟩ X^{5}D^{2}/⟨ (125), (142), (234), (45)(AB) ⟩

m = 4, k = 3 X^{4}D^{3}/⟨ (13)(24)(BC), (ABC) ⟩ X^{4}D^{3}/⟨ (14)(23), (13)(24)(BC), (ABC) ⟩ X^{4}D^{3}/⟨ (13)(24), (14)(23), (243)(ACB) ⟩ X^{4}D^{3}/⟨ (12)(34), (1324)(BC), (ABC) ⟩ X^{4}D^{3}/⟨ (12)(34), (34)(BC), (ABC) ⟩ X^{4}D^{3}/⟨ (13)(24), (14)(23), (12)(BC), (243)(ACB) ⟩ X^{4}D^{3}/⟨ (13)(24), (14)(23), (12)(BC), (ACB) ⟩ X^{4}D^{3}/⟨ (12)(34), (13)(24)(BC), (ABC), (34) ⟩ X^{4}D^{3}/⟨ (12)(34), (13)(24)(BC), (ABC), (1324) ⟩ X^{4}D^{3}/⟨ (13)(24), (14)(23), (ABC), (243), (12)(BC) ⟩

m = 3, k = 4 Take the adjoints of the case m = 4, k = 3.

m = 2, k = 5 Take the adjoints of the case m = 5, k = 2.

m = 1, k = 6 Empty, since X is a factor of every molecular species XD^{6}/K.

m = 0, k = 7 Take the adjoints of the case m = 4, k = 3.

References

[1] Auger P., Labelle G. and Leroux P., Combinatorial addition formulas and applications, Adv. Appl. Math. 28 (2002), 302–342.

[2] Bergeron F., Labelle G. and Leroux P., Combinatorial species and tree-like structures, in: Encyclopedia of Mathematics and Its Applications, vol. 67, Cambridge University Press (1998).

[3] Bodirsky M., Fusy E., Kang M. and Vigerske S., An unbiased pointing operator for unlabelled structures, with applications to counting and sampling, in: Proceedings of the 18-th ACM–SIAM Symposium on Discrete Algorithms, New Orleans (2007), 356–365.

[4] Chiricota Y., Classification des espèces moléculaires de degré 6 et 7, Annales des sciences mathématiques du Québec 17 (1993), 11–37.

[5] The GAP Group, GAP — Groups, Algorithms, and Programming, Version 4.4.10 (2007)

(http://www.gap-system.org).

[6] Gessel I., Enumerative applications of symmetric functions, Proceedings of the 17-th Séminaire Lotharingien de Combinatoire, Publ. I.R.M.A. Strasbourg (1987), 229/S-08, 5–21.

[7] Gessel I. and Labelle G., Lagrange Inversion for Species, J. Combin. Theory Ser. A 72 (1995) 95–117.

[8] Joyal A., Une théorie combinatoire des séries formelles, Adv. Math. 42 (1981), 1–82.

[9] Joyal A., Foncteurs analytiques et espèces de structures, in: Combinatoire Énumérative, Proceedings, Montréal, Lecture Notes in Math., vol. 1234, Springer–Verlag, Berlin (1986), 126–159.

[10] Labelle G., Eclosions combinatoires appliquées à l’inversion multidimensionnelle des séries formelles, J. Combin. Theory Ser. A, 39 (1985), 52–82.

[11] Mishna M., An Holonomic Approach to Algebraic Combinatorics, Monographie du LaCIM, 34, Université du Québec à Montréal (2005).

[12] Yeh Y.N., The calculus of virtual species and 𝕂-species, in: Combinatoire Énumérative, Proceedings, Montréal, Québec, Lecture Notes in Math., vol. 1234, Springer–Verlag, Berlin (1986), 351–369.