Séminaire Lotharingien de Combinatoire 61A (2010), Article B61Al

ECO SPECIES^{∗}

LUCA FERRARI^{†} AND PIERRE LEROUX

Abstract. We introduce the notion of ECO species, by means of which we are able to translate the ECO method into the language of (linear) species. We then define many operations on ECO species, reflecting the most common operations on the associated generating functions, and give examples illustrating such operations.

1. Introduction

The ECO methodology [BDLPP1] is a technique often used in enumerative combinatorics and in the (random and exhaustive) generation of combinatorial structures. Roughly speaking, if we consider a class of combinatorial objects together with a notion of size, given an object of size n, an ECO construction is a purely combinatorial rule which allows to produce a set of objects of size n + 1 in such a way that every objects of size n+1 is generated exactly once starting from some object of size n. When the construction is regular enough, it is often possible to describe it using a succession rule [W] or a generating tree [CGHK]. However, the two methods (ECO and succession rules) are not equivalent, meaning that certain problems can be suitably tackled by using one of the two methods but not the other one. To support this statement, consider the following examples.

• Sometimes it is possible to find an ECO construction but not to encode it by means of a succession rule. For instance, an ECO construction for twodimensional directed animals has been described in [BDLPP2] but it is still not clear if such a construction can be translated into a succession rule. The same situation holds for directed animals on the hexagonal lattice.

• Sometimes we know the succession rule but we are not able to describe the related ECO construction. Consider, for instance, the following jumping succession rule:

Ω : \{ \begin{matrix}(1) \\ (h) & ⇝^{+2} (h + 2) \\ & ⇝^{+h} (h) \end{matrix} .

2010 Mathematics Subject Classification. Primary 05A15; Secondary 05A99, 05A19, 68R05.

∗This work originates from some ideas developed when Pierre Leroux was visiting the “Dipartimento di Sistemi e Informatica” of the University of Firenze, in the April of 2002. During the two weeks Pierre remained in Italy, we essentially fixed the main ideas and definitions and worked out a couple of examples. After the untimely death of Pierre, I decided to try completing our work, by providing the necessary technical details and by supplying a greater amount of examples. Thus, I deem to be able to assert for sure that all the good ideas of the present paper have the marks of both Pierre and myself, whereas any possible mistake or oversight must be certainly ascribed to myself alone. (L.F.)

†Dipartimento di Sistemi e Informatica, viale Morgagni 65, 50134 Firenze, Italy ferrari@dsi.unifi.it.

Here a superscript +a indicates that, if a node lies at level n of the generating tree, then the related production consists of nodes lying at level n + a (see [FPPR2]). It is known [FPR] that Ω describes an ECO construction for integer partitions into odd parts, so it also gives a construction for partitions into distinct parts. However, this last construction is presently unknown. Observe that, as remarked in [FPR], if one succeeds in finding such a construction, then necessarily a label (h) would represent a lecture hall partition of minimum length \frac{h−1}{2} (see [BE] for the definition of a lecture hall partition).

• Some ECO constructions are described by very complicated succession rules, so that it is extremely difficult to use the rule to enumerate the objects under consideration. For instance, denoting by S(123 ⋯ k) the set of permutations avoiding the pattern 123 ⋯ k, in [G] an ECO construction for S(123 ⋯ k) is determined, which can be described by an explicit succession rule, but such a rule is too complicated to find |S_{n}(123 ⋯ k)|, for a generic k.

In spite of the fact that the two methodologies are not equivalent, the advantages of having a succession rule describing an ECO construction are obvious. Moreover, any known attempt of providing a rigorous mathematical framework for ECO (for instance rule operators [FP] or production matrices [DFR]) actually consists of the formalization of the notion of succession rule. In the present paper our aim is to come back to the original combinatorial roots of ECO, by developing a theory which describes an ECO construction in the framework of (linear) species without making any use of succession rules. The basic idea which makes this possible is a very simple observation. An ECO construction consists essentially of an operator ϑ mapping the set O_{n} of the objects of size n of a given class to the set 2^{O_{n+1}} of subsets of O_{n+1}. However, regarding things from the complementary point of view, ϑ induces a function ψ : O_{n+1} ⟶ O_{n} which maps an object to its “father”. This simple observation allows us to relate O_{n} and O_{n+1} in a more direct way (that is, without using the notion of power set). A suggestive consequence of this “reversed” approach is the possibility of interpreting the ECO method inside the theory of (linear) species.

The notion of combinatorial species goes back to Joyal [J] and is nowadays a very widely employed notion in enumerative and algebraic combinatorics. A fairly complete exposition of the theory of species can be found in [BLL].

In Section 3 we introduce the notion of ECO species, which is, by definition, a pair (F, p), where F is a linear species and p : F′ ⟶ F is a natural transformation. The role of p is to describe the function ψ mentioned above. In the spirit of species theory, we show that the class of ECO species can be endowed with many common operations, like sum, product, composition and so on. This last statement means that, if (F, p), (G, q) are ECO species and □ is an operation such that F □G is a linear species, then it is possible to define a natural transformation p□q : (F □G)′ ⟶ F □G such that (F □G, p□q) is an ECO species. For any operation we consider, we will give an illustrative example. Our idea is to provide elementary examples, in order to better clarify our theory, leaving more sophisticated applications to possible future works. Moreover, some efforts will be spent to relate our approach with that developed in [FPPR1, PPR1], namely we will try to see what is the resulting succession rule when each of our operations on ECO species is performed (under the hypothesis that the starting ECO species do have a description in terms of succession rules); we will see that in some cases we get to known results, whereas, in some other cases, the problem of finding the resulting succession rule remains open. In the specific case of ordinal substitution, our result is believed to be new.

In closing this introduction, we would like to add a final remark. After a first reading of the above considerations, one would think that the link between the ECO methodology and the theory of species would only result in a better understanding of the mathematical foundations of ECO. With this interpretation, the advantages of having a connection between the two theories would simply result in an improvement of only one of them. On the contrary, we deem that our approach could be of great interest also for the theory of species, since it is the first rigorous attempt of giving a formal meaning to some notion of “combinatorially interesting (linear) species”. This is achieved with the definition of a natural transformation which provides a link between structures of the same species having different cardinalities. In order to better clarify this statement, consider a linear species F such that the sets of F -structures of different cardinalities has nothing in common from a purely combinatorial point of view. For instance, F could be the linear species consisting of set partitions of a set of cardinality 0, permutations of a set of cardinality 1, sets of cardinality 2, Dyck paths of semilength 3, Motzkin paths of length 4, binary trees having 5 nodes, posets having 6 elements, octopuses having 7 nodes, etc. This species has absolutely no interest from a combinatorial point of view, nevertheless its definition is formally correct. The theory of ECO species provides a framework in which such examples are automatically pulled out, due to the presence of a natural transformation which requires a deep combinatorial relationship between the sets of structures of the same species whose cardinalities differ by a specific quantity. In terms of species, this can be considered an attempt to capture a notion of hereditarity which would surely bring species theory nearer to its combinatorial roots.

2. Preliminaries

Let l be a linearly ordered set. If π is a partition of (the underlying set of) l, we can introduce a linear order on the set of its blocks in a very natural way. If B_{i}, B_{j} are blocks of π, say that B_{i} ≤ B_{j} when min B_{i} ≤ min B_{j}. Therefore we can speak of the linearly ordered set of the blocks of any given partition. When considering a partition of l, we will always assume that its blocks are linearly ordered according to the above. We will denote P(l) the set of all partitions of l.

If l, m are two linearly ordered sets, the ordinal sum l +_{O} m is defined to be the linearly ordered set whose underlying set is the disjoint union of the underlying sets of l and m and such that x ≤ y if and only if either x ≤ y in l or x ≤ y in m or x ∈ l and y ∈ m. For example, the linearly ordered set l +_{O} 1 is obtained from l by simply adding a new maximum. Such a linearly ordered set will very frequently occur in the sequel, so we use for it a special symbol: l^{+} = l +_{O} 1.

An ordered partition of a linearly ordered set l is a partition π = {B_{1}, … B_{k}} of l such that l = B_{1} +_{O} ⋯ +_{O} B_{k} (that is, a partition of l into intervals). The set of all ordered partitions of l will be denoted PL(l).

Let 𝔼, 𝕃 denote the categories of finite sets and functions and of finite linearly ordered sets and increasing bijections, respectively. A linear species is a functor F : 𝕃 ⟶ 𝔼. This means, by definition, that: i) for any (finite) linearly ordered set l, F [l] is a (finite) set; ii) for any increasing bijection γ : l_{1} ⟶ l_{2}, F [γ] : F [l_{1}] ⟶ F [l_{2}] is a function such

that

F [1_{l}] = 1_{F [l]}, F [β ∘ γ] = F [β] ∘ F [γ],

where 1_{X} denotes the identity function on the set X and β : l_{2} ⟶ l_{3} is an increasing bijection.

Observe that the category 𝕃 has a simple structure, since increasing bijections between totally ordered sets are unique.

The elements of F [l] are then called F -structures, and the functions F [γ] transport functions. Observe that, as an immediate consequence of the above definition, every transport function is a bijection.

We say that a linear species F has order n_{0} when F [l] = ∅, for every l of cardinality < n_{0}, and F [l] ≠ ∅ when |l| = n_{0}. The order of a linear species F will be denoted by o(F).

Given a linear species F of order n_{0}, the exponential generating function associated with F is the formal power series F (x) = ∑_{n≥n_{0}} a_{n} \frac{x^{n}}{n!} such that a_{n} = |F [l]|, where l is a linearly ordered set having n elements. We will also consider the ordinary generating function associated with F, that is the series f(x) = ∑_{n≥n_{0}} a_{n}x^{n}.

The class of linear species can be endowed with many operations (sum, product, Cartesian product, substitution,...), whose combinatorial definitions can be found in [BLL]. However, such definitions will be formulated in the next sections. The only one we need to introduce now is that of derivative of a linear species. If F is a linear species of order n_{0}, the derivative of F is, by definition, the linear species F′ defined by F′[l] = F [l^{+}]. It is clear that F′ is a linear species of order n_{0} − 1.

In closing this section, we would like to remark that our use of the equality sign “=” depends on the context. Indeed, we will freely use it to denote (ECO) species isomorphism. The reader will easily deduce its meaning from the context.

3. Main definitions

An ECO species of order n_{0} is a pair (F, p), where F : 𝕃 ⟶ 𝔼 is a linear species of order n_{0} and p : F′ ⟶ F is a natural transformation (here F′ is assumed to be defined only on linearly ordered sets of cardinality ≥ n_{0}). F will be called the support and p the operator of the ECO species (F, p).

Thus the natural transformation p is a set of functions (p_{l})_{l∈Ob(𝕃)} such that p_{l} : F [l^{+}] ⟶ F [l]. This means that p_{l} maps any F -structure on l^{+} into an F -structure on l. Roughly speaking, p_{l} removes the top element of the underlying set of a given F -structure and reorganizes the remaining elements into another F -structure. Recall that, for a category ℂ, Ob(ℂ) and Mor(ℂ) denotes the objects and the morphisms of ℂ, respectively.

As already remarked in the introduction, the idea behind the definition of an ECO species is that the operator of an ECO species represents the combinatorial realization of the operator which maps a node of a generating tree to its father. However, we notice here that our definition of an ECO species is a little bit more general than the notion of ECO construction. In fact, when a class of combinatorial objects is generated by means of an ECO construction, it is always assumed that there is only one structure of minimum cardinality. Therefore, such a construction can be described by a suitable generating tree, in which the root encodes the (unique) object of minimum size. In terms of ECO species, this means that the linear species F under consideration is such that, if |l| = o(F), then |F [l]| = 1. Instead, by using our definition of an ECO species, we are able to consider classes of combinatorial objects having several objects of minimum size. Moreover, we are also able to formalize the construction of classes of objects whose “root objects” have different sizes. In particular, this means that the graphical representation of our constructions is not merely a generating tree, but more generally a generating forest, whose roots can lie at different levels. In such a case, the associated succession rule (if any) has several axioms, and, for each of them, a positive integer must be specified, representing its “depth” in the generating forest. In order to express this fact, a generic succession rule having r + 1 axioms lying at levels n_{0}, n_{1}, …, n_{r}, respectively, will be written as follows:

Ω : \{ \begin{matrix}(a_{0})_{n_{0}}; ⋯; (a_{r})_{n_{r}} \\ (k) ⇝ (e_{1}(k)) ⋯ (e_{k}(k)) \end{matrix} .

Let (F, p), (G, q) be two ECO species having orders n_{0} and m_{0} = n_{0} + k, respectively. Given a linearly ordered set l, with |l| = h, we denote by l̂ a linearly ordered set such that |l̂| = h + k. An ECO isomorphism φ : (F, p) ⟶ (G, q) is a family of bijections (φ_{(l,l̂)})_{(l,l̂)} such that, for every l, the following diagram is commutative:

\xymatrix{F′[l] \ar[d]_{φ′_{(l,l̂)}} \ar[r]^{p_{l}} & F [l] \ar[d]^{φ_{(l,l̂)}} \\ G′[l̂] \ar[r]_{ql̂} & G[l̂]}

where, by definition, φ′_{(l,l̂)} = φ_{(l^{+},l̂^{+})}.

4. Operations on ECO species

The present section is the heart of our paper. Here we will show that, for several usual operations on linear species, it is possible to define analogous operations on ECO species.

At this point, an important remark is in order. In performing an ECO construction, a new maximum is added to l and the resulting linearly ordered set l^{+} is endowed with a suitable structure. Thus, if we describe an ECO construction in the language of ECO species, we are required to remove the maximum of l^{+} and endow l with a suitable structure. In the definition of some common operations on linear species, the underlying linearly ordered set l is partitioned into subsets. Therefore, it can well happen that the maximum of l^{+} belongs to a subset of l^{+} of minimum cardinality with respect to the species it is endowed with. It is then clear that we cannot simply remove such a maximum; instead, we have somehow to modify the starting partition to get a satisfactory definition. In what follows we will always try to completely define the natural transformation p□q on all structures, even if, in some cases, we will just outline the construction, leaving to the reader the task of providing all details.

4.1. Derivative. Let (F, p) be an ECO species of order n_{0}. It is a straightforward verification to check that p′ : F′′ ⟶ F′ defined by p′_{l} = p_{l^{+}} is a natural transformation. The ECO species (F′, p′) (of order max(0, n_{0} − 1) ) is called the derivative of (F, p).

We recall that the exponential generating function of F′ is simply the derivative of that of F: F′(x) = \frac{d}{dx}F (x). As far as the ordinary generating function is concerned, we have the obvious equality f′(x) = \frac{f(x)−f(0)}{x}.

In terms of succession rules, denoting by Ω the succession rule (if it exists) associated with (F, p), then the succession rule associated with (F′, p′) is obtained from Ω by replacing all the axioms at level 0 with the sets of sons they produce and by decreasing by 1 the levels of all the remaining axioms of Ω.

Example. Let P ermF ix be the linear species of permutations whose last element is fixed and equal to the maximum. The order of F is 1. Consider the natural transformation move which maps any permutation π of n elements into the permutation move(π) obtained from π by removing n and moving n − 1 to the last position. Thus, if, for instance, π = 34125, then move(π) = 3124. It is easy to see that (P ermF ix, move) is an ECO species, whose associated succession rule is

Ω : \{ \begin{matrix}(1)_{1} \\ (k) ⇝ (k + 1)^{k} \end{matrix} .

Indeed, if a permutation π has length n, it is immediate to see that it produces precisely n sons.

The derivative of (P ermF ix, move) is given by the ECO species (of order 0) (P erm, max), where P erm is the linear species of permutations and max is the natural transformation mapping a permutation into the one obtained by simply removing the maximum. The interested reader will find quite easy to prove that P erm = P ermF ix′ and max = move′. The succession rule associated with (P ermF ix, move) is then obtained from Ω by replacing the axiom (1)_{1} with (1)_{0}.

4.2. Sum. Let (F, p), (G, q) be two ECO species having orders n_{0} and m_{0}, respectively. The linear species F + G is defined by

(F + G)[l] = F [l] + G[l],

where A + B denotes the disjoint union of the sets A and B.

Both the exponential and the ordinary generating functions of the sum are easily derived from those of the summand, since we have (F + G)(x) = F (x) + G(x) and (f + g)(x) = f(x) + g(x).

For any linearly ordered set l, |l| ≥ min(n_{0}, m_{0}), consider the function (p + q)_{l} : (F + G)′[l] ⟶ (F + G)[l] mapping F′[l] to F [l] through p and G′[l] to G[l] through q.

Proposition 4.1. p + q : (F + G)′ ⟶ F + G is a natural transformation.

Proof. Take two linearly ordered sets l, m and a morphism (that is, an increasing bijection) α : l ⟶ m. Our goal is to prove that the following diagram is commutative:

\xymatrix{(F + G)′[l] \ar[d]_{(F +G)′[α]} \ar[r]^{(p+q)_{l}} & (F + G)[l] \ar[d]^{(F +G)[α]} \\ (F + G)′[m] \ar[r]_{(p+q)_{m}} & (F + G)[m]}

If we consider an F′-structure on l, then the commutativity of the above diagram is equivalent to the identity F [α] ∘ p_{l} = p_{m} ∘ F′[α], which is true since p is a natural transformation. Analogously, if we take a G′-structure on l, we have to show that G[α]∘ q_{l} = q_{m} ∘ G′[α], and this is the same as saying that q is a natural transformation. □

The sum (F, p) + (G, q) is, by definition, the ECO species (F + G, p + q) of order min(n_{0}, m_{0}).

When the two ECO species under consideration can be encoded by suitable succession rules, the ECO species (F +G, p+q) can be described by the sum of the two succession rules related to (F, p) and (G, q) essentially as it is defined (in the case of “classical” succession rules) in [PPR1, FPPR1]. More precisely, if (F, p) and (G, q) are associated respectively with the two succession rules Ω and Σ given by

(1)  Ω : \{ \begin{matrix}(a_{0})_{n_{0}}; ⋯; (a_{r})_{n_{r}} \\ (k) ⇝ (e_{1}(k)) ⋯ (e_{k}(k)) \end{matrix}  Σ : \{ \begin{matrix}(b_{0})_{m_{0}}; ⋯; (b_{s})_{m_{s}} \\ (k) ⇝ (c_{1}(k)) ⋯ (c_{k}(k)) \end{matrix} ,

then (F + G, p + q) is described by the succession rule

Ω + Σ : \{ \begin{matrix}(a_{0})_{n_{0}}; ⋯; (a_{r})_{n_{r}}; (\overline{b_{0}})_{m_{0}}; ⋯; (\overline{b_{s}})_{m_{s}} \\ (h) ⇝ (e_{1}(h)) ⋯ (e_{h}(h)) \\ (\overline{k}) ⇝ (\overline{c_{1}(k)}) ⋯ (\overline{c_{k}(k)}) \end{matrix} .

Here overlined labels can be interpreted as coloured labels, see [FPPR1].

Example. Define the species DP_{3} of 3-bounded Dyck prefixes to be the species whose objects are the paths of finite, even length starting from the origin of a fixed Cartesian coordinate system, using only steps u = (1, 1) and d = (1, −1) and contained in the horizontal string delimited by the two lines x = 0 and x = 3 (see figure 1). Alternatively, given a linearly ordered set l, with |l| = n ≥ 1, an element of DP_{3}[l] can be represented as an n-dimensional vector whose components are the positions of the up steps of the path, with the convention that, if the vector represents a Dyck path, then the last component is set equal to 0. Referring again to figure 1, the corresponding vector is (1, 2, 4, 7, 8, 9, 11, 14, 16); instead, the 4-dimensional vector (1, 3, 4, 0) represents the (Dyck) path uduudd. Using this language, the length of a path in DP_{3}[l] is 2n − 2. The order of DP_{3} is clearly 1. Consider the natural transformation peak : DP′_{3} ⟶ DP_{3} defined as follows:

• if P is a nonempty Dyck path, then remove its last peak;

• if P is not a Dyck path, then remove its first peak, if any.

Figure 1. A 3-bounded Dyck prefix of length 16.

To prove that the pair (DP_{3}, peak) is actually an ECO species we will show that it can be expressed as the sum of two ECO species.

Let Dyck_{3} be the species of 3-bounded Dyck paths and P ref_{3} the species of 3bounded Dyck prefixes ending at height 2. There is a known ECO-construction for Dyck_{3}-structures, described for instance in [PPR2]: given a 3-bounded Dyck path, add a new peak in any point of the last sequence of down steps, provided that the obtained path remains below the line x = 3. This construction can be encoded by the following succession rule:

Ω : \{ \begin{matrix}(1)_{1} \\ (1) ⇝ (2) \\ (2) ⇝ (2)(3) \\ (3) ⇝ (2)(3)(3) \end{matrix} .

The natural transformation lastpeak which removes the last peak of the path is the operator of the ECO species (Dyck_{3}, lastpeak) determined by Ω.

Analogously, a possible ECO-construction for P ref_{3}-structures consists of adding a new peak in any point of the first sequence of up steps, provided that the same warning as above is taken into account. Also this construction can be described by means of a suitable succession rule, which is very similar to the above one:

Σ : \{ \begin{matrix}(3)_{2} \\ (2) ⇝ (2)(3) \\ (3) ⇝ (2)(3)(3) \end{matrix} .

Similarly as before, the operator of the ECO species (P ref_{3}, firstpeak) acts by deleting the first peak of the path, if any.

The two ECO species (Dyck_{3}, lastpeak) and (P ref_{3}, firstpeak) have orders 1 and 2, respectively.

It is now easy to see that

(DP_{3}, peak) = (Dyck_{3}, lastpeak) + (P ref_{3}, firstpeak),

which proves that (DP_{3}, peak) is indeed an ECO species (of order 1).

4.3. Product. The product of two linear species F and G is defined exactly in the same way as for ordinary species, that is

(F · G)[l] = ∑_{l_{1}+l_{2}=l} F [l_{1}] × G[l_{2}].

As mentioned in [BLL], for the product of two linear species the Leibniz rule holds.

Proposition 4.2. If F, G are any two linear species, then we have

(F · G)′ = F′ · G + F · G′.

Proof (sketch). An (F ·G)′-structure on l is an (F ·G)-structure on l^{+}, which is, in turn, an F -structure on a subset l_{1} of l^{+} together with a G-structure on the complement l_{2} of l_{1} in l^{+}. Depending on whether the maximum of l^{+} belongs to l_{1} or l_{2}, such a structure is indeed an (F′ · G)-structure or an (F · G′)-structure on l, respectively. □

Observe that, as far as the exponential generating functions are concerned, we get (F · G)(x) = F (x) · G(x).

Now consider two ECO species (F, p), (G, q) of orders n_{0} and m_{0}, respectively. We define a natural transformation p · q : (F · G)′ ⟶ F · G as follows. First of all, use Proposition 4.2 to map (F ·G)′ to F′·G+F ·G′. Next consider the natural transformation from F′ ·G+F ·G′ to F ·G defined in the following way. If X is an (F′ ·G)-structure on l, then there exist l_{1}, l_{2} such that l_{1} + l_{2} = l and X consists of an F -structure on l_{1}^{+} and a G-structure on l_{2}. If we apply the natural transformation p to the F -part of X, then we obtain an (F · G)-structure on l. On the other hand, if X is an (F · G′)-structure on l, then we can argue in a similar way to obtain an (F · G)-structure on l. Therefore, putting things together, we have defined a transformation p · q from (F · G)′ to F · G.

Observe that, strictly speaking, the above construction works only if the top element of l^{+} belongs to a suitable subset. Indeed, if, for instance, it belongs to l_{1} and l_{1} bears a minimal F -structure, we are not able to apply the natural transformation p. However, in such a case, it is not difficult to find an alternative construction: just apply q to l_{2} (by removing the top element of l_{2}) and suitably rename the remaining elements of l (details are left to the reader).

Proposition 4.3. p · q : (F · G)′ ⟶ F · G is a natural transformation.

Proof. Given α : l ⟶ m, we have to show that the following is commutative:

\xymatrix{(F · G)′[l] \ar[d]_{(F ·G)′[α]} \ar[r]^{(p·q)_{l}} & (F · G)[l] \ar[d]^{(F ·G)[α]} \\ (F · G)′[m] \ar[r]_{(p·q)_{m}} & (F · G)[m]}

Recall that (F · G)′[α] = (F · G)[α + 1], where α + 1 : l^{+} ⟶ m^{+} is the unique order-preserving bijection which extends α. Given X ∈ (F · G)′[l], suppose (without loss of generality) that the top element of l^{+} belongs to the F -part of X. Applying (F · G)′[α] implies that the top element of l^{+} is mapped into the top element of m^{+}, thus this last element indeed belongs to the F -part of (F · G)′[α](X). Now the natural transformation (p · q)_{m} simply consists of applying p to (F · G)′[α](X). It is not difficult to realize that the same result can be obtained by first applying p to X (thus removing the top element of l^{+}) and then renaming the elements of the obtained structure using (F · G)[α]. □

Using the above proposition, we can define an ECO species (F · G, p · q) of order n_{0} + m_{0}: it will be called the product of the two ECO species (F, p) and (G, q).

Example. Let (Dyck, lastpeak) be the ECO species of Dyck paths, where the operator lastpeak maps a given Dyck path to the Dyck path obtained by removing the last peak. The succession rule describing this ECO species is

\{ \begin{matrix}(1)_{0} \\ (k) ⇝ (2)(3) ⋯ (k)(k + 1) \end{matrix} .

Analogously to what we observed in a preceding example, the linear species Dyck can be conveniently represented as follows: for any linear order l of cardinality n, Dyck[l] is the set of all vectors having n components such that the i-th component is the position of the i-th up step in the corresponding Dyck path. Thus, for example, (1, 2, 5) encodes the Dyck path uuddud.

Let (E, elem) be the ECO species of sets, where the operator elem simply deletes the maximum element of a set. The succession rule describing such an ECO species is then obviously

\{ \begin{matrix}(1)_{0} \\ (1) ⇝ (1) \end{matrix} .

Both the ECO species defined above have order 0. We can consider the product (Dyck · E, lastpeak · elem), and look for a simple combinatorial description of it. Consider the linear species Schr(dh^{2}) of Schröder paths (i.e., lattice paths starting from (0, 0), ending on the x-axis, never falling below the x-axis and using steps u = (1, 1), d = (1, −1) and h^{2} = (2, 0)) in which d steps cannot be followed by h^{2} steps. Assigning a Schr(dh^{2})-structure on l means, for any l_{1}, l_{2} such that l_{1} + l_{2} = l, to give a Dyckstructure on l_{1} and an E-structure on l_{2}. Indeed, this corresponds to encoding the path by means of a vector with bicoloured components, having dimension equal to the sum of the number of u steps and h^{2} steps of the path; the components of such a vector are the positions of the u and h^{2} steps, and colours are used to distinguish the two types of steps. The fact that the path must avoid the pattern dh^{2} allows to split the bicoloured vector into two “classical” vectors containing the positions of the u steps and of the h^{2} steps, respectively. Consider, for instance, the Schr(dh^{2})-structure (1, 2, \overline{3}, 4, 7, \overline{8}) on {1, … 6}. In the preceding vector, the nonoverlined components determine a Dyckstructure on the subset {1, 2, 4, 5} of {1, … 6} which is isomorphic to (1, 2, 3, 6) on {1, 2, 3, 4}, whereas the overlined components determine the unique E-structure on the subset {3, 6} of {1, … 6}. The resulting Schröder path is shown in figure 2. Thus, in particular, we get that the class of restricted Schröder paths under consideration is enumerated by s_{n} = ∑_{k=0}^{n} \binom{n}{k}C_{k}, where (C_{n})_{n∈N} = (1, 1, 2, 5, 14, 42, …) are the Catalan numbers (this is sequence A007317 in [Sl], but the present interpretation is not recorded).

Figure 2. A restricted Schröder path.

We close this example by observing that, using the definition of the product of two ECO species, we are able to describe a succession rule for the above class of restricted Schröder paths. Indeed, the associated operator is the following: given a path P ∈ Schr(dh^{2}),

-) if the last step before the final sequence of d steps is u, then delete the last peak; -) if the last step before the final sequence of d steps is h^{2}, then delete it.

From this, we easily deduce the following succession rule:

Ω : \{ \begin{matrix}(2)_{0} \\ (2) ⇝ (2)(3) \\ (k) ⇝ (3)(4) ⋯ (k − 1)(k)^{2}(k + 1) \end{matrix} .

Remark. We observe that, unlike the case of the derivative and of the sum, it is not known the general form of the succession rule associated with the product of two given ECO species (although we have been able to find it in the above considered special case). It would therefore be interesting to have such a description of the product in terms of succession rules (when the factors can be encoded with suitable succession rules, of course).

4.4. Ordinal product. Consider the linear species F ·_{O} G as defined in [BLL], that is:

(F ·_{O} G)[l] = ∑_{l_{1}+_{O}l_{2}=l} F [l_{1}] × G[l_{2}].

This is called the ordinal product, and corresponds to the product of ordinary generating functions, so that (f ·_{O} g)(x) = f(x) · g(x).

Observe that the Leibniz rule does not hold for the ordinal product. However, it is possible to prove an analogous result, which is contained in the following lemma.

Lemma 4.1. For any linear species F, G, we have:

(F ·_{O} G)′ = F ·_{O} G′,  if o(G) > 0;
(F ·_{O} G)′ = F ·_{O} G′ + F′,  if o(G) = 0.

Proof. (1) Combinatorial (species-theoretic) proof. Given a linearly ordered set, from the definition of ordinal product we get immediately:

(2)  (F ·_{O} G)′[l] = (F ·_{O} G)[l^{+}] = ∑_{l_{1}+_{O}l_{2}=l^{+}} F [l_{1}] × G[l_{2}].

If o(G) > 0, denoting by l^{−} = l −_{O} 1 the linearly ordered set obtained from l by removing its top element, the above equality can be extended as follows:

∑_{l_{1}+_{O}l_{2}=l^{+}} F [l_{1}] × G[l_{2}] = ∑_{l_{1}+_{O}l_{2}=l^{+}} F [l_{1}] × G′[l_{2}^{−}]

= ∑_{l_{1}+_{O}l_{2}=l} F [l_{1}] × G′[l_{2}] = (F ·_{O} G′)[l].

If o(G) = 0, the sum in (2) naturally splits into two distinct summands:

∑_{l_{1}+_{O}l_{2}=l^{+}} F [l_{1}] × G[l_{2}] = _{∑_{l_{1}+_{O}l_{2}=l^{+}} ; l_{2}≠∅}F [l_{1}] × G[l_{2}] + F [l^{+}]

= ∑_{l_{1}+_{O}l_{2}=l} F [l_{1}] × G′[l_{2}] + F′[l]

= (F ·_{O} G′ + F′)[l].

(2) Generating functions proof. Since two linear species are isomorphic if and only if their (ordinary) generating functions are identical, to get the assertion it suffices to compare the generating functions of the linear species under consideration.

If o(G) > 0, we get first that the generating function of (F ·_{O} G)′ is

\frac{f(x) · g(x)}{x} = f(x) · \frac{g(x)}{x},

and the right hand side is clearly the generating function of F ·_{O} G′. On the other hand, if o(G) = 0, the generating function of F ·_{O} G′ + F′ is

f(x) · \frac{g(x) − 1}{x} + \frac{f(x) − f(0)}{x} = \frac{f(x) · g(x) − f(0)}{x},

which clearly coincides with the generating function of (F ·_{O} G)′. □

If (F, p), (G, q) are ECO species of orders n_{0}, m_{0}, respectively, we define the ordinal product (F, p)·_{O}(G, q) = (F ·_{O}G, p·_{O}q) to be the ECO species of order n_{0}+m_{0} such that F ·_{O} G is the ordinal product of F and G and p·_{O} q is the natural transformation defined as follows. Given l ∈ Ob(𝕃) such that |l| ≥ n_{0} + m_{0}, let (F ·_{O} G)′[l] = (F ·_{O} G)[l^{+}] = ∑_{l_{1}+_{O}l_{2}=l^{+}} F [l_{1}] × G[l_{2}]. We distinguish two cases.

1) If m_{0} > 0, then the above lemma says that (F ·_{O} G)′ = F ·_{O} G′. In this case, if l_{2} is endowed with a nonminimal structure, we simply apply q to the G-part of X to get an (F ·_{O} G)-structure on l. Otherwise we get an (F ·_{O} G)-structure on l by imposing the unique G-structure on the final segment of l and, on the remaining initial segment, the F -structure essentially obtained by applying p to the F -part of X (this requires a suitable renaming of the elements of l).

2) If o(G) = 0, then, from the above lemma, we get (F ·_{O} G)′ = F ·_{O} G′ + F′. More precisely, the proof of the lemma shows that, if |l_{2}| > 0, then we get an (F ·_{O} G′)-structure on l, whereas, if |l_{2}| = 0, we essentially have an F′-structure on l. With this in mind, we define p ·_{O} q by arguing as in 1) if |l_{2}| > 0 and by saying that it coincides with p if |l_{2}| = 0.

Thus we have completed the definition of p ·_{O} q. In order to show that our definition is correct, we need the following result.

Proposition 4.4. p ·_{O} q is a natural transformation.

Proof. We have to show that, for any choice of l, m, α : l ⟶ m, the following diagram is commutative:

\xymatrix{(F ·_{O} G)′[l] \ar[d]_{(F ·_{O}G)′[α]} \ar[r]^{(p·_{O}q)_{l}} & (F ·_{O} G)[l] \ar[d]^{(F ·_{O}G)[α]} \\ (F ·_{O} G)′[m] \ar[r]_{(p·_{O}q)_{m}} & (F ·_{O} G)[m]}

Let X be an (F ·_{O} G)′-structure on l. This means that there exist two linearly ordered sets l_{1}, l_{2} such that l_{1} +_{O} l_{2} = l^{+} and X is endowed with an F -structure on the initial segment l_{1} and a G-structure on the final segment l_{2}. If l_{2} bears a nonminimal Gstructure, then (p ·_{O} q)_{l} acts as the identity on the F -structure on l_{1} and coincides with q on the G′-structure on l_{2}^{−}. Therefore, in this case the proof of the assertion can be reduced to the proof of identities of the type

G[α] ∘ q = q ∘ G′[α],
F [α] ∘ 1 = 1 ∘ F [α],

which are clearly true since q is a natural transformation.

Otherwise, (p ·_{O} q)_{l} essentially coincides with p on the F′-structure on l_{1}^{−} and acts as the identity on the G-structure on l_{2}. Therefore the equalities to be proved in this case are of the following type:

F [α] ∘ p = p ∘ F′[α],
G[α] ∘ 1 = 1 ∘ G[α],

and they follow immediately from the fact that p is a natural transformation. □

When the starting ECO species are associated with suitable succession rules, then the ordinal product can be alternatively described using a succession rule, by means of an operation essentially equivalent to the one defined in [FPPR1, PPR1]. Indeed, if (F, p) and (G, q) are associated respectively with the two succession rules Ω and Σ given in (1), then (F ·_{O} G, p ·_{O} q) is described by the succession rule

Ω ·_{O} Σ : \{ \begin{matrix}((a_{i} + b_{j}))_{n_{0}≤i≤n_{r},m_{0}≤j≤m_{s}} \\ (k + b_{j}) ⇝ (e_{1}(k) + b_{j}) ⋯ (e_{k}(k) + b_{j})(\overline{c_{1}(b_{j})}) ⋯ (\overline{c_{b_{j}}(b_{j})}), ∀j \\ (\overline{k}) ⇝ (\overline{c_{1}(k)}) ⋯ (\overline{c_{k}(k)}) \end{matrix} .

Example. It is known that any nonempty Dyck path can be uniquely decomposed as an elevated (possibly trivial) Dyck path followed by another Dyck path (where an elevated Dyck path is, by definition, a Dyck path touching the x-axis only at its starting and ending points). This can also be expressed using a linear species identity. Indeed, if Dyck^{∗} is the linear species of nonempty Dyck paths and ElevDyck is the linear species of elevated Dyck paths, we have the identity:

Dyck^{∗} = ElevDyck ·_{O} Dyck.

Observe that Dyck has order 0, whereas ElevDyck has order 1. Now consider the previously defined ECO species (Dyck, lastpeak). We can consider the restriction of such an ECO species to Dyck^{∗} and ElevDyck: in both cases, it can be shown that the operator lastpeak can be suitably redefined in order to actually get an ECO species. More precisely, the ECO species thus obtained for ElevDyck is described by the same succession rule associated with (Dyck, lastpeak) (where the axiom (1)_{0} is replaced by the axiom (1)_{1}), whereas, in the case of Dyck^{∗}, the axiom is (2)_{1} instead of (1)_{0}. With these considerations in mind, using the same name “lastpeak” also for the operators of the ECO species associated with Dyck^{∗} and ElevDyck, we have that

(Dyck^{∗}, lastpeak) = (ElevDyck, lastpeak) ·_{O} (Dyck, lastpeak).

4.5. Cartesian product. Given two linear species F, G, their Cartesian product is defined on l by:

(F × G)[l] = F [l] × G[l].

The Cartesian product is related to the Hadamard product of the associated generating functions.

Now assume that (F, p), (G, q) are ECO species of orders n_{0}, m_{0}, respectively. We introduce the transformation p×q : (F ×G)′ ⟶ F ×G defined by (p×q)_{l} = p_{l}×q_{l}. Here we recall the usual definition of the Cartesian product of two functions f : A ⟶ B and g : C ⟶ D: it is simply the function f × g : A × C ⟶ B × D such that (f × g)(x, y) = (f(x), g(y)).

Observe that, in the definition of p × q, we have used the fact (easy to show) that (F × G)′ = F′ × G′.

Proposition 4.5. p × q : (F × G)′ ⟶ F × G is a natural transformation.

Proof. The generic (F ×G)′-structure on l can be expressed as X ×Y, where X is an F′- structure and Y is a G′-structure. Now, the fact that p and q are natural transformations means that:

(F′[α] ∘ p_{l})(X) = (p_{m} ∘ F [α])(X),
(G′[α] ∘ q_{l})(Y) = (q_{m} ∘ G[α])(Y),

for any α : l ⟶ m. Therefore we have immediately:

(F′[α] × G′[α]) ∘ (p_{l} × q_{l})(X × Y) = (p_{m} × q_{m}) ∘ (F [α] × G[α])(X × Y),

which is precisely the condition of commutativity which ensures that p × q is a natural transformation. □

The ECO species (F × G, p × q) will be called the Cartesian product of the two ECO species (F, p) and (G, q). It is immediate to see that it is an ECO species of order max(n_{0}, m_{0}).

Also in the case of the Cartesian product, when the starting ECO species can be described by some succession rules, it is possible to translate the above defined operation on ECO species into an operation on succession rules. Indeed, if Ω and Σ are associated with the ECO species (F, p) and (G, q), respectively, the labels of the Cartesian product Ω × Σ are obtained by multiplying each label of Ω by each label of Σ, and the same happens for productions. Colours are possibly used when the multiplications of different pairs of labels give rise to the same value. This operation has been briefly sketched in [FPPR1] (together with an illustrative example), and corresponds to the Kronecker product on the associated production matrices (see [DFR]).

Example. Consider the linear species C of cycles and P of subsets. We get an ECO species (of order 1) if we consider the natural transformation max : C′ ⟶ C which takes a cycle π to the one obtained by removing its maximum. It can be equivalently described by the succession rule:

\{ \begin{matrix}(\overline{1})_{1} \\ (\overline{1}) ⇝ (1) \\ (k) ⇝ (k + 1)^{k} \end{matrix} .

As for P, consider the natural transformation el which acts on a subset of a set of cardinality n either by removing the maximum (if it belongs to such a subset) or by leaving the subset unchanged. The resulting ECO species (P, el) is associated with the succession rule

\{ \begin{matrix}(2)_{0} \\ (2) ⇝ (2)^{2} \end{matrix} .

Performing the Cartesian product, we get the ECO species (C × P, max × el), which is the linear species of cycles where some of the elements are distinguished, together with the ECO construction corresponding to the following succession rule:

\{ \begin{matrix}(\overline{2})_{1} \\ (\overline{2}) ⇝ (2)^{2} \\ (2k) ⇝ (2k + 2)^{2k} \end{matrix} .

4.6. Substitution. If F, G are linear species, with G[∅] = ∅, the substitution of G into F (also called partitional composition) is, by definition, the following linear species:

(F ∘ G)[l] = ∑_{π∈P(l)} F [π] × ∏_{p∈π} G[l_{|p}].

Therefore an (F ∘ G)-species on l is a partition of l endowed with an F -species on the set of its blocks (which is linearly ordered as described in Section 2) and a G-species on each of the blocks. It can be shown that the behavior of the related exponential generating functions is described by the usual substitution operation:

(F ∘ G)(x) = F (G(x)) = ∑_{n≥0} f_{n} \frac{(G(x))^{n}}{n!} .

An important fact concerning substitution is the following chain rule, which we state without proof (see, for instance, [BLL]).

Proposition 4.6. For any (linear) species F, G, we have:

(F ∘ G)′ = (F′ ∘ G) · G′.

The above isomorphism of species is essential in defining a natural ECO species associated with the substitution operation.

Assume that (F, p), (G, q) are ECO species of orders n_{0}, m_{0}, respectively, and suppose that m_{0} > 0. Our aim is to define a natural transformation p ∘ q from (F ∘ G)′ to F ∘ G. Given a linearly ordered set l, using the isomorphism reported in the last proposition, we can map (F ∘ G)′[l] to ((F′ ∘ G) · G′)[l]. In order to fix notations, suppose that

((F′ ∘ G) · G′)[l] = ∑_{l_{1}+l_{2}=l}(F′ ∘ G)[l_{1}] × G′[l_{2}].

Now we have essentially two cases, depending on the G-structure on l_{2}^{+}.

(1) If l_{2}^{+} is endowed with a nonminimal G-structure, then we are able to apply q to the G′-structure on l_{2}, thus removing the maximum of l^{+} (which necessarily belongs to l_{2}) and obtaining a G-structure on l_{2}. Therefore, in this case, we get an ((F′ ∘ G) · G)-structure on l. Moreover, it is not difficult to realize that (F′ ∘ G) · G is isomorphic to F ∘ G.

(2) If l_{2} bears a minimal G′-structure, we further have two distinct possibilities.

(i) If |l_{2}| = 1, then we can remove the whole block l_{2}, and this is essentially an application of the operator p. Therefore, also in this case we get an ((F′ ∘ G) · G)-structure on l, or equivalently an (F ∘ G)-structure on l. (ii) If |l_{2}| > 1, then we have to remove the maximum of the elements of l_{1} which belong to a block having strictly more than m_{0} elements (if any). For instance, we can choose the maximum block (with respect to the linear order on the blocks mentioned in Section 2) endowed with a nonminimal G-structure. As a matter of fact, this means to apply q to a suitable Gstructure (observe that, in this case, also a suitable renaming of part of the elements of l has to be performed). What we obtain can be interpreted as an (F ∘ G)-structure on l.

Thus, in all cases we can conclude that

((F′ ∘ G) · G)[l] = (F ∘ G)[l].

In this way we have completed the definition of the transformation p ∘ q.

Proposition 4.7. p ∘ q : (F ∘ G)′ ⟶ F ∘ G is a natural transformation.

Proof. Consider the following diagram:

\xymatrix{(F ∘ G)′[l] \ar[d]_{(F ∘G)′[α]} \ar[r]^{(p∘q)_{l}} & (F ∘ G)[l] \ar[d]^{(F ∘G)[α]} \\ (F ∘ G)′[m] \ar[r]_{(p∘q)_{m}} & (F ∘ G)[m]}

where, as usual, α : l ⟶ m is an increasing bijection. Consider a structure X ∈ (F ∘ G)′[l] = (F ∘ G)[l^{+}]; let {B_{1}, …, B_{n}} be the partition of l^{+} determined by X, and suppose the top element of l^{+} belongs to B_{k}. We have to distinguish two different cases.

If B_{k} is endowed with a nonminimal G-structure, then (p ∘ q)_{l}(X) is the (F ∘ G)- structure on l obtained by applying q to the G-structure on B_{k} and leaving the other blocks untouched; the successive application of (F ∘G)[α] is simply the transport of the structure along the given increasing bijection. On the other hand, one can consider the structure (F ∘ G)′[α](X): observe that this simply means transporting the structure X along α + 1, which, in particular, maps the top element of l^{+} to the top element of m^{+}. Therefore one can apply (p∘q)_{m}, which removes the top element of m^{+} by means of the natural transformation q. It is clear that the two computations give the same result, so that the commutativity of the above diagram is ensured in this first case.

The other possibility is that B_{k} bears a minimal G-structure. If |B_{k}| = 1, then p ∘ q acts by removing the whole block B_{k}, which is just the singleton of the maximum of l^{+}, by means of the natural transformation p. In this specific situation, (F ∘ G)′[α] preserves the whole block B_{k}, which is then removed by (p ∘ q)_{m}; the same thing can be achieved by first removing B_{k} by means of (p ∘ q)_{l} and then transporting the remaining structure by means of (F ∘ G)[α]. The case |B_{k}| > 1 is left to the reader. □

Example. Let P ar be the linear species of set partitions. It is well known that P ar = E ∘ E_{+}, where E_{+} denotes the linear species of nonempty sets. The above equality can be easily “lifted” to an ECO species equality. Indeed, if we consider the ECO species (E, elem) and (E_{+}, elem) (where elem is essentially defined for E_{+} as for E, the only difference being that E_{+} has order 1), their composition is the ECO species (P ar, stirling) = (E, elem) ∘ (E_{+}, elem), where stirling acts by simply removing the top element of the underlying linearly ordered set. Of course, depending on the fact that such an element belongs to a block of cardinality > 1 or else to a singleton block, stirling must be properly defined.

Remark. As it happened for the product of ECO species, it is an open problem to determine the succession rule associated with the substitution of two ECO species, under the hypothesis that such ECO species allow a description in terms of succession rules.

4.7. Ordinal substitution. If we replace set partitions with ordered partitions in the definition of substitution, we obtain the following definition of ordinal substitution of two linear species F and G:

(F ∘_{O} G)[l] = ∑_{π∈PL(l)} F [π] × ∏_{p∈π} G[l_{|p}].

Ordinal substitution is related to the composition of the associated ordinary generating functions:

(f ∘_{O} g)(x) = f(g(x)).

Now let (F, p), (G, q) be any two ECO species. Using an argument very similar to the one employed for substitution, it is easy to see that the linear species F ∘_{O} G and (F′ ∘_{O} G) ·_{O} G′ are isomorphic. Then it is possible to define a natural transformation from (F′ ∘_{O} G) ·_{O} G′ to (F′ ∘_{O} G) ·_{O} G by performing either p or q on some suitable structure, using the same cautions as for substitution. Finally, it can be shown that (F′ ∘_{O} G) ·_{O} G and F ∘_{O} G are isomorphic: in this way we have defined a natural transformation p ∘_{O} q : (F ∘_{O} G)′ ⟶ F ∘_{O} G. The ECO species (F ∘_{O} G, p ∘_{O} q) will be called the ordinal substitution of (G, q) into (F, p). The proof that this construction is correct is completely analogous to that of Proposition 4.7.

In order to help the reader in understanding the above definition of p ∘_{O} q we will provide a more combinatorial description of it in terms of ECO (see also figure 3).

• In the generating forest associated with the ECO species (F ∘_{O} G, p ∘_{O} q), the roots of the trees (corresponding to the minimal structures) consist of those structures given by an assembly of minimal G-structures on the blocks of an ordered partition of a linearly ordered set l together with any F -structure on the set of blocks of such an ordered partition.

• Given an (F ∘_{O} G)-structure X determined by an ordered partition π of l, let B be rightmost block of π endowed with a non minimal G-structure. Then our ECO construction performs the following actions:

(i) add a new maximum to B and consider all the G-structures determined by (G, q) on the resulting block (without modifying the F -structure on the set of blocks);

(ii) if \overline{B} is a block of π to the right of B, then perform the same action as in

(i); (iii) only in case G has order 1, add a singleton block to the right of each block \overline{B} defined as in (ii) (endowed with any possible G-structure) and endow the set of blocks of the resulting partition with all possible F -structures determined by (F, p).

Figure 3. ECO construction associated with the ordinal substitution.

In the framework of succession rules, the problem of determining a succession rule associated with the composition of the ordinary generating functions of two given succession rules has never been considered. Here we describe a special case, which turns out to be quite easy to deal with.

Let (F, p) and (G, q) be two ECO species both having order 1, and suppose that, when |l| = 1, |F [l]| = |G[l]| = 1. Moreover, denote with Ω and Σ the associated succession rules, respectively, and, as usual, suppose that such rules are described as in (1). It is clear that, under the above hypotheses, it is r = s = 0 and n_{0} = m_{0} = 1.

Proposition 4.8. The succession rule

\{ \begin{matrix}(a, b)_{1} \\ (h, k) ⇝ (e_{1}(h), b) ⋯ (e_{h}(h), b)(h, c_{1}(k)) ⋯ (h, c_{k}(k)) \end{matrix}

has associated generating function f(g(x)), where f and g are the ordinary generating functions of the two succession rules Ω and Σ, respectively.

Proof. Let X be an (F ∘_{O} G)-structure on l^{+}. Denote by π the ordered partition determined by X. By definition of ordinal substitution of ECO species in this specific case, the natural transformation p ∘_{O} q removes the maximum of l^{+} from the rightmost block B of π. Then either

• B = 1, and so p ∘_{O} q removes the whole B and reorganizes the remaining blocks of the partition π into an F -structure, or

• |B| > 1, and so p∘_{O}q reorganizes the remaining elements of B into a G-structure. This construction can be equally described in a “reversed” manner. Take an (F ∘_{O}G)-

structure X on l such that the F -structure on the blocks of the associated partition π is labelled (h) and the G-structure on the rightmost block of π has label (k). Then, performing our ECO construction on X gives rise to a set of F ∘_{O} G-structures on l^{+} either:

• by adding the new block B consisting of the singleton of the maximum of l^{+} (B thus become the rightmost block in the associated partition), then defining one among the h possible F -structures on the set of the blocks of the resulting partition, or

• by adding a new maximum to the rightmost block of π, then defining one among

the k possible G-structures on the new rightmost block. In the first case, supposing to label (h, k) the structure X, we get the production

(h, k) ⇝ (e_{1}(h), b) ⋯ (e_{h}(h), b),

whereas in the second case the resulting production is

(h, k) ⇝ (h, c_{1}(k)) ⋯ (h, c_{k}(k)).

Putting things together, the assertion immediately follows. □

Example. Let Comp_{m} be the linear species of m-compositions of positive length, or, which is the same, the linear species of nonempty m-coloured linear partitions. These objects have been defined in [MPR], and we recall here their definitions.

An m-composition is an m×k matrix with nonnegative integer entries whose columns are different from the zero vector. We say that the number k of columns is the length of the composition. Moreover we say that M is an m-composition of a nonnegative integer n when the sum of all its elements is exactly n.

Let C = {c_{1}, …, c_{m}} be a set of colours linearly ordered in the natural way c_{1} < ⋯ < c_{m}. We say that the linearly ordered set [n] = {1, 2, …, n} is m-coloured when each element is coloured with one colour in C respecting the following condition: if c_{i} and c_{j} are the respective colours of two elements x and y, with x ≤ y, then i ≤ j. In other words, an m-colouring of [n] is an order-preserving map γ : [n] ⟶ C. We define an m-coloured linear partition of [n] as a linear partition in which each block is m-coloured.

Giving a structure of species Comp_{m} on a linearly ordered set l is equivalent to providing a nonempty m-coloured linear partition of L, i.e., to assigning a nonempty ordered partition π on l and then an m-colouring, that is an order-preserving map into C, on each block of π. Then, if Map_{≠∅}^{(m)} denotes the linear species of order-preserving maps from a nonempty linearly ordered set to the set of colours C, we have that

(3)  Comp_{m} = E_{+} ∘_{O} Map_{≠∅}^{(m)}.

Now observe that we can define an ECO species of support Map_{≠∅}^{(m)}. Indeed, given a linearly ordered set l of cardinality n ≥ 1, for any structure of species Map_{≠∅}^{(m)} on l, one can define a set of new structures on l^{+} by simply mapping n + 1 to a colour greater than or equal to the colour of n. This simple observation implies that Map_{≠∅}^{(m)} possesses an ECO construction which can be described by means of the following succession rule:

\{ \begin{matrix}(1)_{1}; (2)_{1}; ⋯; (m)_{1} \\ (k) ⇝ (1)(2) ⋯ (k − 1)(k) \end{matrix} .

Now let (Map_{≠∅}^{(m)}, colour) be the the ECO species associated with the above succession rule. Thanks to what we have shown in the present section, equality (3) implies the existence of an ECO species of support Comp_{m}, which can also be described by means of a suitable succession rule:

\{ \begin{matrix}(1)_{1}; ⋯; (m)_{1} \\ (k) ⇝ (1)^{2}(2)^{2} ⋯ (k)^{2}(k + 1) ⋯ (m) \end{matrix} .

For instance, if m = 3 and C = {a, b, c}, with a < b < c, consider the following 3-composition of length 4:

τ = ( \begin{matrix}1 & 3 & 0 & 2 \\ 0 & 1 & 1 & 1 \\ 2 & 2 & 0 & 1 \end{matrix} ) .

The operator of the above described ECO species simply replaces the 1 in the bottom right corner of τ with a 0. On the other hand, the ECO construction associated with such an ECO species generates four 3-compositions starting from τ, which are precisely

( \begin{matrix}1 & 3 & 0 & 2 \\ 0 & 1 & 1 & 1 \\ 2 & 2 & 0 & 2 \end{matrix} ) , ( \begin{matrix}1 & 3 & 0 & 2 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 2 & 2 & 0 & 1 & 0 \end{matrix} ) ,

( \begin{matrix}1 & 3 & 0 & 2 & 0 \\ 0 & 1 & 1 & 1 & 1 \\ 2 & 2 & 0 & 1 & 0 \end{matrix} ) , ( \begin{matrix}1 & 3 & 0 & 2 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 2 & 2 & 0 & 1 & 1 \end{matrix} ) .

4.8. An application to permutation enumeration. We conclude our treatment of ECO species with a possible application to the study of some topics on permutations, such as permutation classes, the structure of permutations and pattern avoidance, whose importance is witnessed by a relevant number of publications during the last decade.

For given permutations π = p_{1} ⋯ p_{k} ∈ S_{k} and β_{1}, …, β_{k} ∈ S (where S_{k} and S denote the symmetric group of order k and the whole symmetric group, respectively), the inflation of π by β_{1}, …, β_{k} is defined to be the permutation π[β_{1}, … β_{k}] obtained by replacing each element p_{i} of π with a block whose pattern is β_{i} (for 1 ≤ i ≤ k), so that the relative ordering of the blocks is the same as the relative ordering of the corresponding elements of π. For instance, if π = 213, β_{1} = 21, β_{2} = 4312, β_{3} = 132, then π[β_{1}, β_{2}, β_{3}] = 654312798. An obvious extension to sets can be introduced, by defining π[B_{1}, …, B_{k}] as the set of all permutations of the form π[β_{1}, …, β_{k}] with β_{i} ∈ B_{i}. This definition can be found in [AA], where it is proposed as a sort of “localized version” of the wreath product construction, whose definition we are going to recall below.

Given two sets of permutations A and B, their wreath product [AS] is defined to be the set

A ≀ B = {α[β_{1}, …, β_{k}] | α ∈ A, β_{1}, …, β_{k} ∈ B}.

What is relevant for us is to recognize that the wreath product construction is intimately related with the ordinal substitution operation. As a matter of fact, the ordinal substitution of two linear species each representing a set of permutations coincides with the wreath product of the two sets, provided that each permutation of the resulting set can be written in a unique way as a permutation in the wreath product. This statement is essentially a translation, in the language of linear species, of Theorem 10 of [AS].

Thus the whole theory of the wreath product of classes of permutations can be rephrased in terms of ordinal substitution of linear species. As a sample application of this fact, we will present here two ECO constructions related with the wreath product operation. The first one is completely elementary, whereas the second one is less trivial, and provides an effective construction for a result of [AS]. We encourage the reader to find analogous constructions for all the examples in the above cited paper.

Layered permutations. A permutation is called layered when it is the concatenation of decreasing subsequences d_{1}, …, d_{k} so that each entry of d_{i} is less than each entry of d_{j} for all i < j. It is clear that the class of layered permutations is the wreath product I ≀ R of the classes I of identity permutations and R of reversed nonempty identity permutations. Thus, applying our theory, we can describe an elementary ECO construction for layered permutations, which simply consists of adding a new entry at the end of any layered permutation π = π_{1} ⋯ π_{n} in two possible ways: either add π_{n} −1 or n + 1.

Sorting with a stack of queues. Consider the set of permutations that can be sorted by a stack in which the push operation can take any number of input symbols at a time, place them in a queue and then place this queue on the stack. This set of permutations can be simply described as a wreath product, since it coincides with S_{n}(231) ≀ I (here S_{n}(π) denotes the set of π-avoiding permutations of length n). As a consequence of Corollary 11 in [AS], S_{n}(231) ≀ I = G ≀ I, where G is the set of irreducible 231-avoiding permutations (an irreducible permutation is one in which no pair i, i + 1 appears). Here we will show that irreducible 231-avoiding permutations can be generated by a suitable ECO construction, whence an ECO construction for S_{n}(231) ≀ I immediately follows. Indeed, it is known that S_{n}(231) = S_{n}(2−31) (see for instance [C]), and an ECO construction for S_{n}(2−31) goes as follows: given a permutation π ∈ S_{n}(2−31), generate a set of permutations of S_{n+1}(2 − 31) by appending at the end of π an element greater than or equal to the last element of π and then suitably renaming the elements of π greater than the added element. Thus, for instance, the permutation 216435 ∈ S_{6}(2−31) generates the set of permutations {2174365, 2174356, 2164357} ⊆ S_{7}(2 − 31). This construction can be easily adapted to generate irreducible 2−31-avoiding permutations: just avoid to append the element equal to the last element of π plus 1. Therefore, in the above example, after having noticed that 216435 is indeed irreducible, we have to delete from the generated set the permutation 217456. Such a construction for irreducible 2 − 31-avoiding permutations can be described by the following succession rule:

\{ \begin{matrix}(1) \\ (k) ⇝ (1)(2) ⋯ (k − 1)(k + 1) \end{matrix} ,

which is known to be associated with the sequence of Motzkin numbers. Now we can apply our theory, which allows us to describe an ECO construction associated with the ordinal substitution of the (trivial) ECO species of identity permutations into the ECO species of irreducible 231-avoiding permutations. Such an ECO construction is illustrated in figure 4.

Figure 4. A graphical representation of the permutation 128953467; the white circles on the right indicates where an element can be appended, according to our ECO construction.

5. Conclusions and further work

Our translation of the ECO method into the theory of linear species can be considered as a first step towards a better understanding of the purely combinatorial features of ECO. In particular, the notion of ECO isomorphism, which has just been introduced here but not thoroughly investigated, provides a more restrictive notion of bijection. Indeed, two ECO species are ECO isomorphic when their supports are isomorphic (i.e., there is a bijection between the structures of size n of the first species and of the second species, for any n) and the generating forests of the two ECO species are isomorphic. This last conditions means that not only the two ECO species are equipotent but they are also recursively generated by the same ECO construction.

The fact that an ECO species gives a way of encoding an ECO construction could have some relevance in the design of algorithms for the generation of combinatorial structures. There are several papers in which the ECO methodology provides some tools to find algorithms for the random and exhaustive generation of combinatorial objects. More specifically, random generation algorithms can be designed by considering generating trees in which edges are suitably labelled [BDLP]. This can be alternatively described by assigning a weight to each object (namely, the weight of the edge connecting that object to its father), and this naturally leads to the notion of weighted linear species. The generalization of the theory of ECO species to the case of weighted species could then provide a suitable setting for studying random generation algorithms. As far as exhaustive generation is concerned, in [BFG] a technique is developed which is based on some finite generating trees (i.e., each branch eventually ends in a node without sons). Then a suitable visit of such trees is defined, which of course requires to go back and forth. Since the notion of ECO species in fact formalizes the concept of father (and so of “going back in the tree”), it is reasonable to think that our theory can be of some help in dealing with exhaustive generation algorithms.

Finally, we would like to briefly mention some possible future developments of the present theory which are more species-oriented. A first idea would be that of replacing linear species with ordinary species. Here the use of linear species is justified by the needs of clearly identify the element to be removed in order to be as closer as possible to the spirit of ECO. However, from a purely theoretical point of view, there is no special reason preventing from taking off a generic element, and so using ordinary species. A second theme of research could be the development of a differential calculus for ECO species along the lines of the classical differential calculus for species.

Acknowledgment. The contents of the present paper have been presented by the first author at LACIM, during his visit at the end of May 2009. During such a visit, L.F. had a long and stimulating conversation on these topics with François Bergeron. Another similarly deep conversation took place in Firenze (July 2009), during the Permutation Patterns Conference. L.F. takes pleasure in warmly thanking François Bergeron for many suggestions which both improved the present article and gave hints for future research on related matters.

References

[AA] M.H. Albert, M.D. Atkinson, Simple permutations and pattern restricted permutations, Discrete Math. 300 (2005) 1–15.

[AS] M. D. Atkinson, T. Stitt, Restricted permutations and the wreath product, Discrete Math. 259 (2002) 19–36.

[BBGP] S. Bacchelli, E. Barcucci, E. Grazzini, E. Pergola, Exhaustive generation of combinatorial objects by ECO, Acta Inform. 40 (2004) 585–602.

[BDLP] E. Barcucci, A. Del Lungo, E. Pergola, Random generation of trees and other combinatorial objects, Theoret. Comput. Sci. 218 (1999) 219–232.

[BDLPP1] E. Barcucci, A. Del Lungo, E. Pergola, R. Pinzani, ECO: a methodology for the Enumeration of Combinatorial Objects, J. Difference Eq. Appl. 5 (1999) 435–490.

[BDLPP2] E. Barcucci, A. Del Lungo, E. Pergola, R. Pinzani, Directed animals, forests and permutations, Discrete Math. 204 (1999) 41–71.

[BLL] F. Bergeron, G. Labelle, P. Leroux, Combinatorial Species and Tree-like Structures, Encyclopedia of Mathematics and its Applications, 67, Cambridge University Press, 1998.

[BFG] A. Bernini, I. Fanti, E. Grazzini, An exhaustive generation algorithm for Catalan objects and others, Pure Math. Appl. 17 (2006) 39–53.

[BE] M. Bousquet-Mélou, K. Eriksson, Lecture hall partitions, Ramanujan J. 1 (1997) 101–111.

[CGHK] F. R. K. Chung, R. L. Graham, V. E. Hoggatt, M. Kleiman, The number of Baxter permutations, J. Combin. Theory Ser. A 24 (1978) 382–394.

[C] A. Claesson, Generalized pattern avoidance, European J. Combin. 22 (2001) 961–971.

[DFR] E. Deutsch, L. Ferrari, S. Rinaldi, Production matrices, Adv. Appl. Math. 34 (2005) 101–122.

[FPPR1] L. Ferrari, E. Pergola, R. Pinzani, S. Rinaldi, An algebraic characterization of the set of succession rules, Theoret. Comput. Sci. 281 (2002) 351–367.

[FPPR2] L. Ferrari, E. Pergola, R. Pinzani, S. Rinaldi, Jumping succession rules and their generating functions, Discrete Math. 271 (2003) 29–50.

[FP] L. Ferrari, R. Pinzani, A linear operator approach to succession rules, Linear Algebra Appl. 348 (2002) 231–246.

[FPR] L. Ferrari, R. Pinzani, S. Rinaldi, Enumerative results on integer partitions using the ECO method, in: M. Drmota, P. Flajolet, D. Gardy, B. Gittenberger (eds.), Mathematics and Computer Science III, Birkhäuser, Basel, 2004, pp. 25–36.

[G] O. Guibert, Combinatoire des permutations á motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, PhD. thesis, Université Bordeaux 1 (1995).

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

[MPR] E. Munarini, M. Poneti, S. Rinaldi, Matrix compositions, J. Integer Seq. 12 (2009) #09.4.8, 28 pp.

[PPR1] E. Pergola, R. Pinzani, S. Rinaldi, A set of well-defined operations on succession rules, in: D. Gardy, A. Mokkadem (eds.), Mathematics and Computer Science, Birkhäuser, Basel, 2000, pp. 141–152.

[PPR2] E. Pergola, R. Pinzani, S. Rinaldi, Approximating algebraic functions by means of rational ones, Theoret. Comput. Sci. 270 (2002) 643–657.

[Sl] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, available at

    http://www.research.att.com/∼njas/sequences/index.html.

[W] J. West, Generating trees and the Catalan and Schröder numbers, Discrete Math. 146 (1995) 247–262.