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

DECOMPOSABLE FUNCTORS AND THE EXPONENTIAL PRINCIPLE, II

Peter J. Cameron^{†}, Christian Krattenthaler^{‡}, and Thomas W. Müller^{†}

† School of Mathematical Sciences, Queen Mary & Westfield College, University of London, Mile End Road, London E1 4NS, United Kingdom.

                WWW: http://www.maths.qmw.ac.uk/~pjc/
                WWW: http://www.maths.qmw.ac.uk/~twm/

‡ Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria.

               WWW: http://www.mat.univie.ac.at/~kratt

Dedié à la mémoire de Pierre Leroux

Abstract. We develop a new setting for the exponential principle in the context of multisort species, where indecomposable objects are generated intrinsically instead of being given in advance. Our approach uses the language of functors and natural transformations (composition operators), and we show that, somewhat surprisingly, a single axiom for the composition already suffices to guarantee validity of the exponential formula. We provide various illustrations of our theory, among which are applications to the enumeration of (semi-)magic squares.

1. Introduction

One of the corner stones of combinatorial enumeration is a theory which runs under several different names, for instance theory of species [6], theory of exponential structures [28, Ch. 5], theory of exponential families [29], symbolic method [11, Part A], théorie du composé partitionnel [12], theory of prefabs [4], all of which are more or less equivalent. It is probably fair to say that the most elaborate of these theories is the theory of species, as formulated by Joyal [16] (with the functorial concept of species of structures going back to Ehresmann [10]) and further developed by many other authors. It provides the most general framework for such a theory, at the expense of employing a rather abstract language, namely that of category theory.

2000 Mathematics Subject Classification. Primary 05A15; Secondary 05A16 05A19 05C30. Key words and phrases. labelled combinatorial structures, multisort species, exponential principle,

functor decomposition, magic squares.

‡Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

A fundamental theorem in each of these theories is the so-called exponential formula. Roughly speaking, given a family G of labelled combinatorial objects (“components”), one produces a larger family F (“composite objects”) whose objects are obtained by putting together various elements of G. The theorem then states that the (exponential) generating function for F equals the exponential of the (exponential) generating function for G.

The aim of the present article is to develop a setting, where one starts with a family F of labelled combinatorial objects (“composite objects”) and a composition of such objects, and then identifies, in an intrinsic way, a subfamily G of indecomposable objects (“components”), such that each element of F can be decomposed into objects from G, and such that the exponential formula holds for F and G. The main point here is that, in contrast to the usual set-up for the exponential formula, indecomposable objects are not given in advance, but are defined inherently via the composition operation. In particular, our theory leads to a uniform definition of the property to be indecomposable for arbitrary labelled combinatorial objects equipped with a composition operator. Interestingly, we show that a single axiom for the composition operator suffices to guarantee validity of the exponential formula. The natural language for formulating a corresponding theory is that of functors and natural transformations. Consequently, our presentation will be in the context of species theory.

For “ordinary” species (1-sort species), such a theory has been presented in [9] on the basis of two axioms for the composition operator. In the present article, we extend this approach to weighted multisort species. Moreover, we show that, actually, one of the axioms in [9] can be derived from the other, and that also in our multivariate setting a single axiom suffices. Strictly speaking, our presentation does not cover weighted species (in the sense of [16, Sec. 6], [6, p. 104]) in full generality; rather, we restrict ourselves to the case where the defining functor maps to a category of finite sets, thus avoiding unnecessary technicalities. However, extension to the general case of weighted multisort species is completely straightforward, and is left to the interested reader (see also Footnote 4).

An exponential principle in a wider context, that encompasses multisort species as a particular case, has been defined by Menni in [21] (see [23] for further work in this direction). Indeed, Menni’s work and ours partially overlap. In order to explain the relation between the two, recall that — as already pointed out by Joyal [16, Sec. 7.1]

— multisort species have the structure of a symmetric monoidal category. Now, in the focus of [21] there are simple commutative monoids in a given symmetric monoidal category. Menni defines an exponential principle in this set-up, and he proves this principle to hold for a large family of symmetric monoidal categories (see [21, Prop. 1.4]). He shows that this provides a uniform framework for the exponential principle for numerous variations of species that had appeared earlier in the literature, including multisort species (see [21, Ex. 3.2 and Ex. 3.5 with I = 1 + 1 + ⋯ + 1]).^{1} However, as it turns out, in the case of multisort species, Menni’s theory does not cover the setting of our paper. It does apply whenever the considered multisort species, together with the product induced by our composition operator, forms a simple commutative monoid. This does not need to be the case, as Example 3 in Section 7 shows (see also Section 9 for more detailed elaboration on these matters). So, one could say that Menni’s theory exhibits the structural essentials of the exponential principle in a wide categorical framework, whereas our paper presents a “minimalistic” axiomatic setting for the exponential principle that is specific for multisort species but, as a bonus, includes a wider set of examples than Menni’s theory does (in the case of multisort species). It is conceivable that our setting can be adapted to work for some other kinds of species, but it is unlikely that it can be lifted to the level of generality of Menni’s theory.

1Strictly speaking, weights are not discussed in [21]. However, it would not be difficult to include them in the theory developed in [21].

In the next section, we develop the general set-up for our theory. It is formulated within the theory of multisort species, for which we define certain composition operators η that are subject to a single axiom, which, in order to be consistent with [9], we call (D1). Furthermore, in the same section, we present our main results. These are two exponential formulae, see Theorems 1 and 4. Theorem 4 refines Theorem 1 by introducing another variable whose powers keep track of the number of “components.” The proof of Theorem 4 requires two general facts about our composition operators η, which are presented in Propositions 2 and 3. (It is the latter, which, in the less general context of [9], had been assumed as a separate axiom, (D2). As our proof of Proposition 3 shows, this was actually not necessary since, within the general framework, (D2) follows from (D1). It is interesting to note that, in the context of [21], Menni also observed that the axiom (D2) was not necessary; see [21, Ex. 3.5]. Our derivation of (D2) from (D1) provides the reason why this is the case: we show that (D2) is implied by — as we call it — “m-permutability” of a species together with a composition operator; see the proof of Proposition 3, and Lemmas 11 and 15. This “m-permutability” comes for free in the context of [21] since the underlying species is assumed to form a commutative monoid in the category of species and, thus, satisfies stronger forms of “permutatility;” see also the more detailed explanations at the beginning of Section 9, and in particular the paragraph containing (9.4) and (9.5).) The proofs of Theorems 1 and 4, and of Propositions 2 and 3, are given in Sections 4 and 6, respectively. They require a number of auxiliary results, which are established in Sections 3 and 5, respectively.

Sections 7 and 8 offer illustrations for the theory developed in Sections 2–6. Section 7 presents three simple examples highlighting different aspects of combinatorial situations covered by Theorems 1 and 4. In Section 8, we show how to apply our results to obtain generating function identities for (semi-)magic squares, thereby generalising previous results in the literature.

The final section, Section 9, discusses the relationship between Menni’s theory in [21] and ours. Moreover, there we make Menni’s characterisation (see [21, Sec. 2.6]) of the simple commutative monoids that are covered by his result [21, Prop. 1.4] on the (general) exponential principle explicit for the special case of multisort species. As we show, this provides, in the language of our paper, a characterisation of composition operators that are pointwise associative and commutative (see (9.4) and (9.5)). Menni’s characterisation implies that a family F of labelled combinatorial objects equipped with such a composition operator can be re-constructed, in a sense made precise in Theorem 22, from the standard operation of forming the disjoint union in E(G) (the species of sets of objects from G), where G denotes again the family of indecomposable objects in F. We conclude our paper by “twisting” this construction (see Theorem 23), thereby obtaining a large family of examples that fit under our theory but not under Menni’s.

2. Set-up and main results

Denote by Ŝet the category of finite sets and injective mappings, and by Set the subcategory consisting of finite sets and bijective maps. Moreover, for a positive integer r, let 𝔇_{r} be the full subcategory of Set^{r} × Set^{r} whose objects are given by

Ob(𝔇_{r}) = {(Ω_{1}, Ω_{2}) ∈ Ob(Set^{r} × Set^{r}) : Ω_{1} ∩ Ω_{2} = ∅∅∅},

where ∅∅∅ = (∅, …, ∅) is the element of Ob(Set^{r}) all of whose components are empty, and intersection is componentwise.

The ingredients needed for our theory are r-sort species and certain composition operators defined on them. Recall from [16] (or see [6, Def. 4 on p. 102] for a definition avoiding the language of category theory) that, for a positive integer r, an r-sort species is a covariant functor F : Set^{r} → Set. Given r and an r-sort species F, the composition operators we have in mind are certain natural transformations η from the functor^{2}

F × F : 𝔇_{r} ⟶^{(F,F)} Set × Set ⟶^{×} Set ⟶^{ι} Ŝet

to the functor

F ∘ ⨿ : 𝔇_{r} ⟶^{⨿} Set^{r} ⟶^{F} Set ⟶^{ι} Ŝet;

that is, families η = (η_{(Ω_{1},Ω_{2})})_{(Ω_{1},Ω_{2})∈Ob(𝔇_{r})} of injective maps,

η_{(Ω_{1},Ω_{2})} : F [Ω_{1}] × F [Ω_{2}] ↪ F [Ω_{1} ⨿ Ω_{2}],  (2.1)

such that, for every morphism f : (Ω_{1}, Ω_{2}) ⟶ (Ω̃_{1}, Ω̃_{2}) of 𝔇_{r}, the diagram

F [Ω_{1}] × F [Ω_{2}] ⟶^{η_{(Ω_{1},Ω_{2})}} F [Ω_{1} ⨿ Ω_{2}]
(F ×F)[f]↓  ↓^{(F ∘⨿)[f]}
F [Ω̃_{1}] × F [Ω̃_{2}] ⟶_{η_{(Ω̃_{1},Ω̃_{2})}} F [Ω̃_{1} ⨿ Ω̃_{2}]

(2.2)

commutes. Here, × is the natural product (Cartesian product) in the category of sets, ⨿ is the natural coproduct (componentwise disjoint union) in the category Set^{r} and in the category Set (relying on the context to clarify the intended meaning), and ι : Set → Ŝet is the inclusion functor. In what follows, the set-theoretic operations ∩, ∪, − as well as the inclusion relation ⊆ and | (restriction of morphisms) in Set^{r} are all understood to be componentwise.^{3} We shall most of the time drop the indices of η-maps when they are clear from the context, thus writing η(F [Ω_{1}]×F [Ω_{2}]) instead of η_{(Ω_{1},Ω_{2})}(F [Ω_{1}]×F [Ω_{2}]), for example. We shall think of the elements of a set η(F [Ω_{1}] × F [Ω_{2}]) as composite objects within F [Ω_{1} ⨿ Ω_{2}].

Given an r-sort species F and a composition operator η as above, the next step is to identify the subset F_{η}[Ω] of “indecomposable” elements of a set F [Ω]. It is most natural to define F_{η} : Ob(Set^{r}) → Ob(Set) via

2The introduction of the category 𝔇_{r} corrects a slight imprecision in the set-up of [9].

3Throughout this paper, we use the symbol − to denote the difference of sets.

F_{η}[Ω] := \begin{cases}F [Ω] − _{⋃_{(I,J)∈Ob(𝔇_{r})} ; I⨿J=Ω ; I≠∅ ∅ ∅≠J} η(F [I] × F [J]), & Ω ≠ ∅∅∅ \\ ∅, & Ω = ∅∅∅ \end{cases} , Ω ∈ Ob(Set^{r}).

At this point, F_{η} is just defined as a map from Ob(Set^{r}) to Ob(Set). In Lemma 14 in Section 3 we shall show that F_{η} is in fact a functor, that is, an r-sort species.

Not every natural transformation η is suited for giving rise to an exponential principle. We present the single axiom which is needed for this purpose next. Given F, we call a natural transformation η : F × F → F ∘ ⨿ a composition operator of F, if Axiom (D1) below holds.

(D1) For each Ω ∈ Ob(Set^{r}) and any two partitions (Ω_{1}, Ω_{2}), (Ω̃_{1}, Ω̃_{2}) ∈ Ob(𝔇_{r}) of Ω into disjoint parts,

Ω_{1} ⨿ Ω_{2} = Ω = Ω̃_{1} ⨿ Ω̃_{2},

we have that

η(F [Ω_{1}] × F [Ω_{2}]) ∩ η(F [Ω̃_{1}] × F [Ω̃_{2}]) = η(η(F [Ω_{11}] × F [Ω_{12}]) × η(F [Ω_{21}] × F [Ω_{22}])),

(2.3)

where Ω_{ij} := Ω_{i} ∩ Ω̃_{j} for i, j ∈ {1, 2}.

An r-sort species F will be called decomposable, if F ≠ ∅ (that is, F [Ω] ≠ ∅ for some Ω ∈ Ob(Set^{r}), and if F admits some composition operator η.

Next, we define weights on (F, η). Fix a commutative ring Λ which contains the rational numbers. A family w = (w_{Ω})_{Ω∈Ob(Set^{r})} of maps w_{Ω} : F [Ω] → Λ is termed a Λ-weight on (F, η), if the following three conditions hold:

(W0) For all x ∈ F [∅∅∅], we have w_{∅ ∅ ∅}(x) = 1.

(W1) For each morphism f : Ω_{1} → Ω_{2} of Set^{r}, the diagram

F [Ω_{1}] ⟶^{w_{Ω_{1}}} Λ
F [f]↓  ↓^{id}_{Λ}
F [Ω_{2}] ⟶_{w_{Ω_{2}}} Λ

commutes.

(W2) For each pair (Ω_{1}, Ω_{2}) ∈ Ob(𝔇_{r}), the diagram

F_{η}[Ω_{1}] × F [Ω_{2}] ⟶^{η_{(Ω_{1},Ω_{2})}|_{Fη[Ω_{1}]×F [Ω_{2}]}} F [Ω_{1} ⨿ Ω_{2}]
w_{Ω_{1}}|_{Fη[Ω_{1}]}×w_{Ω_{2}} ↓  ↓^{w_{Ω_{1}⨿Ω_{2}}}
Λ × Λ ⟶

multiplication in Λ

Λ

commutes.

Here, (W0) and (W1) make F a weighted r-sort species (cf. [6, p. 104]), whereas (W2) demands (in a weak form) the Λ-weight w to be compatible with the composition operator η.^{4} In Section 9, we shall also need the concept of a weak Λ-weight, by which we mean a collection w = (w_{Ω})_{Ω∈Ob(Set^{r})} of mappings as above satisfying (W0) and (W1), but not necessarily (W2).

Given a Λ-weight w = (w_{Ω})_{Ω∈Ob(Set^{r})} on (F, η), we define the corresponding exponential generating functions for F and F_{η}, respectively, by^{5}

GF_{F} (z_{1}, …, z_{r}) := ∑_{n_{1},...,n_{r}≥0} ∑_{x∈F [([n_{1}],...,[n_{r}])]} w_{([n_{1}],...,[n_{r}])}(x)\frac{z_{1}^{n_{1}} ⋯ z_{r}^{n_{r}}}{n_{1}! ⋯ n_{r}!} ,

GF_{F_{η}}(z_{1}, …, z_{r}) := ∑_{n_{1},...,n_{r}≥0} ∑_{x∈F_{η}[([n_{1}],...,[n_{r}])]} w_{([n_{1}],...,[n_{r}])}(x)\frac{z_{1}^{n_{1}} ⋯ z_{r}^{n_{r}}}{n_{1}! ⋯ n_{r}!} ,

where we suppress the dependence on w in the notation for better readability.

We are now ready to state our first main result, an exponential principle, which generalises Part (a) of the main result in [9].

Theorem 1. Let r be a positive integer, F : Set^{r} → Set an r-sort species, and let η : F × F → F ∘ ⨿ be a natural transformation. If F is decomposable and η is a composition operator for F, then the generating functions GF_{F} and GF_{F_{η}} are connected via the relation

GF_{F} (z_{1}, …, z_{r}) = exp ( GF_{F_{η}}(z_{1}, …, z_{r})).  (2.4)

The proof of Theorem 1 is given in Section 4. It requires several preparatory results, which are established in the next section.

In analogy to [9], there is a refinement of Theorem 1 in the spirit of [18, 24], which we explain next. Making use of the map F_{η} defined above, we define a sequence of mappings

F_{η}^{(k)} : Ob(Set^{r}) → Ob(Set), k ≥ 0,

with the property that F_{η}^{(k)}[Ω] ⊆ F [Ω] by induction on k via

F_{η}^{(0)}[Ω] := \begin{cases}F [∅∅∅], & Ω = ∅∅∅ \\ ∅, & Ω ≠ ∅∅∅ \end{cases}

and

F_{η}^{(k)}[Ω] := _{⋃_{Ω_{1}∈Ob(Set^{r})} Ω_{1}⊆Ω} η(F_{η}[Ω_{1}] × F_{η}^{(k−1)}[Ω − Ω_{1}]), k ≥ 1.  (2.5)

As the definition suggests, one should think of F_{η}^{(k)}[Ω] as the subset of objects in F [Ω] consisting of exactly k “indecomposable” elements (components).

An immediate induction on

∥Ω∥ = ∥(Ω^{(1)}, Ω^{(2)}, …, Ω^{(r)})∥ := ∑_{j=1}^{r} |Ω^{(j)}|  (2.6)

4As already remarked in the introduction, it would be easy to generalise our set-up to cover weighted multisort species in full generality, by relaxing the condition that F [Ω] needs to be finite, and requiring instead that each preimage w_{Ω}^{−1}(λ) is finite and that the ring Λ is multiplicatively finite, in the sense that the number of different product representations of λ ∈ Λ is always finite.

5For a non-negative integer n, we write [n] for the standard set {1, 2, …, n} of cardinality n.

shows that

F_{η}^{(k)}[Ω] = ∅, k > ∥Ω∥.  (2.7)

Again, by definition, F_{η}^{(k)} is just a map from Ob(Set^{r}) to Ob(Set). In Lemma 16 in Section 5 we shall show that F_{η}^{(k)} is in fact a functor, that is, an r-sort species.

It is not difficult to see that, for any Ω ∈ Ob(Set^{r}), the sets F_{η}^{(k)}[Ω] with k = 0, 1, 2, … cover all of F [Ω].

Proposition 2. For every Ω ∈ Ob(Set^{r}), we have

F [Ω] = ⋃_{k≥0} F_{η}^{(k)}[Ω].  (2.8)

The proof of Proposition 2 can be found in Section 6.

In [9], a second axiom, (D2), was imposed on the composition operators η for obtaining a refined exponential principle that takes into account the filtration given by the sets F_{η}^{(k)}[Ω] appearing on the right-hand side of (2.8) (for the case of 1-sort species): it required pairwise disjointness of the sets F_{η}^{(k)}[Ω] for k = 0, 1, 2, . . .. The proposition below says that, actually, this assertion is a consequence of Axiom (D1) (within the general set-up), and this is even true for multisort species.

Proposition 3. If F : Set^{r} → Set is an r-sort species and η is a composition operator for F, then we have, for^{6} k, ℓ ∈ ℕ_{0} and k ≠ ℓ,

F_{η}^{(k)}[Ω] ∩ F_{η}^{(ℓ)}[Ω] = ∅, Ω ∈ Ob(Set^{r}).  (2.9)

Proposition 3 is also proved in Section 6. Its proof depends crucially on the fact that “η-bracketings” of F -sets and F_{η}-sets do not depend on the order of the terms F [Ω] respectively F_{η}[Ω] involved, nor on the type of bracketing used; see Lemmas 11 and 15 in Sections 3 and 5, respectively. From a technical point of view, this is the decisive improvement over the results in [9], and it is the reason that the dependence of Axiom (D2) from Axiom (D1) was not observed there.

Given a Λ-weight w on (F, η), the above propositions allow us to refine the weighting to

w̃_{Ω}(x) := y^{k}w_{Ω}(x), x ∈ F_{η}^{(k)}[Ω].

We then can define the refined generating function

G̃F_{F} (z_{1}, …, z_{r}, y) := ∑_{n_{1},...,n_{r}≥0} ∑_{x∈F [([n_{1}],...,[n_{r}])]} w̃_{([n_{1}],...,[n_{r}])}(x) \frac{z_{1}^{n_{1}} ⋯ z_{r}^{n_{r}}}{n_{1}! ⋯ n_{r}!}

= ∑_{n_{1},...,n_{r}≥0} ∑_{k≥0} ∑_{x∈F_{η}^{(k)}[([n_{1}],...,[n_{r}])]} y^{k} w_{([n_{1}],...,[n_{r}])}(x) \frac{z_{1}^{n_{1}} ⋯ z_{r}^{n_{r}}}{n_{1}! ⋯ n_{r}!} .

With the above notation, we have the following refinement of Theorem 1, which is our second main result.

Theorem 4. Under the hypotheses of Theorem 1, we have

G̃F_{F} (z_{1}, …, z_{r}, y) = exp (y GF_{F_{η}}(z_{1}, …, z_{r})),  (2.10)

6We denote by ℕ_{0} the set of non-negative integers.

as well as

G̃F_{F} (z_{1}, …, z_{r}, y) = ( GF_{F} (z_{1}, …, z_{r}))^{y}.  (2.11)

The proof of Theorem 4 is given in Section 6, as a simple consequence of (the proof of) Proposition 3.

3. Auxiliary results, I

The purpose of this section is to establish several lemmas, which will be needed in the next section in the proof of Theorem 1. At the same time, they also form the basis for the proofs of the auxiliary results in Section 5, which eventually will lead to proofs of Propositions 2 and 3, and of Theorem 4, in Section 6. In all of this section, we assume that F is a decomposable r-sort species with composition operator η.

Lemma 5. We have |F [∅∅∅]| = 1.

Proof. By the injectivity of η_{(∅ ∅ ∅,∅ ∅ ∅)} : F [∅∅∅]×F [∅∅∅] → F [∅∅∅], the set F [∅∅∅] is either empty or a 1set. Suppose that F [∅∅∅] = ∅. Choose Ω_{1} = (Ω_{1}^{(1)}, …, Ω_{1}^{(r)}) ∈ Ob(Set^{r}) with F [Ω_{1}] ≠ ∅, and Ω_{2} = (Ω_{2}^{(1)}, …, Ω_{2}^{(r)}) ∈ Ob(Set^{r}) such that Ω_{1} ∩ Ω_{2} = ∅∅∅ and |Ω_{1}^{(i)}| = |Ω_{2}^{(i)}| for 1 ≤ i ≤ r. Now consider (D1) for the partition Ω := Ω_{1} ⨿ Ω_{2}, Ω̃_{i} := Ω_{i} for i = 1, 2. By the functoriality of F, we also have F [Ω_{2}] ≠ ∅ and, consequently, the left-hand side of (2.3) is non-empty, whereas the right-hand side of (2.3) would be empty in case F [∅∅∅] = ∅, a contradiction. □

Lemma 6 (Commutativity for (F, η)). For every pair (Ω_{1}, Ω_{2}) ∈ Ob(𝔇_{r}), we have

η(F [Ω_{1}] × F [Ω_{2}]) = η(F [Ω_{2}] × F [Ω_{1}]).  (3.1)

Proof. Applying Axiom (D1) to the partitions

Ω := Ω_{1} ⨿ Ω_{2} = Ω_{2} ⨿ Ω_{1},

we find that

ℑ := η(F [Ω_{1}] × F [Ω_{2}]) ∩ η(F [Ω_{2}] × F [Ω_{1}])
= η(η(F [Ω_{1} ∩ Ω_{2}] × F [Ω_{1}]) × η(F [Ω_{2}] × F [Ω_{1} ∩ Ω_{2}])).

By Lemma 5 and injectivity of the η-maps, the map

η_{(∅ ∅ ∅,Ω_{1})} : F [∅∅∅] × F [Ω_{1}] → F [Ω_{1}]

is surjective; that is,

η(F [Ω_{1} ∩ Ω_{2}] × F [Ω_{1}]) = F [Ω_{1}].

Similarly, we have

η(F [Ω_{2}] × F [Ω_{1} ∩ Ω_{2}]) = F [Ω_{2}].

Thus,

ℑ = η(F [Ω_{1}] × F [Ω_{2}]).

By an analogous application of (D1) and Lemma 5 to the partitions

Ω = Ω_{2} ⨿ Ω_{1} = Ω_{1} ⨿ Ω_{2},

we find that

ℑ = η(F [Ω_{2}] × F [Ω_{1}]),

and the proof is complete. □

Lemma 7 (3-Associativity for (F, η)). For pairwise disjoint Ω_{1}, Ω_{2}, Ω_{3} ∈ Ob(Set^{r}), we have

η(η(F [Ω_{1}] × F [Ω_{2}]) × F [Ω_{3}]) = η(F [Ω_{1}] × η(F [Ω_{2}] × F [Ω_{3}])).  (3.2)

Proof. We shall show that both sides of (3.2) equal the intersection

ℑ := η(F [Ω_{1} ⨿ Ω_{2}] × F [Ω_{3}]) ∩ η(F [Ω_{1}] × F [Ω_{2} ⨿ Ω_{3}]).

Applying (D1) to the partitions

Ω := (Ω_{1} ⨿ Ω_{2}) ⨿ Ω_{3} = Ω_{1} ⨿ (Ω_{2} ⨿ Ω_{3}),

we find that

ℑ = η(η(F [Ω_{1}] × F [Ω_{2}]) × η(F [Ω_{1} ∩ Ω_{3}] × F [Ω_{3}]));

and, arguing as in the proof of Lemma 6, this equation simplifies to

ℑ = η(η(F [Ω_{1}] × F [Ω_{2}]) × F [Ω_{3}]).

The same argument, when applied to the partitions

Ω = Ω_{1} ⨿ (Ω_{2} ⨿ Ω_{3}) = (Ω_{1} ⨿ Ω_{2}) ⨿ Ω_{3},

yields

ℑ = η(F [Ω_{1}] × η(F [Ω_{2}] × F [Ω_{3}])),

whence (3.2). □

For the sake of convenience, for pairwise disjoint elements Ω_{1}, …, Ω_{m} ∈ Ob(Set^{r}), let us call expressions formed by applying η-maps to F [Ω_{1}], …, F [Ω_{m}] (in any order), with each set F [Ω_{i}] occurring exactly once, an η-bracketing of F [Ω_{1}], …, F [Ω_{m}]. More formally, for any Ω ∈ Ob(Set^{r}), we call the set F [Ω] an η-bracketing of F [Ω]; and, given an η-bracketing B_{1} of F [Ω_{i_{1}}], …, F [Ω_{i_{k}}] and an η-bracketing B_{2} of F [Ω_{i_{k+1}}], …, F [Ω_{i_{m}}], with 1 ≤ k ≤ n − 1 and {i_{1}, i_{2}, …, i_{m}} = {1, 2, …, m}, the expression η(B_{1} × B_{2}) is, by definition, an η-bracketing of F [Ω_{1}], …, F [Ω_{m}]. For example, the left-hand side and the right-hand side of (3.2) are two possible η-bracketings of F [Ω_{1}], F [Ω_{2}], F [Ω_{3}], as are

η(η(F [Ω_{3}] × F [Ω_{2}]) × F [Ω_{1}]) and η(F [Ω_{3}] × η(F [Ω_{1}] × F [Ω_{2}])).

A simple consequence of Lemma 6 and (the proof of) Lemma 7 is the following fact.

Corollary 8. All η-bracketings of F [Ω_{1}], F [Ω_{2}], F [Ω_{3}] are equal to

η(F [Ω_{1} ⨿ Ω_{2}] × F [Ω_{3}]) ∩ η(F [Ω_{1} ⨿ Ω_{3}] × F [Ω_{2}]) ∩ η(F [Ω_{2} ⨿ Ω_{3}] × F [Ω_{1}]). (3.3)

Proof. From the proof of Lemma 7, we know that

η(η(F [Ω_{1}] × F [Ω_{2}]) × F [Ω_{3}]) = η(F [Ω_{1} ⨿ Ω_{2}] × F [Ω_{3}]) ∩ η(F [Ω_{1}] × F [Ω_{2} ⨿ Ω_{3}]).

If, in this equation, we interchange Ω_{1} and Ω_{2} and use Lemma 6 (commutativity), then we obtain

η(η(F [Ω_{1}] × F [Ω_{2}]) × F [Ω_{3}]) = η(F [Ω_{1} ⨿ Ω_{2}] × F [Ω_{3}]) ∩ η(F [Ω_{2}] × F [Ω_{1} ⨿ Ω_{3}]).

Both equations together, plus another application of Lemma 6, imply our claim. □

Lemma 9 (4-Permutability for (F, η)). If Ω_{1}, Ω_{2}, Ω_{3}, Ω_{4} are pairwise disjoint elements of Ob(Set^{r}), then all η-bracketings of F [Ω_{1}], F [Ω_{2}], F [Ω_{3}], F [Ω_{4}] are equal to each other.

Proof. The possible η-bracketings of F [Ω_{1}], F [Ω_{2}], F [Ω_{3}], F [Ω_{4}] are

η(η(η(F [Ω_{1}] × F [Ω_{2}]) × F [Ω_{3}]) × F [Ω_{4}]),  (3.4)
η(η(F [Ω_{1}] × η(F [Ω_{2}] × F [Ω_{3}])) × F [Ω_{4}]),  (3.5)
η(η(F [Ω_{1}] × F [Ω_{2}]) × η(F [Ω_{3}] × F [Ω_{4}])),  (3.6)
η(F [Ω_{1}] × η(η(F [Ω_{2}] × F [Ω_{3}]) × F [Ω_{4}])),  (3.7)
η(F [Ω_{1}] × η(F [Ω_{2}] × η(F [Ω_{3}] × F [Ω_{4}]))),  (3.8)

together with all expressions arising from the above by permuting F [Ω_{1}], F [Ω_{2}], F [Ω_{3}], F [Ω_{4}]. By Lemma 7 (3-associativity), the bracketing (3.4) equals the bracketing (3.5), and the bracketing (3.7) equals the bracketing (3.8). It suffices therefore to prove the equality of (3.4), (3.6), (3.8), and all expressions arising from these three by permuting F [Ω_{1}], F [Ω_{2}], F [Ω_{3}], F [Ω_{4}].

Applying (D1) to the partitions

Ω := (Ω_{1} ⨿ Ω_{2}) ⨿ (Ω_{3} ⨿ Ω_{4}) = (Ω_{1} ⨿ Ω_{3}) ⨿ (Ω_{2} ⨿ Ω_{4}),

we find that

η(F [Ω_{1} ⨿ Ω_{2}] × F [Ω_{3} ⨿ Ω_{4}]) ∩ η(F [Ω_{1} ⨿ Ω_{3}] × F [Ω_{2} ⨿ Ω_{4}])

= η(η(F [Ω_{1}] × F [Ω_{2}]) × η(F [Ω_{3}] × F [Ω_{4}])).

Using this equation, as well as the one which arises by interchanging Ω_{1} and Ω_{2} and applying Lemma 6 (commutativity) on the resulting right-hand side, we obtain

η(η(F [Ω_{1}] × F [Ω_{2}]) × η(F [Ω_{3}] × F [Ω_{4}]))

= η(F [Ω_{1} ⨿ Ω_{2}] × F [Ω_{3} ⨿ Ω_{4}]) ∩ η(F [Ω_{1} ⨿ Ω_{3}] × F [Ω_{2} ⨿ Ω_{4}])

∩ η(F [Ω_{2} ⨿ Ω_{3}] × F [Ω_{1} ⨿ Ω_{4}]). (3.9)

On the other hand, by Corollary 8, the expression

η(η(F [Ω_{1}] × F [Ω_{2}]) × F [Ω_{3}])

equals the expression (3.3). Therefore, “bracketing” these two expressions by η( . × F [Ω_{4}]), using the injectivity of η, and applying Lemma 7 (3-associativity) to the expression resulting from (3.3), we arrive at

η(η(η(F [Ω_{1}] × F [Ω_{2}]) × F [Ω_{3}]) × F [Ω_{4}])

= η(F [Ω_{1} ⨿ Ω_{2}] × η(F [Ω_{3}] × F [Ω_{4}])) ∩ η(F [Ω_{1} ⨿ Ω_{3}] × η(F [Ω_{2}] × F [Ω_{4}]))

∩ η(F [Ω_{2} ⨿ Ω_{3}] × η(F [Ω_{1}] × F [Ω_{4}])). (3.10)

Since η(F [Ω_{3}]×F [Ω_{4}]) ⊆ F [Ω_{3}⨿Ω_{4}], and similar inclusions hold for other combinations of the Ω_{i}’s, we have

η(F [Ω_{1} ⨿ Ω_{2}] × η(F [Ω_{3}] × F [Ω_{4}])) ⊆ η(F [Ω_{1} ⨿ Ω_{2}] × F [Ω_{3} ⨿ Ω_{4}]),
η(F [Ω_{1} ⨿ Ω_{3}] × η(F [Ω_{2}] × F [Ω_{4}])) ⊆ η(F [Ω_{1} ⨿ Ω_{3}] × F [Ω_{2} ⨿ Ω_{4}]),
η(F [Ω_{2} ⨿ Ω_{3}] × η(F [Ω_{1}] × F [Ω_{4}])) ⊆ η(F [Ω_{2} ⨿ Ω_{3}] × F [Ω_{1} ⨿ Ω_{4}]).

Altogether, these inclusions imply that the right-hand side of (3.10) is contained in the right-hand side of (3.9). We infer that

η(η(η(F [Ω_{1}] × F [Ω_{2}]) × F [Ω_{3}]) × F [Ω_{4}]) ⊆ η(η(F [Ω_{1}] × F [Ω_{2}]) × η(F [Ω_{3}] × F [Ω_{4}])).

(3.11)

However, by injectivity of the η-maps, both sides of (3.11) have cardinality

|F [Ω_{1}]| · |F [Ω_{2}]| · |F [Ω_{3}]| · |F [Ω_{4}]|.

Hence, they must be equal, which proves the equality of (3.4) and (3.6).

An analogous argument proves equality of (3.6) and (3.8).

Since, by Lemma 6 (commutativity), the right-hand side of (3.9) is invariant under permutation of Ω_{1}, Ω_{2}, Ω_{3}, Ω_{4}, the proof is complete. □

The (proof of the) above lemma, combined with Lemma 6 and Corollary 8, leads to the following observation.

Corollary 10. All η-bracketings of F [Ω_{1}], F [Ω_{2}], F [Ω_{3}], F [Ω_{4}] are equal to

η(F [Ω_{1} ⨿ Ω_{2}] × F [Ω_{3} ⨿ Ω_{4}]) ∩ η(F [Ω_{1} ⨿ Ω_{3}] × F [Ω_{2} ⨿ Ω_{4}])

∩ η(F [Ω_{2} ⨿ Ω_{3}] × F [Ω_{1} ⨿ Ω_{4}])
∩ η(F [Ω_{1}] × F [Ω_{2} ⨿ Ω_{3} ⨿ Ω_{4}]) ∩ η(F [Ω_{2}] × F [Ω_{1} ⨿ Ω_{3} ⨿ Ω_{4}])

∩ η(F [Ω_{3}] × F [Ω_{1} ⨿ Ω_{2} ⨿ Ω_{4}]) ∩ η(F [Ω_{4}] × F [Ω_{1} ⨿ Ω_{2} ⨿ Ω_{3}]). (3.12)

Proof. By Corollary 8, we have

η(F [Ω_{1} ⨿ Ω_{2}] × η(F [Ω_{3}] × F [Ω_{4}]))

= η(F [Ω_{1} ⨿ Ω_{2} ⨿ Ω_{3}] × F [Ω_{4}]) ∩ η(F [Ω_{1} ⨿ Ω_{2} ⨿ Ω_{4}] × F [Ω_{3}])
∩ η(F [Ω_{3} ⨿ Ω_{4}] × F [Ω_{1} ⨿ Ω_{2}]).

Analogous identities hold for the other two terms on the right-hand side of (3.10). If we combine this with Lemma 6 (commutativity) and Lemma 9 (4-permutability), then the claim follows immediately. □

Before we state the general permutability result, let us introduce the following shorthand notation, which will be used in its proof. Given a subset I of [m], where I = {i_{1}, i_{2}, …, i_{k}} with i_{1} < i_{2} < ⋯ < i_{k}, we let Ω_{I} stand for Ω_{i_{1}} ⨿ ⋯ ⨿ Ω_{i_{k}}.

Lemma 11 (m-Permutability for (F, η)). If Ω_{1}, …, Ω_{m} are pairwise disjoint elements of Ob(Set^{r}), then all η-bracketings of F [Ω_{1}], …, F [Ω_{m}] are equal to each other.

Proof. We shall prove by induction on m that, for each m ≥ 2, all η-bracketings of F [Ω_{1}], …, F [Ω_{m}] equal

⋂_{I,J⊆[m]} ; I∪J=[m], I∩J=∅ ; I≠∅≠Jη(F [Ω_{I}] × F [Ω_{J}]).  (3.13)

For m = 2, the assertion follows from Lemma 6 (commutativity). For m = 3, the assertion is equivalent to Corollary 8 (again, modulo Lemma 6), and for m = 4, the assertion is equivalent to Corollary 10.

Now let m ≥ 5, and let us suppose that the assertion is true up to m − 1. Consider an η-bracketing of Ω_{1}, …, Ω_{m}. There are three possibilities. Either this bracketing has the form

η(η(E_{1}) × η(E_{2})),  (3.14)

where E_{1} and E_{2} are expressions involving η-maps and distinct Ω_{i}’s, each of them involving at least two Ω_{i}’s, or the form

η(F [Ω_{i}] × η(E_{3})),  (3.15)

where E_{3} involves η-maps and Ω_{1}, …, Ω_{i−1}, Ω_{i+1}, …, Ω_{m}, for some i, or the form

η(η(E_{4}) × F [Ω_{i}]),  (3.16)

where E_{4} involves η-maps and Ω_{1}, …, Ω_{i−1}, Ω_{i+1}, …, Ω_{m}, for some i.

We start by considering (3.14). Let us assume that E_{1} involves all Ω_{r}’s for r ∈ R, and E_{2} involves all Ω_{s}’s for s ∈ S, with R ∪ S = [m], R ∩ S = ∅, R ≠ ∅ ≠ S. By the inductive hypothesis, we know that

η(E_{1}) = _{⋂_{I_{1},J_{1}⊆R} ; I_{1}∪J_{1}=R, I_{1}∩J_{1}=∅ ; I_{1}≠∅≠J_{1}}η(F [Ω_{I_{1}}] × F [Ω_{J_{1}}])  (3.17)

and

η(E_{2}) = _{⋂_{I_{2},J_{2}⊆S} ; I_{2}∪J_{2}=S, I_{2}∩J_{2}=∅ ; I_{2}≠∅≠J_{2}}η(F [Ω_{I_{2}}] × F [Ω_{J_{2}}]).  (3.18)

If we substitute (3.17) and (3.18) in (3.14) and use injectivity of the η-maps, then we obtain

⋂_{I_{1},J_{1}⊆R} ; I_{1}∪J_{1}=R, I_{1}∩J_{1}=∅ ; I_{1}≠∅≠J_{1} _{⋂_{I_{2},J_{2}⊆S} ; I_{2}∪J_{2}=S, I_{2}∩J_{2}=∅ ; I_{2}≠∅≠J_{2}}η(η(F [Ω_{I_{1}}] × F [Ω_{J_{1}}]) × η(F [Ω_{I_{2}}] × F [Ω_{J_{2}}])).

We may now apply Corollary 10 to each of the terms on the right-hand side of this equation. It is not difficult to see that, together with Lemma 6 (commutativity), we obtain (3.13).

Next we consider (3.15). By the inductive hypothesis, we know that

η(E_{3}) = _{⋂_{I,J⊆[m]−{i}} ; I∪J=[m]−{i}, I∩J=∅ ; I≠∅≠J}η(F [Ω_{I}] × F [Ω_{J}]).

If we substitute this in (3.15) and use injectivity of the η-maps, then we obtain

⋂_{I,J⊆[m]−{i}} ; I∪J=[m]−{i}, I∩J=∅ ; I≠∅≠Jη(F [Ω_{i}] × η(F [Ω_{I}] × F [Ω_{J}])).

We may now apply Corollary 8 to each of the terms on the right-hand side of this equation. It is not difficult to see that, together with Lemma 6 (commutativity), we obtain (3.13).

The argument for (3.16) is analogous. This completes the proof of the lemma. □

For Ω = (Ω^{(1)}, …, Ω^{(r)}) ∈ Ob(Set^{r}) and an integer ρ ∈ [r], we write (ω, ρ) ∈ Ω to mean ω ∈ Ω^{(ρ)}. This is the concept of base point needed in the present context.

Lemma 12. For non-empty Ω ∈ Ob(Set^{r}) and every choice of base point (ω, ρ) ∈ Ω, we have

F [Ω] = _{⋃_{Ω_{1}∈Ob(Set^{r})} (ω,ρ)∈Ω_{1}⊆Ω}η(F_{η}[Ω_{1}] × F [Ω − Ω_{1}]).  (3.19)

Proof. Let x ∈ F [Ω] be an arbitrary element, and consider the totality of all Ω_{1} ∈ Ob(Set^{r}) such that (ω, ρ) ∈ Ω_{1} ⊆ Ω and x ∈ η(F [Ω_{1}] × F [Ω − Ω_{1}]). Such Ω_{1}’s do exist; for instance Ω_{1} = Ω has these properties, since the map

η_{(Ω,∅ ∅ ∅)} : F [Ω] × F [∅∅∅] ↪ F [Ω]

is surjective. Among these Ω_{1}’s we choose one of minimal norm ∥Ω_{1}∥ (recall the definition in (2.6)), say Ω_{1}(x). Now suppose that x ∉ η(F_{η}[Ω_{1}(x)] × F [Ω − Ω_{1}(x)]). Then, by the definition of F_{η}, the injectivity of η, and the choice of Ω_{1}(x), we must have

x ∈ η((F [Ω_{1}(x)] − F_{η}[Ω_{1}(x)]) × F [Ω − Ω_{1}(x)])

= _{⋃_{(I,J)∈Ob(𝔇_{r})} ; I⨿J=Ω_{1}(x) ; I≠∅ ∅ ∅≠J}η(η(F [I] × F [J]) × F [Ω − Ω_{1}(x)]).

Consequently, there exists (I_{1}, J_{1}) ∈ Ob(𝔇_{r}) such that I_{1} ⨿ J_{1} = Ω_{1}(x), I_{1} ≠ ∅∅∅ ≠ J_{1}, and

x ∈ η(η(F [I_{1}] × F [J_{1}]) × F [Ω − Ω_{1}(x)]).

Using Corollary 8 (3-permutability), we see that the latter set is contained in both η(F [I_{1}] × F [Ω − I_{1}]) and η(F [J_{1}] × F [Ω − J_{1}]). The base point (ω, ρ) is contained in I_{1} or J_{1}; to fix ideas, say (ω, ρ) ∈ I_{1}. Hence, we arrive at the assertion that

x ∈ η(F [I_{1}] × F [Ω − I_{1}]), (ω, ρ) ∈ I_{1} ⊆ Ω, ∥I_{1}∥ < ∥Ω_{1}(x)∥,

contradicting the choice of Ω_{1}(x). We conclude that x is indeed contained in

η(F_{η}[Ω_{1}(x)] × F [Ω − Ω_{1}(x)]),

and (3.19) is proven. □

Lemma 13. The right-hand side of (3.19) is a disjoint union.

Proof. In the context of Lemma 12, let Ω_{1}, Ω_{2} ∈ Ob(Set^{r}) be such that (ω, ρ) ∈ Ω_{i} ⊆ Ω and Ω_{1} ≠ Ω_{2}, say Ω_{1} ⊈ Ω_{2}. It is enough to show that

ℑ := η(F [Ω_{1}] × F [Ω − Ω_{1}]) ∩ η(F [Ω_{2}] × F [Ω − Ω_{2}])

has an empty intersection with η(F_{η}[Ω_{1}] × F [Ω − Ω_{1}]). But, by (D1), we have

ℑ ⊆ η(η(F [Ω_{1} ∩ Ω_{2}] × F [Ω_{1} − Ω_{2}]) × F [Ω − Ω_{1}]),

and, by definition of F_{η} and the fact that (ω, ρ) ∈ Ω_{1} ∩ Ω_{2} ≠ ∅∅∅ ≠ Ω_{1} − Ω_{2}, we have

F_{η}[Ω_{1}] ∩ η(F [Ω_{1} ∩ Ω_{2}] × F [Ω_{1} − Ω_{2}]) = ∅.

Consequently, by the injectivity of η, we must indeed have

η(F_{η}[Ω_{1}] × F [Ω − Ω_{1}]) ∩ ℑ

⊆ η(F_{η}[Ω_{1}] × F [Ω − Ω_{1}]) ∩ η(η(F [Ω_{1} ∩ Ω_{2}] × F [Ω_{1} − Ω_{2}]) × F [Ω − Ω_{1}]) = ∅,

as required. □

Lemma 14 (Functoriality of F_{η}). Let Ω, Ω̃ ∈ Ob(Set^{r}), and let f : Ω → Ω̃ be a morphism. Then

F [f](F_{η}[Ω]) = F_{η}[Ω̃];

that is, setting F_{η}[f] := F [f]|_{F_{η}[Ω]}, we get a functor F_{η} : Set^{r} → Set.

Proof. The assertion is obvious if Ω = ∅∅∅, so we may suppose that Ω ≠ ∅∅∅. Then, using the naturality of η (that is, the diagram (2.2)), we have

F [f](F_{η}[Ω]) = F [f](F [Ω] − _{⋃_{(I_{1},J_{1})∈Ob(𝔇_{r})} ; I_{1}⨿J_{1}=Ω ; I_{1}≠∅ ∅ ∅≠J_{1}}η(F [I_{1}] × F [J_{1}]))

= F [Ω̃] − _{⋃_{(I_{1},J_{1})∈Ob(𝔇_{r})} ; I_{1}⨿J_{1}=Ω ; I_{1}≠∅ ∅ ∅≠J_{1}}(F ∘ ⨿)[(f|_{I_{1}}, f|_{J_{1}})](η(F [I_{1}] × F [J_{1}]))

= F [Ω̃] − _{⋃_{(I_{1},J_{1})∈Ob(𝔇_{r})} ; I_{1}⨿J_{1}=Ω ; I_{1}≠∅ ∅ ∅≠J_{1}}η(F [f|_{I_{1}}](F [I_{1}]) × F [f|_{J_{1}}](F [J_{1}]))

= F [Ω̃] − _{⋃_{(I_{2},J_{2})∈Ob(𝔇_{r})} ; I_{2}⨿J_{2}=Ω̃ ; I_{2}≠∅ ∅ ∅≠J_{2}}η(F [I_{2}] × F [J_{2}])

= F [Ω̃].

□

4. Proof of Theorem 1

For convenience, let us “extend” the Λ-weight w to subsets of F [Ω], for all Ω ∈ Ob(Set^{r}). To be precise, for A ⊆ F [Ω], we define

w_{Ω}(A) := ∑_{x∈A} w_{Ω}(x).

Given disjoint Ω_{1}, Ω_{2} ∈ Ob(Set^{r}) and subsets A_{1} ⊆ F_{η}[Ω_{1}] and A_{2} ⊆ F [Ω_{2}], Axiom (W2) says that

w_{Ω_{1}⨿Ω_{2}}(η(A_{1} × A_{2})) = w_{Ω_{1}}(A_{1}) · w_{Ω_{2}}(A_{2}).  (4.1)

In the sequel, we shall suppress the indices of weights w for better readability, the indices always being clear from the context.

As a direct consequence of Lemmas 12 and 13, of the injectivity of the η-maps, and of (4.1), we have that, for n_{1}, n_{2}, …, n_{r} ∈ ℕ_{0} and n_{ρ} > 0,

w(F [([n_{1}], …, [n_{r}])])

= _{∑_{Ω_{1}^{(i)}⊆[n_{i}] (1≤i≤r)} ; 1∈Ω_{1}^{(ρ)}} w(F_{η}[(Ω_{1}^{(1)}, …, Ω_{1}^{(r)})]) · w(F [([n_{1}] − Ω_{1}^{(1)}, …, [n_{r}] − Ω_{1}^{(r)})]). (4.2)

Using the functoriality of F and F_{η}, together with Axiom (W1), each Ω_{1} with

Ω_{1} = (Ω_{1}^{(1)}, …, Ω_{1}^{(r)}) ⊆ ([n_{1}], …, [n_{r}]),

(1, ρ) ∈ Ω_{1}, and cardinalities |Ω_{1}^{(i)}| = μ_{i} (1 ≤ i ≤ r), is seen to contribute

w(F_{η}[([μ_{1}], …, [μ_{r}])]) · w(F [([n_{1} − μ_{1}], …, [n_{r} − μ_{r}])])  (4.3)

to the right-hand side of (4.2). We observe that (4.3) does not depend upon Ω_{1} itself, but only on the cardinalities μ_{1}, …, μ_{r} of the components Ω_{1}^{(1)}, …, Ω_{1}^{(r)}. Therefore, the

\frac{μ_{ρ}}{n_{ρ}} ∏_{1≤i≤r} \binom{n_{i}}{μ_{i}}

elements Ω_{1} ∈ Ob(Set^{r}) with Ω_{1} ⊆ ([n_{1}], …, [n_{r}]), (1, ρ) ∈ Ω_{1}, and such that |Ω_{1}^{(i)}| = μ_{i} for 1 ≤ i ≤ r, contribute

\frac{μ_{ρ}}{n_{ρ}} ( ∏_{1≤i≤r} \binom{n_{i}}{μ_{i}})w(F_{η}[([μ_{1}], …, [μ_{r}])]) · w(F [([n_{1} − μ_{1}], …, [n_{r} − μ_{r}])])

to the right-hand side of (4.2), and we obtain

w(F [([n_{1}], …, [n_{r}])]) = ∑_{0≤μ_{i}≤n_{i} (1≤i≤r)} \frac{μ_{ρ}}{n_{ρ}} ( ∏_{1≤i≤r} \binom{n_{i}}{μ_{i}})w(F_{η}[([μ_{1}], …, [μ_{r}])])

· w(F [([n_{1} − μ_{1}], …, [n_{r} − μ_{r}])]),
n_{ρ} > 0,

or, equivalently,

n_{ρ} · w(F [([n_{1}], …, [n_{r}])]) = ∑_{0≤μ_{i}≤n_{i} (1≤i≤r)} μ_{ρ}( ∏_{1≤i≤r} \binom{n_{i}}{μ_{i}})w(F_{η}[([μ_{1}], …, [μ_{r}])])

· w(F [([n_{1} − μ_{1}], …, [n_{r} − μ_{r}])]), (4.4)

as long as n_{ρ} > 0. However, Equation (4.4) holds as well for n_{ρ} = 0, with both sides vanishing, so that we are allowed to drop the restriction n_{ρ} > 0.

Fix ρ ∈ [r], multiply both sides of (4.4) by

z_{1}^{n_{1}} ⋯ z_{ρ−1}^{n_{ρ−1}}z_{ρ}^{n_{ρ}−1}z_{ρ+1}^{n_{ρ+1}} ⋯ z_{r}^{n_{r}}/(n_{1}! ⋯ n_{r}!),

and sum over all tuples (n_{1}, …, n_{r}) ∈ ℕ_{0}^{r}, to get

∑_{n_{1},...,n_{r}≥0} w(F [([n_{1}], …, [n_{r}])]) \frac{z_{1}^{n_{1}} ⋯ z_{ρ−1}^{n_{ρ−1}}z_{ρ}^{n_{ρ}−1}z_{ρ+1}^{n_{ρ+1}} ⋯ z_{r}^{n_{r}}}{n_{1}! ⋯ n_{ρ−1}! (n_{ρ} − 1)! n_{ρ+1}! ⋯ n_{r}!}

= ∑_{n_{1},...,n_{r}≥0} ∑_{0≤μ_{i}≤n_{i} (1≤i≤r)} \frac{w(F_{η}[([μ_{1}], …, [μ_{r}])])}{μ_{1}! ⋯ μ_{ρ−1}! (μ_{ρ} − 1)! μ_{ρ+1}! ⋯ μ_{r}!}

· \frac{w(F [([n_{1} − μ_{1}], …, [n_{r} − μ_{r}])])}{(n_{1} − μ_{1})! ⋯ (n_{r} − μ_{r})!} z_{1}^{n_{1}} ⋯ z_{ρ−1}^{n_{ρ−1}}z_{ρ}^{n_{ρ}−1}z_{ρ+1}^{n_{ρ+1}} ⋯ z_{r}^{n_{r}}, (4.5)

where 1/(−1)! has to be interpreted as 0. The left-hand side equals

\frac{∂ GF_{F}}{∂z_{ρ}} ,

while the right-hand side is identified as

\frac{∂ GF_{F_{η}}}{∂z_{ρ}} GF_{F};

whence the equations

\frac{∂ GF_{F}}{∂z_{ρ}} = \frac{∂ GF_{F_{η}}}{∂z_{ρ}} GF_{F} ,  1 ≤ ρ ≤ r.  (4.6)

Set

Q(z_{1}, …, z_{r}) := GF_{F} (z_{1}, …, z_{r}) exp ( − GF_{F_{η}}(z_{1}, …, z_{r})).

Then, in view of Equations (4.6), the series Q satisfies

\frac{∂Q}{∂z_{ρ}} = 0, 1 ≤ ρ ≤ r.

These last equations force Q to be independent of z_{1}, z_{2}, …, z_{r}. However, since GF_{F_{η}}(0, …, 0) = 0 by definition of F_{η}, and since GF_{F} (0, …, 0) = 1 by Axiom (W0) and Lemma 5, direct inspection shows that

Q(0, 0, …, 0) = 1,

and (2.4) follows. □

5. Auxiliary results, II

In this section, we complement the results of Section 3 by establishing several further results which will be needed in the proofs of Proposition 3 and Theorem 4, to be given in the next section. The first lemma provides the analogue of Lemma 11 for F_{η}, namely that arbitrary permutability holds also for η-bracketings of F_{η}-images (see the subsequent paragraph for the precise definition). All the remaining lemmas concern the maps F_{η}^{(k)}. In all of this section, we assume that F is a decomposable r-sort species with composition operator η.

In complete analogy with the corresponding definition in Section 3, we define the concept of an η-bracketing of F_{η}[Ω_{1}], …, F_{η}[Ω_{m}] for pairwise disjoint elements Ω_{1}, …, Ω_{m} ∈ Ob(Set^{r}): simply replace F by F_{η} everywhere in the definition just after the proof of Lemma 7.

Lemma 15 (m-Permutability for (F_{η}, η)). If Ω_{1}, …, Ω_{m} are pairwise disjoint elements of Ob(Set^{r}), then all η-bracketings of F_{η}[Ω_{1}], …, F_{η}[Ω_{m}] are equal to each other.

Proof. Since F_{η}[∅∅∅] = ∅ by definition of F_{η}, our claim holds if at least one of Ω_{1}, …, Ω_{m} equals ∅∅∅. Hence, we may assume that all of Ω_{1}, …, Ω_{m} are non-empty.

Next we note that, for sets M_{1}, …, M_{m}, A_{1}, …, A_{m}, we have

(M_{1} − A_{1}) × (M_{2} − A_{2}) × ⋯ × (M_{m} − A_{m})

= M_{1} × M_{2} × ⋯ × M_{m} − ( ⋃_{k=1}^{m} M_{1} × ⋯ × M_{k−1} × A_{k} × M_{k+1} × ⋯ × M_{m}). (5.1)

Now assume that we are given two η-bracketings of F_{η}[Ω_{1}], …, F_{η}[Ω_{m}], say

B_{η}(F_{η}[Ω_{1}], …, F_{η}[Ω_{m}]) and B̄_{η}(F_{η}[Ω_{1}], …, F_{η}[Ω_{m}]).

Substituting the definition of F_{η} into B_{η}(F_{η}[Ω_{1}], …, F_{η}[Ω_{m}]), and applying Identity (5.1) plus injectivity of η-maps, we find that

B_{η}(F_{η}[Ω_{1}], …, F_{η}[Ω_{m}]) = B_{η}(F [Ω_{1}], …, F [Ω_{m}])

− ⋃_{k=1}^{m} B_{η}(F [Ω_{1}], …, F [Ω_{k−1}],_{⋃_{(I,J)∈Ob(𝔇_{r})} ; I⨿J=Ω_{k} ; I≠∅ ∅ ∅≠J} η(F [I] × F [J]), F [Ω_{k+1}], …, F [Ω_{m}])

= B_{η}(F [Ω_{1}], …, F [Ω_{m}])

− ⋃_{k=1}^{m} _{⋃_{(I,J)∈Ob(𝔇_{r})} ; I⨿J=Ω_{k} ; I≠∅ ∅ ∅≠J} B_{η}(F [Ω_{1}], …, F [Ω_{k−1}], η(F [I] × F [J]), F [Ω_{k+1}], …, F [Ω_{m}]).

The same argument shows that B̄_{η}(F_{η}[Ω_{1}], …, F_{η}[Ω_{m}]) equals the last expression where every occurrence of B_{η} is replaced by B̄_{η}. By Lemma 11 (m-permutability for (F, η)), we have

B_{η}(F [Ω_{1}], …, F [Ω_{m}]) = B̄_{η}(F [Ω_{1}], …, F [Ω_{m}])

and

B_{η}(F [Ω_{1}], …, F [Ω_{k−1}], η(F [I] × F [J]), F [Ω_{k+1}], …, F [Ω_{m}])

= B̄_{η}(F [Ω_{1}], …, F [Ω_{k−1}], η(F [I] × F [J]), F [Ω_{k+1}], …, F [Ω_{m}]),

hence

B_{η}(F_{η}[Ω_{1}], …, F_{η}[Ω_{m}]) = B̄_{η}(F_{η}[Ω_{1}], …, F_{η}[Ω_{m}]),

which establishes our claim. □

Lemma 16 (Functoriality of F_{η}^{(k)}). For each morphism f : Ω → Ω̃ in Set^{r} and every integer k ≥ 0, we have

F [f](F_{η}^{(k)}[Ω]) = F_{η}^{(k)}[Ω̃].

Proof. We use induction on k, our claim being obvious for k = 0. Suppose that the assertion holds for 0 ≤ k < K with some K ≥ 1. Then, using the definition of F_{η}^{(k)}, the functoriality of F_{η} already demonstrated in Lemma 14, the inductive hypothesis, as well as the naturality of η, we find that

F [f](F_{η}^{(K)}[Ω]) = F [f](_{⋃_{Ω′∈Ob(Set^{r})} Ω′⊆Ω}η(F_{η}[Ω′] × F_{η}^{(K−1)}[Ω − Ω′]))

= _{⋃_{Ω′∈Ob(Set^{r})} Ω′⊆Ω}(F ∘ ⨿)[(f|_{Ω′}, f|_{Ω−Ω′})](η(F_{η}[Ω′] × F_{η}^{(K−1)}[Ω − Ω′]))

= _{⋃_{Ω′∈Ob(Set^{r})} Ω′⊆Ω}η(F [f|_{Ω′}](F_{η}[Ω′]) × F [f|_{Ω−Ω′}](F_{η}^{(K−1)}[Ω − Ω′]))

= _{⋃_{Ω̃′∈Ob(Set^{r})} Ω̃′⊆Ω̃}η(F_{η}[Ω̃′] × F_{η}^{(K−1)}[Ω̃ − Ω̃′])

= F_{η}^{(K)}[Ω̃].

□

Lemma 17. The functors F_{η}^{(1)} and F_{η} coincide.

Proof. It suffices to show that F_{η}^{(1)}[Ω] = F_{η}[Ω] for every Ω ∈ Ob(Set^{r}). By (2.7), this holds if Ω = ∅∅∅, so assume that Ω ≠ ∅∅∅. Then, using the definition of F_{η}^{(k)}, the injectivity of η-maps, Lemma 7 (3-associativity), and Lemma 5, we have

F_{η}^{(1)}[Ω] = _{⋃_{Ω_{1}∈Ob(Set^{r})} Ω_{1}⊆Ω}η(F_{η}[Ω_{1}] × F_{η}^{(0)}[Ω − Ω_{1}])

= η(F_{η}[Ω] × F [∅∅∅])

= η((F [Ω] − _{⋃_{(I,J)∈Ob(𝔇_{r})} ; I⨿J=Ω ; I≠∅ ∅ ∅≠J}η(F [I] × F [J])) × F [∅∅∅])

= η(F [Ω] × F [∅∅∅]) − _{⋃_{(I,J)∈Ob(𝔇_{r})} ; I⨿J=Ω ; I≠∅ ∅ ∅≠J}η(η(F [I] × F [J]) × F [∅∅∅])

= F [Ω] − _{⋃_{(I,J)∈Ob(𝔇_{r})} ; I⨿J=Ω ; I≠∅ ∅ ∅≠J}η(F [I] × F [J])

= F_{η}[Ω],

proving our claim. □

In the next lemma, we require again the concept of a base point, which was introduced just before Lemma 12.

Lemma 18. For every non-empty Ω ∈ Ob(Set^{r}), each choice of base point (ω, ρ) ∈ Ω, and every integer k ≥ 1, we have

F_{η}^{(k)}[Ω] = _{∐_{Ω_{1}∈Ob(Set^{r})} (ω,ρ)∈Ω_{1}⊆Ω}η(F_{η}[Ω_{1}] × F_{η}^{(k−1)}[Ω − Ω_{1}]).  (5.2)

Proof. The fact that the terms on the right-hand side of (5.2) are pairwise disjoint follows from Lemma 13, since a term η(F_{η}[Ω_{1}] × F_{η}^{(k−1)}[Ω − Ω_{1}]) is contained in the larger set η(F_{η}[Ω_{1}] × F [Ω − Ω_{1}]).

An immediate induction using the definition of F_{η}^{(m)} shows that, for all m ≥ 2, we have

F_{η}^{(m)}[Ω] = _{⋃_{Ω_{1},...,Ω_{m}∈Ob(Set^{r})} Ω_{1}⨿···⨿Ω_{m}=Ω} η(F_{η}[Ω_{1}] × η(F_{η}[Ω_{2}] × ⋯ × η(F_{η}[Ω_{m−1}] × F_{η}[Ω_{m}]) ⋯).

(5.3)

We first consider the case where k = 1. Here, by definition of F_{η}^{(0)}[∅∅∅], the only contribution to the union on the right-hand side of (5.2) arises for Ω_{1} = Ω. In that situation, we have

η(F_{η}[Ω] × F_{η}^{(0)}[∅∅∅]) = η(F_{η}[Ω] × F [∅∅∅]).

However, this is also the only contribution on the right-hand side of the definition of F_{η}^{(1)} given in (2.5), thus proving (5.2) for k = 1.

Now we consider the case where k ≥ 2. If k ≥ 3, then, given Ω ∈ Ob(Set^{r}), we substitute the right-hand side of (5.3) with m = k − 1 in (5.2). As a result, we obtain

⋃_{Ω_{1},Ω_{2},...,Ω_{k}∈Ob(Set^{r})} Ω_{1}⨿Ω_{2}⨿···⨿Ω_{k}=Ω (ω,ρ)∈Ω_{1}η(F_{η}[Ω_{1}] × η(F_{η}[Ω_{2}] × ⋯ × η(F_{η}[Ω_{k−1}] × F_{η}[Ω_{k}]) ⋯) (5.4)

for the right-hand side of (5.2). We note that Expression (5.4) also agrees with the right-hand side of (5.2) for k = 2 (taking into account the fact that we already know that the union on the right-hand side of (5.2) is a disjoint union).

Expression (5.4) is almost (5.3) with m = k, except that Ω_{1} is distinguished by having to contain the given base point (ω, ρ). However, by Lemma 15 (m-permutability for (F_{η}, η)), the ordering of Ω_{1}, Ω_{2}, …, Ω_{k} in the η-bracketing in the union on the righthand side of (5.4) is of no relevance. Thus, the restriction that (ω, ρ) ∈ Ω_{1} can be dropped. This shows that the right-hand side of (5.2) equals F_{η}^{(k)}[Ω], as claimed. □

6. Proofs of Propositions 2 and 3, and of Theorem 4

We begin this section with the proof of Proposition 2. With Lemma 18 in hand, we are finally in the position to also establish Proposition 3. Theorem 4 is then a simple consequence of an identity on which the proof of Proposition 3 rests (see (6.1) below). Although the property expressed in this proposition is of a structural nature, our proof relies in fact on a counting argument. It would be desirable to find an alternative approach more in keeping with the actual nature of Proposition 3.

Proof of Proposition 2. We use induction on ∥Ω∥, where ∥ . ∥ has been defined in (2.6). By (2.7) and the definition of F_{η}^{(0)}, the statement holds if ∥Ω∥ = 0, that is, if Ω = ∅∅∅. Let Ω be such that ∥Ω∥ = N for some integer N > 0, and suppose that (2.8) holds for all Ω′ ∈ Ob(Set^{r}) of norm strictly less than N. Then we have Ω ≠ ∅∅∅, and therefore

⋃_{k≥0} F_{η}^{(k)}[Ω] = ⋃_{k≥1} F_{η}^{(k)}[Ω]

= ⋃_{k≥1} _{⋃_{Ω_{1}∈Ob(Set^{r})} Ω_{1}⊆Ω}η(F_{η}[Ω_{1}] × F_{η}^{(k−1)}[Ω − Ω_{1}])

= _{⋃_{Ω_{1}∈Ob(Set^{r})} Ω_{1}⊆Ω}η(F_{η}[Ω_{1}] × ( ⋃_{k≥1} F_{η}^{(k−1)}[Ω − Ω_{1}]))

= _{⋃_{Ω_{1}∈Ob(Set^{r})} ∅ ∅ ∅≠Ω_{1}⊆Ω}η(F_{η}[Ω_{1}] × ( ⋃_{k≥0} F_{η}^{(k)}[Ω − Ω_{1}]))

= _{⋃_{Ω_{1}∈Ob(Set^{r})} Ω_{1}⊆Ω}η(F_{η}[Ω_{1}] × F [Ω − Ω_{1}])

= F [Ω].

Here, we have used Lemma 12 for the last equality, and the inductive hypothesis in the second but last step (here it is important that Ω_{1} ≠ ∅∅∅ in order to guarantee that ∥Ω − Ω_{1}∥ < ∥Ω∥). □

Proof of Proposition 3 and of Theorem 4. For k ≥ 0, let us define the generating function for F_{η}^{(k)} by

GF_{F_{η}^{(k)}}(z_{1}, …, z_{r}) := ∑_{n_{1},...,n_{r}≥0} ∑_{x∈F_{η}^{(k)}[([n_{1}],...,[n_{r}])]} w_{([n_{1}],...,[n_{r}])}(x) \frac{z_{1}^{n_{1}} ⋯ z_{r}^{n_{r}}}{n_{1}! ⋯ n_{r}!} .

Again, in the sequel, we shall suppress the indices to weights w for better readability, the indices always being clear from the context.

The first step consists in showing that

GF_{F_{η}^{(k)}}(z_{1}, …, z_{r}) = \frac{1}{k!}( GF_{F_{η}}(z_{1}, …, z_{r}))^{k}.  (6.1)

By definition of F_{η}^{(0)}, the left-hand side of (6.1) equals 1, so that (6.1) holds for k = 0. Therefore, we may in the sequel assume that k ≥ 1.

We now proceed in a manner similar to the proof of Theorem 1 given in Section 4. Here, however, we use Lemma 18 instead of Lemmas 12 and 13, and we also need the functoriality of F_{η}^{(m)} for m = 0, 1, 2, … established in Lemma 16. In this way, we obtain from (5.2) the identity

n_{ρ} · w(F_{η}^{(k)}[([n_{1}], …, [n_{r}])]) = ∑_{0≤μ_{i}≤n_{i} (1≤i≤r)} μ_{ρ}( ∏_{1≤i≤r} \binom{n_{i}}{μ_{i}})w(F_{η}[([μ_{1}], …, [μ_{r}])])

· w(F_{η}^{(k−1)}[([n_{1} − μ_{1}], …, [n_{r} − μ_{r}])]). (6.2)

Fixing ρ ∈ [r], multiplying both sides of (6.2) by

z_{1}^{n_{1}} ⋯ z_{ρ−1}^{n_{ρ−1}}z_{ρ}^{n_{ρ}−1}z_{ρ+1}^{n_{ρ+1}} ⋯ z_{r}^{n_{r}}/(n_{1}! ⋯ n_{r}!),

and summing over all tuples (n_{1}, …, n_{r}) ∈ ℕ_{0}^{r}, gives

∑_{n_{1},...,n_{r}≥0} w(F_{η}^{(k)}[([n_{1}], …, [n_{r}])]) \frac{z_{1}^{n_{1}} ⋯ z_{ρ−1}^{n_{ρ−1}}z_{ρ}^{n_{ρ}−1}z_{ρ+1}^{n_{ρ+1}} ⋯ z_{r}^{n_{r}}}{n_{1}! ⋯ n_{ρ−1}! (n_{ρ} − 1)! n_{ρ+1}! ⋯ n_{r}!}

= ∑_{n_{1},...,n_{r}≥0} ∑_{0≤μ_{i}≤n_{i} (1≤i≤r)} \frac{w(F_{η}[([μ_{1}], …, [μ_{r}])])}{μ_{1}! ⋯ μ_{ρ−1}! (μ_{ρ} − 1)! μ_{ρ+1}! ⋯ μ_{r}!}

· \frac{w(F_{η}^{(k−1)}[([n_{1} − μ_{1}], …, [n_{r} − μ_{r}])])}{(n_{1} − μ_{1})! ⋯ (n_{r} − μ_{r})!} z_{1}^{n_{1}} ⋯ z_{ρ−1}^{n_{ρ−1}}z_{ρ}^{n_{ρ}−1}z_{ρ+1}^{n_{ρ+1}} ⋯ z_{r}^{n_{r}}, (6.3)

where, again, 1/(−1)! has to be interpreted as 0. The left-hand side equals

\frac{∂ GF_{F_{η}^{(k)}}}{∂z_{ρ}} ,

while the right-hand side is identified as

\frac{∂ GF_{F_{η}}}{∂z_{ρ}} GF_{F_{η}^{(k−1)}},

whence the equations

\frac{∂ GF_{F_{η}^{(k)}}}{∂z_{ρ}} = \frac{∂ GF_{F_{η}}}{∂z_{ρ}} GF_{F_{η}^{(k−1)}},  1 ≤ ρ ≤ r.  (6.4)

Assuming inductively that

GF_{F_{η}^{(k−1)}} = \frac{1}{(k − 1)!}( GF_{F_{η}} )^{k−1},

we infer from (6.4) that

GF_{F_{η}^{(k)}} = \frac{1}{k!}( GF_{F_{η}} )^{k} + C,

where C is independent of z_{1}, z_{2}, …, z_{r}. Making use of the facts that GF_{F_{η}^{(k)}}(0, …, 0) = 0 (since k ≥ 1) and that GF_{F_{η}}(0, …, 0) = 0, we see that C = 0, which proves (6.1).

On the other hand, by Theorem 1, we know that

GF_{F} (z_{1}, z_{2}, …, z_{r}) = exp ( GF_{F_{η}}(z_{1}, z_{2}, …, z_{r})),

or, equivalently,

GF_{F} (z_{1}, z_{2}, …, z_{r}) = ∑_{k≥0} \frac{1}{k!}( GF_{F_{η}}(z_{1}, z_{2}, …, z_{r}))^{k}.  (6.5)

If there were a non-empty intersection between F_{η}^{(k_{1})}[Ω] and F_{η}^{(k_{2})}[Ω], for some k_{1}, k_{2} with k_{1} < k_{2} and some Ω ∈ Ob(Set^{r}), then Proposition 2 would contradict (6.5) and (6.1). This proves the assertion of Proposition 3.

The proof of Theorem 4 is now easily completed. By definition of G̃F_{F} (z_{1}, …, z_{r}, y), we have

G̃F_{F} (z_{1}, …, z_{r}, y) = ∑_{k≥0} y^{k} GF_{F_{η}^{(k)}}(z_{1}, …, z_{r}).

If we now substitute (6.1), then we immediately obtain (2.10). Identity (2.11) results from using Theorem 1 to express GF_{F_{η}}(z_{1}, …, z_{r}) in terms of GF_{F} (z_{1}, …, z_{r}) and substituting the result in (2.10). □

7. Illustrations, I: Three examples

We give here three illustrations for the application of our theory. In the first and second example below, bipartite graphs are considered. Example 1 is, in some sense, “standard,” since it addresses the case where the composition operator η consists in “putting objects together,” so that the combinatorial objects in our (in this case, 2-sort) species are sets of indecomposable objects, a situation which is well covered by classical species theory. In Example 2, however, the composition operator η is different, “nonstandard,” so that classical species theory does not apply, but our (extension of species) theory does. On the other hand, we shall see in Section 9 that this composition operator is pointwise associative and commutative (for the precise definition see (9.4) and (9.5)), and that this is equivalent to the fact that this case is also covered by Menni’s theory in [21]. As a consequence, this family of composition operators is closely related to the classical operation of “putting objects together.” (See Theorem 22 for the precise statement.) Our last example in this section, Example 3, presents an example of a composition operator that is neither pointwise associative nor pointwise commutative, in other words, a composition operator that is not covered by Menni’s theory in [21]. A particular aspect demonstrated by Examples 1 and 2 that we want to highlight is that composition operators need not be unique.

Example 1 (Bipartite graphs I). Let the 2-sort species F : Set^{2} → Set be defined by

F [Ω] = F [(Ω^{(1)}, Ω^{(2)})] := 2^{Ω^{(1)}×Ω^{(2)}}, Ω = (Ω^{(1)}, Ω^{(2)}) ∈ Ob(Set^{2}).

Thus, F [(Ω^{(1)}, Ω^{(2)})] can be considered as set of all bipartite graphs, where the set of “white” vertices is Ω^{(1)} and the set of “black” vertices is Ω^{(2)}. For (Ω_{1}, Ω_{2}) ∈ Ob(𝔇_{2}), b_{1} ∈ F [Ω_{1}] and b_{2} ∈ F [Ω_{2}], put

η_{(Ω_{1},Ω_{2})}((b_{1}, b_{2})) := b_{1} ⨿ b_{2}.

This means that η_{(Ω_{1},Ω_{2})} merely forms the disjoint union of the bipartite graphs b_{1} and b_{2}. Then it is not difficult to see that η is a natural transformation satisfying (D1). Moreover, F_{η}[Ω] consists of the connected bipartite graphs with bipartition Ω = (Ω^{(1)}, Ω^{(2)}).

For a weight, we choose Λ = ℤ[t] and

w_{Ω}(b) := t^{|b|}, b ∈ F [Ω].

Again, it is not difficult to see that w satisfies Axioms (W0)–(W2); that is, w is a Λ-weight on (F, η).

Theorem 1 then says that

GF_{F} (z_{1}, z_{2}) = exp ( GF_{F_{η}}(z_{1}, z_{2})),  (7.1)

where

GF_{F} (z_{1}, z_{2}) = ∑_{n_{1},n_{2}≥0} ∑_{b∈F [([n_{1}],[n_{2}])]} t^{|b|} \frac{z_{1}^{n_{1}}z_{2}^{n_{2}}}{n_{1}! n_{2}!}

and

GF_{F_{η}}(z_{1}, z_{2}) = ∑_{n_{1},n_{2}≥0} ∑_{b∈F_{η}[([n_{1}],[n_{2}])]} t^{|b|} \frac{z_{1}^{n_{1}}z_{2}^{n_{2}}}{n_{1}! n_{2}!}.

However, by straightforward counting, one sees that

GF_{F} (z_{1}, z_{2}) = ∑_{n_{1},n_{2}≥0}(1 + t)^{n_{1}n_{2}} \frac{z_{1}^{n_{1}}z_{2}^{n_{2}}}{n_{1}! n_{2}!}.

From (7.1), it then follows that the generating function for connected bipartite graphs is given by

GF_{F_{η}}(z_{1}, z_{2}) = log ( ∑_{n_{1},n_{2}≥0}(1 + t)^{n_{1}n_{2}} \frac{z_{1}^{n_{1}}z_{2}^{n_{2}}}{n_{1}! n_{2}!}) ,

while (2.11) implies that

G̃F_{F} (z_{1}, z_{2}) := ∑_{n_{1},n_{2}≥0} ∑_{b∈F [([n_{1}],[n_{2}])]} t^{|b|}y^{#(connected components of b)} \frac{z_{1}^{n_{1}}z_{2}^{n_{2}}}{n_{1}! n_{2}!}

= ( ∑_{n_{1},n_{2}≥0}(1 + t)^{n_{1}n_{2}} \frac{z_{1}^{n_{1}}z_{2}^{n_{2}}}{n_{1}! n_{2}!})^{y} .  (7.2)

This example can be considered as a 2-dimensional analogue of the example in [9, Sec. 3] (with the first of the two composition operators considered there). The knowledgeable reader will recognise (7.2) as the exponential generating function for the Tutte polynomials of complete bipartite graphs (cf. e.g. [24, Eq. (3.10)]).

Example 2 (Bipartite graphs II). Let F : Set^{2} → Set be as in Example 1. Here, for (Ω_{1}, Ω_{2}) ∈ Ob(𝔇_{2}), where Ω_{i} = (Ω_{i}^{(1)}, Ω_{i}^{(2)}), i = 1, 2, for b_{1} ∈ F [Ω_{1}] and b_{2} ∈ F [Ω_{2}], we put

η′_{(Ω_{1},Ω_{2})}((b_{1}, b_{2})) := b_{1} ⨿ b_{2} ⨿ (Ω_{1}^{(1)} × Ω_{2}^{(2)}) ⨿ (Ω_{1}^{(2)} × Ω_{2}^{(1)}) .

The graph η′_{(Ω_{1},Ω_{2})}((b_{1}, b_{2})) can be considered as a kind of bipartite completion of the disjoint union of b_{1} and b_{2}. Again, it is not difficult to see that η′ is a natural transformation satisfying (D1). Moreover, F_{η}′(Ω) consists of the complements of connected bipartite graphs with bipartition Ω = (Ω^{(1)}, Ω^{(2)}), where the complement b^{c} of a bipartite graph b ∈ F [Ω] is defined as b^{c} := (Ω^{(1)} × Ω^{(2)}) − b.

If we now were to choose the weight of Example 1, then Axiom (W2) would be violated. Instead, with Λ = ℤ[t], we set

w′_{Ω}(b) := t^{|Ω^{(1)}|·|Ω^{(2)}|−|b|}, b ∈ F [Ω] = F [(Ω^{(1)}, Ω^{(2)})].

Then it is not difficult to see that w′ does satisfy Axioms (W0)–(W2); that is, w′ is a Λ-weight on (F, η′).

Theorem 1 then says that

GF_{F} (z_{1}, z_{2}) = exp ( GF_{F_{_{η}′}}(z_{1}, z_{2})),  (7.3)

where

GF_{F} (z_{1}, z_{2}) = ∑_{n_{1},n_{2}≥0} ∑_{b∈F [([n_{1}],[n_{2}])]} t^{n_{1}n_{2}−|b|} \frac{z_{1}^{n_{1}}z_{2}^{n_{2}}}{n_{1}! n_{2}!}

and

GF_{F_{_{η}′}}(z_{1}, z_{2}) = ∑_{n_{1},n_{2}≥0} ∑_{b∈F_{_{η}′}([n_{1}],[n_{2}])} t^{n_{1}n_{2}−|b|} \frac{z_{1}^{n_{1}}z_{2}^{n_{2}}}{n_{1}! n_{2}!}.

Again, by straightforward counting, one sees that

GF_{F} (z_{1}, z_{2}) = ∑_{n_{1},n_{2}≥0}(1 + t)^{n_{1}n_{2}} \frac{z_{1}^{n_{1}}z_{2}^{n_{2}}}{n_{1}! n_{2}!},

and we obtain the formulae

GF_{F_{_{η}′}}(z_{1}, z_{2}) = log ( ∑_{n_{1},n_{2}≥0}(1 + t)^{n_{1}n_{2}} \frac{z_{1}^{n_{1}}z_{2}^{n_{2}}}{n_{1}! n_{2}!})

and

G̃F_{F} (z_{1}, z_{2}) := ∑_{n_{1},n_{2}≥0} ∑_{b∈F [([n_{1}],[n_{2}])]} t^{n_{1}n_{2}−|b|}y^{#(connected components of b^{c})} \frac{z_{1}^{n_{1}}z_{2}^{n_{2}}}{n_{1}! n_{2}!}

= ( ∑_{n_{1},n_{2}≥0}(1 + t)^{n_{1}n_{2}} \frac{z_{1}^{n_{1}}z_{2}^{n_{2}}}{n_{1}! n_{2}!})^{y} .  (7.4)

This example can be viewed as a 2-dimensional analogue of the example in [9, Sec. 3] (with the second of the two composition operators considered there).

The alert reader will have noticed that the η′-maps could have been alternatively defined by

η′_{(Ω_{1},Ω_{2})}((b_{1}, b_{2})) := (b_{1}^{c} ⨿ b_{2}^{c})^{c},  (7.5)

where the complements have to be taken in the appropriate complete bipartite graphs. This construction will be generalised in Section 9.

Example 3 (Binary functions). Let the (1-sort) species F : Set → Set be defined by

F [Ω] := {0, 1}^{Ω}, Ω ∈ Ob(Set).

For (Ω_{1}, Ω_{2}) ∈ Ob(𝔇_{1}), f_{1} ∈ F [Ω_{1}], and f_{2} ∈ F [Ω_{2}], put

(η_{(Ω_{1},Ω_{2})}((f_{1}, f_{2})))(ω) := \begin{cases}f_{1}(ω), & if ω ∈ Ω_{1}, \\ 1 − f_{2}(ω), & if ω ∈ Ω_{2}. \end{cases}

Then it is easy to see that η is a natural transformation satisfying (D1). Moreover,

F_{η}[Ω] = \begin{cases}\{0_{Ω}, 1_{Ω}\}, & if |Ω| = 1, \\ \{\}, & otherwise, \end{cases}

where 0_{Ω} and 1_{Ω} are the constant functions on Ω taking the value 0 and 1, respectively. We note that, in contrast to Examples 1 and 2, the η-maps of the present example are pointwise non-associative and non-commutative (cf. Section 9); to be precise, in general we have

η_{(Ω_{1}⨿Ω_{2},Ω_{3})}((η_{(Ω_{1},Ω_{2})}((f_{1}, f_{2})), f_{3})) ≠ η_{(Ω_{1},Ω_{2}⨿Ω_{3})}((f_{1}, η_{(Ω_{2},Ω_{3})}((f_{2}, f_{3}))))

and

η_{(Ω_{1},Ω_{2})}((f_{1}, f_{2})) ≠ η_{(Ω_{2},Ω_{1})}((f_{2}, f_{1})).

For the sake of completeness, we remark that, choosing the trivial weighting

w_{Ω}(f) := 1, f ∈ F [Ω],

Theorem 1 yields the trivial identity

GF_{F} (z) = ∑_{n≥0} 2^{n} \frac{z^{n}}{n!} = exp ( GF_{F_{η}}(z)) = exp(2z).

The construction of this example can also be generalised to produce many more (multisort) species with pointwise non-associative and non-commutative composition operator, see Theorem 23 in Section 9.

8. Illustrations, II: Magic squares

The purpose of this section is to illustrate the increased flexibility of our present multivariate setting. We show that a number of generating function identities for combinatorial matrices found scattered throughout the literature can be uniformly explained, and generalised, in the context of our theory.

By a combinatorial matrix on Ω = (Ω^{(1)}, Ω^{(2)}) ∈ Ob(Set^{2}) we shall mean any map

m : Ω^{(1)} × Ω^{(2)} → ℕ_{0}.

The pair of sets Ω is called the support of m. Let m_{1}, m_{2} be two combinatorial matrices with supports Ω_{1} = (Ω_{1}^{(1)}, Ω_{1}^{(2)}) and Ω_{2} = (Ω_{2}^{(1)}, Ω_{2}^{(2)}), respectively, and suppose that Ω_{1} ∩ Ω_{2} = ∅∅∅. Then we define their direct sum m = m_{1} ⊕ m_{2} to be the combinatorial matrix with support Ω := Ω_{1} ⨿ Ω_{2} given by

m(ω_{1}, ω_{2}) := \begin{cases}m_{1}(ω_{1}, ω_{2}), & (ω_{1}, ω_{2}) ∈ Ω_{1}^{(1)} × Ω_{1}^{(2)}, \\ m_{2}(ω_{1}, ω_{2}), & (ω_{1}, ω_{2}) ∈ Ω_{2}^{(1)} × Ω_{2}^{(2)}, \\ 0, & otherwise. \end{cases}

A combinatorial matrix m on Ω is termed s-magic,^{7} s a positive integer, if

∑_{ω_{2}∈Ω^{(2)}} m(ω_{1}, ω_{2}) = s, ω_{1} ∈ Ω^{(1)},

and

∑_{ω_{1}∈Ω^{(1)}} m(ω_{1}, ω_{2}) = s, ω_{2} ∈ Ω^{(2)}.

Computing the sum of entries, we find that an s-magic matrix is necessarily square, |Ω^{(1)}| = |Ω^{(2)}|. The enumeration of s-magic squares has a long history, going back to MacMahon [20, §404–419]. A good account of the enumerative theory of magic squares can be found in [27, Sec. 4.6], with many pointers to further literature. For more recent work, see for instance [3, 8].

7Strictly speaking, the correct term here would be “s-semi-magic,” since we do not require diagonals to sum up to s as well, see e.g. [3]. However, we prefer the term “s-magic” for the sake of brevity.

For s ∈ ℕ and Ω ∈ Ob(Set^{2}), denote by F_{s}(Ω) the set of all s-magic matrices on Ω, and by F̄_{s}(Ω) the set of those s-magic matrices on Ω which do not contain s as an entry. We thus have mappings

F_{s}, F̄_{s} : Ob(Set^{2}) → Ob(Set),

which we turn into functors F_{s}, F̄_{s} : Set^{2} → Set by assigning to a morphism

f = (f_{1}, f_{2}) : Ω → Ω̃

in Set^{2} the map (denoted F_{s}[f] respectively F̄_{s}[f]) sending a combinatorial matrix m in the respective domain to m ∘ (f_{1}^{−1} × f_{2}^{−1}). Moreover, given s and a finite set Ω, let F_{s}^{∗}(Ω) be the set of symmetric s-magic matrices on Ω = (Ω, Ω); that is, combinatorial matrices satisfying

m(ω_{1}, ω_{2}) = m(ω_{2}, ω_{1}), (ω_{1}, ω_{2}) ∈ Ω^{2};

and denote by F̄_{s}^{∗}(Ω) the subset of F_{s}^{∗}(Ω) consisting of those matrices with no entry equal to s. Just as above, the maps

F_{s}^{∗}, F̄_{s}^{∗} : Ob(Set) → Ob(Set)

become functors F_{s}^{∗}, F̄_{s}^{∗} : Set → Set by assigning to a morphism f : Ω → Ω̃ in Set the map sending a combinatorial matrix m in the respective domain to m ∘ (f^{−1} × f^{−1}).

Next, given s ∈ ℕ, a pair (Ω_{1}, Ω_{2}) ∈ Ob(𝔇_{2}), and a pair (Ω_{1}, Ω_{2}) ∈ Ob(𝔇_{1}), the direct sum construction provides us with injective maps

(η_{s})_{(Ω_{1},Ω_{2})} : F_{s}(Ω_{1}) × F_{s}(Ω_{2}) → F_{s}(Ω_{1} ⨿ Ω_{2}),
(η̄_{s})_{(Ω_{1},Ω_{2})} : F̄_{s}(Ω_{1}) × F̄_{s}(Ω_{2}) → F̄_{s}(Ω_{1} ⨿ Ω_{2}),
(η_{s}^{∗})_{(Ω_{1},Ω_{2})} : F_{s}^{∗}(Ω_{1}) × F_{s}^{∗}(Ω_{2}) → F_{s}^{∗}(Ω_{1} ⨿ Ω_{2}),
(η̄_{s}^{∗})_{(Ω_{1},Ω_{2})} : F̄_{s}^{∗}(Ω_{1}) × F̄_{s}^{∗}(Ω_{2}) → F̄_{s}^{∗}(Ω_{1} ⨿ Ω_{2}).

A certain amount of checking is required in order to convince oneself that these definitions fit into the framework of Theorems 1 and 4. The next lemma states the corresponding result. We leave its proof, which essentially amounts to a routine verification, to the reader.

Lemma 19. (i) For each s ∈ ℕ, the collection of maps

η_{s} = ((η_{s})_{(Ω_{1},Ω_{2})})_{(Ω_{1},Ω_{2})∈Ob(𝔇_{2})}

is a natural transformation from the functor F_{s} × F_{s} to the functor F_{s} ∘ ⨿. Analogous statements hold for the functors F̄_{s}, F_{s}^{∗}, F̄_{s}^{∗}, and the families of maps

η̄_{s} = ((η̄_{s})_{(Ω_{1},Ω_{2})})_{(Ω_{1},Ω_{2})∈Ob(𝔇_{2})},
η_{s}^{∗} = ((η_{s}^{∗})_{(Ω_{1},Ω_{2})})_{(Ω_{1},Ω_{2})∈Ob(𝔇_{1})},
η̄_{s}^{∗} = ((η̄_{s}^{∗})_{(Ω_{1},Ω_{2})})_{(Ω_{1},Ω_{2})∈Ob(𝔇_{1})}.

(ii) For each s, the pair (F_{s}, η_{s}) satisfies Axiom (D1), an analogous statement holding for each of the other pairs (F̄_{s}, η̄_{s}), (F_{s}^{∗}, η_{s}^{∗}), and (F̄_{s}^{∗}, η̄_{s}^{∗}).

It follows from Lemma 19 and Theorem 4, that Equations (2.10) and (2.11) hold for each of the pairs (F_{s}, η_{s}), (F̄_{s}, η̄_{s}), (F_{s}^{∗}, η_{s}^{∗}), and (F̄^{∗}, η̄_{s}^{∗}); in particular, we find that

G̃F_{F_{s}}(z_{1}, z_{2}, y) = exp (y GF_{(F_{s})_{η_{s}}}(z_{1}, z_{2})),  (8.1)
G̃FF̄_{s}(z_{1}, z_{2}, y) = exp (y GF_{(F̄_{s})_{η̄_{s}}}(z_{1}, z_{2})),  (8.2)
G̃F_{F_{s}^{∗}}(z, y) = exp (y GF_{(F_{s}^{∗})_{η}∗_{s}}(z)),  (8.3)
G̃FF̄_{s}^{∗}(z, y) = exp (y GF_{(F̄_{s}^{∗})η̄∗_{s}}(z)).  (8.4)

Note that in these identities the variable y keeps track of the number of indecomposable matrices into which the matrices which are counted by the respective generating functions on the left-hand sides can be decomposed. Clearly, the generating functions occurring in (8.1) and (8.2) can be viewed as formal power series in z_{1}z_{2} and y; that is, z_{1}z_{2} could be replaced by a single variable. However, we prefer to keep z_{1} and z_{2} separate, since this is more in line with our general theory.

We note certain dependencies among the series G̃F_{F_{s}}, G̃FF̄_{s}, G̃F_{F_{s}^{∗}}, G̃FF̄_{s}^{∗}; for instance, we observe that an indecomposable s-magic matrix on ([n_{1}], [n_{2}]) cannot contain an entry equal to s, unless n_{1} = n_{2} = 1. It follows that

|(F_{s})_{η_{s}}([n_{1}], [n_{2}])| = \begin{cases}1 + |(F̄_{s})_{η̄_{s}}([1], [1])|, & n_{1} = n_{2} = 1, \\ |(F̄_{s})_{η̄_{s}}([n_{1}], [n_{2}])|, & otherwise, \end{cases}

and hence, by Equations (8.1) and (8.2),

G̃FF̄_{s}(z_{1}, z_{2}, y) = e^{−z_{1}z_{2}y} G̃F_{F_{s}}(z_{1}, z_{2}, y).  (8.5)

Similarly, we have

G̃FF̄_{s}^{∗}(z, y) = e^{−y(z+z^{2}/2)}G̃F_{F_{s}^{∗}}(z, y).  (8.6)

Indeed, for n = 1, 2, there exist indecomposable symmetric s-magic matrices on ([n], [n]) containing an entry s:

(s) and (\begin{matrix}0 & s \\ s & 0 \end{matrix}) .

Now let m be a symmetric s-magic matrix on ([n], [n]) with n ≥ 3, and suppose that m contains an entry equal to s in position (i, j). Then, if i = j, we have m = (s) ⊕ m′, where m′ has support ([n] − {i}, [n] − {i}). If, on the other hand, i ≠ j, then, by symmetry, m also contains s in position (j, i), and we find that m splits as

m = (\begin{matrix}0 & s \\ s & 0 \end{matrix}) ⊕ m′,

where m′ has support ([n] − {i, j}, [n] − {i, j}), and is non-empty since n ≥ 3. Thus, in both cases, m is in fact decomposable. Hence,

|(F_{s}^{∗})_{η}_{s}^{∗}([n])| = \begin{cases}1 + |(F̄_{s}^{∗})η̄_{s}^{∗}([n])|, & n = 1, 2, \\ |(F̄_{s}^{∗})η̄_{s}^{∗}([n])|, & otherwise, \end{cases}

and (8.6) follows from Equations (8.3) and (8.4).

The enumeration can be done exactly if s = 2. For, according to Birkhoff’s Theorem (cf. [5] or [1, Corollary 8.40]), a 2-magic matrix m is the sum of two permutation matrices, say p_{1} and p_{2}. If m is indecomposable, then the pair {p_{1}, p_{2}} is uniquely determined. Premultiplying by p_{1}^{−1}, we obtain a situation where p_{1} is the identity; indecomposability forces p_{2} to be the permutation matrix corresponding to a cyclic permutation. So there are n!(n − 1)! choices for (p_{1}, p_{2}), and half this many choices for m (assuming, as we may, that n > 1). Note that this formula gives half the correct number for n = 1. So we have

|(F_{2})_{η_{2}}([n_{1}], [n_{2}])| = \begin{cases}1, & n_{1} = n_{2} = n = 1, \\ \frac{n!(n−1)!}{2}, & n_{1} = n_{2} = n > 1, \\ 0, & n_{1} ≠ n_{2}, \end{cases}

that is,

GF_{(F_{2})_{η_{2}}}(z_{1}, z_{2}) = \frac{1}{2}z_{1}z_{2} − \frac{1}{2} log(1 − z_{1}z_{2}),

and therefore

G̃F_{F_{2}}(z_{1}, z_{2}, y) = (1 − z_{1}z_{2})^{−y/2} e^{z_{1}z_{2}y/2}  (8.7)

by Equation (8.1). Also,

G̃FF̄_{2}(z_{1}, z_{2}, y) = (1 − z_{1}z_{2})^{−y/2} e^{−z_{1}z_{2}y/2},  (8.8)

making use of Equation (8.5) and the last result. Special cases of Identities (8.7) and (8.8) appear in [2, Sections 8.1 and 8.3] (see also [26, Eqs. (23) and (24) in Example 6.11]). For s > 2, enumeration is more difficult; see Stanley’s paper [25] and Comtet [7, pp. 124–125] for comments in this direction; also Goulden and Jackson [13, Sections 3.4 and 3.5] for some variations on this counting problem.^{8}

For symmetric matrices, it is again possible to count the indecomposables with s = 2. For n > 2, such a matrix can be represented as a graph in which every vertex has degree 2; loops are permitted, but contribute only one to the degree of a vertex. Indecomposability of the matrix is reflected in connectedness of the graph. So the graphs we must consider are paths (with a loop at each end) and cycles; and, for n > 2, their number is \frac{1}{2}(n! + (n − 1)!). Including the cases where n ≤ 2, we obtain

GF_{(F_{2}^{∗})_{η}∗_{2}}(z) = \frac{z^{2}}{4} + \frac{z}{2(1 − z)} − \frac{1}{2} log(1 − z),

and, hence

G̃F_{F_{2}^{∗}}(z, y) = (1 − z)^{−y/2} exp (\frac{yz^{2}}{4} + \frac{yz}{2(1 − z)}),  (8.9)

as well as

G̃FF̄_{2}^{∗}(z, y) = (1 − z)^{−y/2} exp ( − \frac{yz^{2}}{4} − yz + \frac{yz}{2(1 − z)}).  (8.10)

Identity (8.9) generalises [14, Eq. (6.3)], whereas (8.10) generalises [14, Eq. (6.4)].

8Note however, that the formula given in [7] for s = 3 is erroneous.

9. Simple commutative monoids in species

In this final section, we address the natural question: ‘Can one characterise all possible composition operators in r-sort species?’ In particular: how far can the composition operator η of our theory differ from the standard operation for the species of sets of combinatorial structures given by forming the disjoint union, of which Example 1 in Section 7 is a prototypical example? We do not have an answer in general. However, while addressing this question, we also clarify the relation of our work to the theory developed by Menni in [21].

Already Joyal pointed out in [16, Sec. 7.1] that (r-sort) species are endowed with the structure of a symmetric monoidal category. The main objects in Menni’s theory [21] are simple commutative monoids in an arbitrary symmetric monoidal category. He defines the notion of a decomposition as a simple commutative monoid that satisfies a certain pullback condition (see [21, Def. 2.1]), and, in the case where the symmetric monoidal category that we start with is the category of (r-sort) species, he shows that a decomposition is equivalent with a composition operator as defined in Section 2. He defines an exponential principle in this general setting, and he proves this principle to hold for a large family of symmetric monoidal categories that includes r-sort species (see [21, Prop. 1.4, Ex. 3.2, and Ex. 3.5 with I = 1 + 1 + ⋯ + 1, the summand 1 appearing r times in the sum]). He then moves on to characterise decompositions in symmetric monoidal categories (see [21, Sec. 2.6]).

We shall next discuss the notions mentioned in the previous two paragraphs in some more detail, in order to provide a better feeling of what Menni’s theory is about. Subsequently, we shall make Menni’s characterisation of decompositions explicit for the case of r-sort species, that is, of composition operators in the sense of Section 2 that define the structure of a simple commutative monoid in r-sort species. We shall see that the latter is equivalent to the condition of the composition operator being “pointwise associative” and “pointwise commutative” (see (9.4) and (9.5)). For the sake of being self-contained, and for including the case of weighted species as well (weights not being addressed in [21], which however could be built in without too much effort), we provide an independent proof. We close this section by exhibiting a large family of examples of composition operators (see Theorem 23), generalising Example 3, that are not pointwise associative or commutative and, thus, do not define the structure of a commutative monoid. These examples are therefore not included in Menni’s theory [21], which shows that our axiomatic set-up is wider than Menni’s theory in the special case of r-sort species.

Let Sp_{r} denote the category of r-sort species. Given two species F and G in Ob(Sp_{r}) and Ω ∈ Ob(Set^{r}), we define their product ∗ (a special case of the more general concept of Day convolution; cf. [15] and [22, Sec. 3.1]) by

(F ∗ G)[Ω] := ∐_{Ω_{1}⨿Ω_{2}=Ω} F [Ω_{1}] × G[Ω_{2}],

with the obvious morphisms. In order to discuss monoids in species, we need to introduce the “unit” species 1 by

1[Ω] := \begin{cases}\{1\} & if Ω = ∅, \\ ∅ & if Ω ≠ ∅. \end{cases}

Here, 1 denotes a “canonical” element, and the morphisms are the obvious ones. Then the triple (Sp_{r}, ∗, 1) forms a symmetric monoidal category (see [16, Sec. 7.1]). We refer the reader to [17] (see also [19]) for the precise definition of a symmetric monoidal category. For our purposes, it suffices to say that, in the case of r-sort species, this involves the natural transformation(s)

α = α_{F,G,H} : F ∗ (G ∗ H) → (F ∗ G) ∗ H

given by

α : (x, (y, z)) → ((x, y), z), for x ∈ F [Ω_{1}], y ∈ G[Ω_{2}], z ∈ H[Ω_{3}],

where F, G, H ∈ Ob(Sp_{r}), and where Ω_{1}, Ω_{2}, Ω_{3} ∈ Ob(Set^{r}) are pairwise disjoint, the natural transformation(s)

β = β_{F,G} : F ∗ G → G ∗ F

given by

β : (x, y) → (y, x), for x ∈ F [Ω_{1}], y ∈ G[Ω_{2}],

the natural transformation(s)

λ = λ_{F} : 1 ∗ F → F

given by

λ : (1, x) → x, for x ∈ F [Ω_{1}],

and the natural transformation(s)

ρ = ρ_{F} : F ∗ 1 → F

given by

ρ = ρ_{F} : (x, 1) → x, for x ∈ F [Ω_{1}],

so that — roughly speaking — all association and commutation laws that one may think of are satisfied.

A monoid in the symmetric monoidal category Sp_{r} is by definition a triple (F, ∗, 1), where F ∈ Ob(Sp_{r}), such that there are natural transformations μ : F ∗ F → F and ν : 1 → F such that the diagrams

[figure: F ∗ (F ∗ F); α; (F ∗ F) ∗ F; μ ∗ id; F ∗ F; F ∗ F; id ∗μ; μ; F; μ]  (9.1)

and

[figure: 1 ∗ F; ν ∗ id; F ∗ F; id ∗ν; F ∗ 1; F; μ; ρ; λ]  (9.2)

commute. A monoid (F, ∗, 1) is commutative if the diagram

[figure: F ∗ F; β; F ∗ F; F; μ; μ]  (9.3)

commutes. It is called simple if the natural transformation ν : 1 → F is unique.

As Menni explains in [21, Example 3.2], a natural transformation η from F × F to F ∘ ⨿ as in Section 2 induces a natural transformation μ : F ∗ F → F by

F [Ω_{1}] × F [Ω_{2}] ⟶^{η_{(Ω_{1},Ω_{2})}} F [Ω_{1} ⨿ Ω_{2}] ⟶^{id} F [Ω]

(where, as usual, Ω = Ω_{1} ⨿ Ω_{2} is a partition of Ω) and by the universality property of coproducts. Conversely, a natural transformation μ : F ∗ F → F induces a natural transformation η from F × F to F ∘ ⨿ by

F [Ω_{1}] × F [Ω_{2}] ⟶ (F ∗ F)[Ω_{1} ⨿ Ω_{2}] ⟶^{μ} F [Ω_{1} ⨿ Ω_{2}]

In this precise sense, natural transformations μ : F ∗F → F and natural transformations η : F ×F → F ∘⨿ are equivalent notions. Under this equivalence, commutativity of the diagrams (9.1) and (9.3) is equivalent to the composition operator η being pointwise associative and pointwise commutative, respectively. Here, we say that η is pointwise associative if, for all pairwise disjoint Ω_{1}, Ω_{2}, Ω_{3} ∈ Ob(Set^{r}), and all elements x_{1} ∈ F [Ω_{1}], x_{2} ∈ F [Ω_{2}], x_{3} ∈ F [Ω_{3}], we have

η_{(Ω_{1}⨿Ω_{2},Ω_{3})}((η_{(Ω_{1},Ω_{2})}((x_{1}, x_{2})), x_{3})) = η_{(Ω_{1},Ω_{2}⨿Ω_{3})}((x_{1}, η_{(Ω_{2},Ω_{3})}((x_{2}, x_{3})))), (9.4)

and we say that η is pointwise commutative if, for all (Ω_{1}, Ω_{2}) ∈ Ob(𝔇_{r}), and all elements x_{1} ∈ F [Ω_{1}], x_{2} ∈ F [Ω_{2}], we have

η_{(Ω_{1},Ω_{2})}((x_{1}, x_{2})) = η_{(Ω_{2},Ω_{1})}((x_{2}, x_{1})).  (9.5)

The η-maps in Examples 1 and 2 are instances of pointwise associative and commutative composition operators, while the composition operator in Example 3 is neither pointwise associative nor pointwise commutative. The notion of pointwise commutativity and associativity should not be confused with the commutativity and the 3-associativity proved in Lemmas 6 and 7, respectively, which are (in general) strictly weaker assertions. In particular, if (F, ∗, 1) is a monoid, then all “permutabilities” in Lemmas 6, 7, 9, 11, 15 come for free since they hold already on a functorial level, but, as Theorem 23 shows, the converse is not true; that is, these “permutabilities” do not guarantee that (F, ∗, 1) forms a monoid.

Finally, it is easy to see that there is a unique natural transformation ν : 1 → F if and only if |F [∅]| = 1, a condition automatically satisfied by a composition operator (see Lemma 5), and it is also easy to see that the diagram (9.2) always commutes.

To summarise the above discussion: the notion of (F, ∗, 1) being a simple commutative monoid is equivalent to the corresponding composition operator η being pointwise associative and commutative.

Now that we have discussed the precise relationship between the theory in [21] (specialised to r-sort species) and our setting laid down in Section 2, we want to make Menni’s characterisation of simple commutative monoids in the case of r-sort species, that is — in our language — of pointwise and associative composition operators, explicit. In order to do so, we need two preparatory results. Recall that a species isomorphism between two r-sort species F_{1} and F_{2} is a collection of maps φ = (φ_{Ω})_{Ω∈Ob(Set^{r})}, where, for each Ω ∈ Ob(Set^{r}),

φ_{Ω} : F_{1}[Ω] → F_{2}[Ω]

is a bijection, with the property that, for every morphism f : Ω → Ω̃ in the category Set^{r}, the diagram

\begin{matrix}F_{1}[Ω] & ⟶^{F_{1}[f]} & F_{1}[Ω̃] \\ ^{φ_{Ω}}↓ & & ↓^{φΩ̃} \\ F_{2}[Ω] & ⟶_{F_{2}[f]} & F_{2}[Ω̃] \end{matrix}  (9.6)

commutes. If F_{1} carries a weak Λ_{1}-weight w_{1} and F_{2} carries a weak Λ_{2}-weight w_{2}, where, by “weak,” we mean that w_{1} and w_{2} satisfy Axioms (W0) and (W1), but not necessarily (W2) (cf. Section 2), then an isomorphism φ : F_{1} → F_{2} is called weightpreserving, if there exists a ring homomorphism λ : Λ_{1} → Λ_{2} such that the diagram

\begin{matrix}F_{1}[Ω] & ⟶^{(w_{1})_{Ω}} & Λ_{1} \\ ^{φ_{Ω}}↓ & & ↓^{λ} \\ F_{2}[Ω] & ⟶_{(w_{2})_{Ω}} & Λ_{2} \end{matrix}  (9.7)

commutes.

The lemma below tells us that, if F_{1} and F_{2} are two isomorphic r-sort species, where F_{1} is decomposable with composition operator η_{1}, then η_{1} can be lifted to a composition operator for F_{2}, demonstrating that F_{2} is decomposable as well.

Lemma 20. Let F_{1} and F_{2} be two isomorphic r-sort species, where F_{1} is decomposable with composition operator η_{1}. Furthermore, let φ be an isomorphism between F_{1} and F_{2}. Then F_{2} is decomposable, and the family of maps η_{2} = ((η_{2})_{(Ω_{1},Ω_{2})})_{(Ω_{1},Ω_{2})∈Ob(𝔇_{r})} defined by

(η_{2})_{(Ω_{1},Ω_{2})}(x_{1}, x_{2}) := φ_{Ω_{1}⨿Ω_{2}}((η_{1})_{(Ω_{1},Ω_{2})}((φ_{Ω_{1}}^{−1}(x_{1}), φ_{Ω_{2}}^{−1}(x_{2})))),

x_{1} ∈ F_{2}[Ω_{1}], x_{2} ∈ F_{2}[Ω_{2}],

is a composition operator for F_{2}.

Proof. We have to show that η_{2} is a natural transformation from F_{2} × F_{2} to F_{2} ∘ ⨿, and that the pair (F_{2}, η_{2}) satisfies Axiom (D1). The former follows immediately from the corresponding property for (F_{1}, η_{1}) and the naturality condition (9.6). In order to verify (D1), we start with the left-hand side of (2.3) for the pair (F_{2}, η_{2}), suppressing the indices of η_{1}, η_{2}, φ for better readability:

η_{2}(F_{2}[Ω_{1}] × F_{2}[Ω_{2}]) ∩ η_{2}(F_{2}[Ω̃_{1}] × F_{2}[Ω̃_{2}])
= φ(η_{1}(φ^{−1}(F_{2}[Ω_{1}]) × φ^{−1}(F_{2}[Ω_{2}]))) ∩ φ(η_{1}(φ^{−1}(F_{2}[Ω̃_{1}]) × φ^{−1}(F_{2}[Ω̃_{2}])))
= φ(η_{1}(F_{1}[Ω_{1}] × F_{1}[Ω_{2}])) ∩ φ(η_{1}(F_{1}[Ω̃_{1}] × F_{1}[Ω̃_{2}]))
= φ(η_{1}(F_{1}[Ω_{1}] × F_{1}[Ω_{2}]) ∩ η_{1}(F_{1}[Ω̃_{1}] × F_{1}[Ω̃_{2}])).

Here we have used the injectivity of φ to obtain the last line. Now we substitute the right-hand side of (2.3) for the pair (F_{1}, η_{1}), to obtain

η_{2}(F_{2}[Ω_{1}] × F_{2}[Ω_{2}]) ∩ η_{2}(F_{2}[Ω̃_{1}] × F_{2}[Ω̃_{2}])

= φ(η_{1}(η_{1}(F_{1}[Ω_{11}] × F_{1}[Ω_{12}]) × η_{1}(F_{1}[Ω_{21}] × F_{1}[Ω_{22}]))),

where Ω_{ij} := Ω_{i} ∩ Ω̃_{j} for i, j ∈ {1, 2}. Using F_{1}[Ω_{ij}] = φ^{−1}(F_{2}[Ω_{ij}]) at each possible place, and inserting id = φ^{−1} ∘ φ at two places, we arrive at

η_{2}(F_{2}[Ω_{1}]×F_{2}[Ω_{2}]) ∩ η_{2}(F_{2}[Ω̃_{1}] × F_{2}[Ω̃_{2}])
= φ(η_{1}(φ^{−1}(φ(η_{1}(φ^{−1}(F_{2}[Ω_{11}]) × φ^{−1}(F_{2}[Ω_{12}]))))
× φ^{−1}(φ(η_{1}(φ^{−1}(F_{2}[Ω_{21}]) × φ^{−1}(F_{2}[Ω_{22}]))))))
= η_{2}(η_{2}(F_{2}[Ω_{11}] × F_{2}[Ω_{12}]) × η_{2}(F_{2}[Ω_{21}] × F_{2}[Ω_{22}])),

which is exactly (2.3) for the pair (F_{2}, η_{2}). □

The second preparatory result, Proposition 21 below, states that, given a decomposable r-sort species F with pointwise associative and commutative composition operator η, F is isomorphic to E(F_{η}), where E(F_{η}) denotes the species of sets of F_{η}-structures (cf. [6, p. 8] for the definition of the species of sets, E, and [6, p. 41] for the definition of composition of species). In rigorous terms, for Ω ∈ Ob(Set^{r}), the set E(F_{η})[Ω] can be defined by

E(F_{η})[Ω] := {{(x_{1}, Ω_{1}), …, (x_{k}, Ω_{k})} : x_{i} ∈ F_{η}[Ω_{i}], i = 1, …, k,

for some k ∈ ℕ_{0} and Ω_{1} ⨿ ⋯ ⨿ Ω_{k} = Ω, all Ω_{i}’s being non-empty},

with the obvious notion of induced morphisms. If F carries a weak Λ-weight w, then w can be lifted to a weak Λ-weight of E(F_{η}) by setting

w_{Ω}({(x_{1}, Ω_{1}), …, (x_{k}, Ω_{k})}) := w_{Ω_{1}}(x_{1}) ⋯ w_{Ω_{k}}(x_{k}).

Proposition 21. Let F be a decomposable weighted r-sort species with composition operator η, where η is pointwise associative and commutative. Then there exists a weight-preserving isomorphism between F and E(F_{η}).

Proof. The starting point is the combination of Lemmas 12 and 13. It says that, for each non-empty Ω ∈ Ob(Set^{r}) and every choice of base point (ω, ρ) ∈ Ω, we have

F [Ω] = _{∐_{Ω_{1}∈Ob(Set^{r})} (ω,ρ)∈Ω_{1}⊆Ω}η_{(Ω_{1},Ω−Ω_{1})}(F_{η}[Ω_{1}] × F [Ω − Ω_{1}]).  (9.8)

We are now going to construct bijective maps ψ_{Ω} : F [Ω] → E(F_{η})[Ω] by induction on ∥Ω∥, where ∥ . ∥ has been defined in (2.6). For Ω = ∅∅∅, we have |F [Ω]| = |E(F_{η})[Ω]| = 1 by Lemma 5 respectively the definition of E(F_{η}), whence the construction of ψ_{∅ ∅ ∅} is trivial. Henceforth, we shall suppose that ∥Ω∥ ≥ 1, and we assume that we have constructed maps ψΩ̃ for all Ω̃ ∈ Ob(Set^{r}) with ∥Ω̃∥ < N.

Now let ∥Ω∥ = N. Choose a base point (ω, ρ) ∈ Ω, and let x ∈ F [Ω]. By (9.8), there is a unique Ω_{1} such that x ∈ η_{(Ω_{1},Ω−Ω_{1})}(F_{η}[Ω_{1}] × F [Ω − Ω_{1}]) and (ω, ρ) ∈ Ω_{1}. Let (y_{1}, x_{1}) be the uniquely determined pair with y_{1} ∈ F_{η}[Ω_{1}] and x_{1} ∈ F [Ω − Ω_{1}], such that

(y_{1}, x_{1}) := η_{(Ω_{1},Ω−Ω_{1})}^{−1}(x).  (9.9)

By the inductive hypothesis, there exist uniquely determined elements y_{2}, …, y_{k}, for some k ∈ ℕ and y_{i} ∈ F_{η}[Ω_{i}], i = 2, …, k, with Ω_{2} ⨿ ⋯ ⨿ Ω_{k} = Ω − Ω_{1}, such that

ψ_{Ω−Ω_{1}}(x_{1}) = {(y_{2}, Ω_{2}), …, (y_{k}, Ω_{k})}.  (9.10)

Define

ψ_{Ω}(x) := {(y_{1}, Ω_{1}), (y_{2}, Ω_{2}), …, (y_{k}, Ω_{k})}.

We claim that this yields a well-defined bijection ψ_{Ω} : F [Ω] → E(F_{η})[Ω]. What needs to be checked here first of all is that different choices of base points would always lead to the same result. So, let us suppose, that, by choosing a different base point, we would have obtained

ψ̄_{Ω}(x) := {(ȳ_{1}, Ω̄_{1}), (ȳ_{2}, Ω̄_{2}), …, (ȳ_{l}, Ω̄_{l})},

for some l, instead. Since we must have

Ω = Ω_{1} ⨿ Ω_{2} ⨿ ⋯ Ω_{k} = Ω̄_{1} ⨿ Ω̄_{2} ⨿ ⋯ Ω̄_{l},

there is a j such that (w, ρ) ∈ Ω̄_{j}. By our inductive construction via (9.9) and (9.10), we have

x ∈ η(F_{η}[Ω̄_{1}] × η(F_{η}[Ω̄_{2}] × ⋯ × (F_{η}[Ω̄_{l−1}] × F_{η}[Ω̄_{l}]) ⋯)).

By Lemma 15 (m-permutability for (F_{η}, η)), this is equivalent to saying that

x ∈ η(F_{η}[Ω̄_{j}] × η(F_{η}[Ω̄_{σ(2)}] × ⋯ × (F_{η}[Ω̄_{σ(l−1)}] × F_{η}[Ω̄_{σ(l)}]) ⋯)),  (9.11)

where σ(2), …, σ(l − 1), σ(l) is some permutation of {1, …, j − 1, j + 1, …, l}. If Ω̄_{j} ≠ Ω_{1}, then (9.9) and (9.11) would contradict the disjointness in (9.8). Hence, we must have Ω̄_{j} = Ω_{1}, and, by our assumption that η be pointwise associative and commutative, we even must have ȳ_{j} = y_{1}. The inductive hypothesis applied to Ω − Ω_{1} then guarantees that, moreover,

{(y_{2}, Ω_{1}), …, (y_{k}, Ω_{k})} = {(ȳ_{1}, Ω_{1}), …, (ȳ_{j−1}, Ω̄_{j−1}), (ȳ_{j+1}, Ω̄_{j+1}), …, (ȳ_{l}, Ω_{l})}.

This proves that ψ_{Ω} is indeed well-defined.

The facts that each map ψ_{Ω} is a bijection, and that the family ψ = (ψ_{Ω})_{Ω∈Ob(Set^{r})} is an isomorphism between F and E(F_{η}), are not hard to verify. The fact that ψ is weight-preserving is obvious from the definition of ψ and Axiom (W2) for (F, η, w). This completes the proof of the proposition. □

If we combine Lemma 20 and Proposition 21, then we can say exactly how a decomposable r-sort species F with pointwise associative and commutative composition operator η arises from the composition of the species of sets with the species of F_{η}-structures (“components”). We should point out here that, clearly, a natural composition operator for E(F_{η}) is given by

(y_{1}, y_{2}) ↦ y_{1} ⨿ y_{2}, y_{1} ∈ E(F_{η})[Ω_{1}], y_{2} ∈ E(F_{η})[Ω_{2}], Ω_{1} ⨿ Ω_{2} = Ω.  (9.12)

Theorem 22. Let F be a decomposable r-sort species with composition operator η, where η is pointwise associative and commutative. Then, for all (Ω_{1}, Ω_{2}) ∈ Ob(𝔇_{r}), the composition operator η can be expressed as follows:

η_{(Ω_{1},Ω_{2})}(x_{1}, x_{2}) = ψ_{Ω_{1}⨿Ω_{2}}^{−1}(ψ_{Ω_{1}}(x_{1}) ⨿ ψ_{Ω_{2}}(x_{2})), x_{1} ∈ F [Ω_{1}], x_{2} ∈ F [Ω_{2}], (9.13)

where ψ is the isomorphism between F and E(F_{η}) constructed in the proof of Proposition 21.

Proof. One combines Lemma 20 with Proposition 21, where the role of the isomorphism φ in Lemma 20 is played by the family of maps ψ^{−1} constructed in the proof of Proposition 21. □

In summary, all decomposable r-sort species with pointwise associative and commutative composition operator can be constructed from E(G), for some species G, equipped with the natural composition operator as given in (9.12) (in the case where G = F_{η}), by applying a lift in the sense of Lemma 20 via a species isomorphism. In the more general setting of [21], the identification of the “indecomposable” objects G (denoted by L(F, ζ) there) is explained in [21, Sec. 2.6], while the isomorphism between F and “composite objects built from G” (denoted by EG = EL(F, ζ) there) is constructed in [21, Lemma 2.8].

In order to see how Example 2 in Section 7 fits into the setting of Theorem 22, recall that the isomorphism between F and E(F_{η}) in that example can be defined by mapping the bipartite graph b ∈ F [Ω] to its complement b^{c}, identifying the connected components (in the classical sense of graph theory) of b^{c}, and forming the set of complements of these connected components (restricted to the set of vertices which a component involves). If this isomorphism is inserted in (9.13), the result is (7.5).

We conclude our paper by pointing out that the construction in Theorem 22 can be “twisted” to produce pointwise non-associative and non-commutative composition operators as well, thereby obtaining a large family of examples that still fit under our theory but not under Menni’s.

Theorem 23. Let G be a weighted r-sort species, and let g : G → G be a weightpreserving isomorphism. We extend g to E(G) by setting

g_{Ω⨿···⨿Ω_{k}}({(y_{1}, Ω_{1}), …, (y_{k}, Ω_{k})}) = {(g_{Ω_{1}}(y_{1}), Ω_{1}), …, (g_{Ω_{k}}(y_{k}), Ω_{k})}.

Then the family η = (η_{(Ω_{1},Ω_{2})})_{(Ω_{1},Ω_{2})∈Ob(𝔇_{r})} of maps defined by

η_{(Ω_{1},Ω_{2})}(x_{1}, x_{2}) = x_{1} ⨿ g_{Ω_{2}}(x_{2}), x_{1} ∈ E(G)[Ω_{1}], x_{2} ∈ E(G)[Ω_{2}],

where (Ω_{1}, Ω_{2}) ∈ Ob(𝔇_{r}), is a composition operator for the weighted species E(G).

It is obvious from the definition that the composition operator η of Theorem 23 will, in general, be neither pointwise associative nor pointwise commutative and, thus, not fit into the theory in [21]. Example 3 in Section 7 provides a typical example of the above construction, with G given by

G[Ω] = \begin{cases}\{0_{Ω}, 1_{Ω}\}, & if |Ω| = 1, \\ \{\}, & otherwise, \end{cases}

where 0_{Ω} and 1_{Ω} are the constant functions on Ω taking the value 0 and 1, respectively, and where the isomorphism g is given by g_{Ω}(0_{Ω}) = 1_{Ω} and g_{Ω}(1_{Ω}) = 0_{Ω} for |Ω| = 1. However, we expect that there are many composition operators η not obtainable in this way.

Acknowledgement

We thank Matías Menni for explaining his work in [21] to us, and for his patience in discussing the relationship between his work and the work of the present paper, leading to a significantly improved presentation of our results, by putting them in perspective.

References

[1] M. Aigner, Combinatorial Theory, Springer–Verlag, Berlin, 1979.

[2] H. Anand, V. C. Dumir, and H. Gupta, A combinatorial distribution problem, Duke Math. J. 33 (1966), 757–769.

[3] M. Beck, M. Cohen, J. Cuomo and P. Gribelyuk, The number of “magic” squares, cubes, and hypercubes, Amer. Math. Monthly 110 (2003), 707–717.

[4] E. Bender and J. Goldman, Enumerative uses of generating functions, Indiana Univ. Math. J 20 (1971), 753–764.

[5] G. Birkhoff, Tres observaciones sobre el algebra lineal, Univ. Nac. Tucumán Rev. Ser. A 5 (1946), 147–150.

[6] F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge University Press, Cambridge, 1998.

[7] L. Comtet, Advanced Combinatorics, Reidel, Dordrecht and Boston, 1974.

[8] J. A. De Loera, F. Liu and R. Yoshida, A generating function for all semi-magic squares and the volume of the Birkhoff polytope, J. Algebraic Combin. 30 (2009), 113–139.

[9] A. Dress and T. W. Müller, Decomposable functors and the exponential principle, Adv. in Math. 129 (1997), 188–221.

[10] C. Ehresmann, Catégories et structures, Dunod, Paris, 1965.

[11] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.

[12] D. Foata, La série génératrice exponentielle dans les problèmes d’énumération, Séminaire de mathématiques supérieures — été 1971, no. 54, Montréal, Les Presses de l’Université de Montréal, 1974.

[13] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley & Sons, New York, 1983.

[14] H. Gupta, Enumeration of symmetric matrices, Duke Math. J. 35 (1968), 653–659.

[15] G. B. Im and G. M. Kelly, A universal property of the convolution monoidal structure, J. Pure Appl. Algebra 43 (1986), 75–88.

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

[17] G. M. Kelly, Basic Concepts of Enriched Category Theory, London Mathematical Society Lecture Note Series, vol. 64, Cambridge University Press, Cambridge, New York, 1982.

[18] G. Labelle and P. Leroux, An extension of the exponential formula in enumerative combinatorics, Electron. J. Comb. 3(2) (1996), Article R12, 14 pp.

[19] S. MacLane, Categories for the Working Mathematician, Graduate Texts in Mathematics, vol. 5, Springer–Verlag, New York, Berlin, 1971.

[20] P. A. MacMahon, Combinatory Analysis, vol. 2, Cambridge University Press, 1916; reprinted by Chelsea, New York, 1960.

[21] M. Menni, Symmetric monoidal completions and the exponential principle among labeled combinatorial structures, Theory Appl. Categories 11 (2003), 397–419.

[22] M. Menni, Combinatorial functional and differential equations applied to differential posets, Discrete Math. 308 (2008), 1864–1888.

[23] M. Menni, Algebraic categories whose projections are explicitly free, Theory Appl. Categories 22 (2009), 509–541.

[24] A. D. Scott and A. D. Sokal, Some variants of the exponential formula, with application to the multivariate Tutte polynomial (alias Potts model), Séminaire Lotharingien Combin. 61A (2009), Article B61Ae, 33 pp.

[25] R. P. Stanley, Linear homogeneous diophantine equations and magic labelings of graphs, Duke Math. J. 40 (1973), 607–632.

[26] R. P. Stanley, Generating functions, in: MAA Studies in Mathematics, vol. 17 (G.-C. Rota, ed.), Math. Assoc. Am., Washington, 1978, 100–141.

[27] R. P. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986; reprinted by Cambridge University Press, Cambridge, 1998.

[28] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

[29] H. S. Wilf, generatingfunctionology, 2nd edition, Academic Press, San Diego, 1994.

School of Mathematical Sciences, Queen Mary & Westfield College, University of London, Mile End Road, London E1 4NS, United Kingdom.

WWW: http://www.maths.qmw.ac.uk/~pjc/, http://www.maths.qmw.ac.uk/~twm/.

Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna,

Austria. WWW: http://www.mat.univie.ac.at/~kratt.