\documentclass[12pt,reqno]{amsart} \usepackage{latexsym} \usepackage{amssymb,amsfonts} \usepackage{amscd} \usepackage[nohug]{diagrams} %\usepackage{bbold} %\usepackage{epsfig} %\parskip2ex %\parindent0pt \textheight22.8cm \textwidth15.6cm \hoffset-1.7cm \voffset-.5cm \numberwithin{equation}{section} \newtheorem{theorem}{Theorem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{definition}[theorem]{Definition} \newtheorem*{propositionno}{Proposition} \theoremstyle{remark} \newtheorem{example}{Example} \newtheorem{remark}{Remark} \newtheorem*{remarkno}{Remark} \def\Sp{\operatorname{Sp}} \def\id{\operatorname{id}} \def\Hom{\operatorname{Hom}} \def\Obj{\operatorname{Ob}} \def\GF{\operatorname{GF}} \def\f{\mathfrak{f}} \def\F{\mathfrak{F}} \def\J{\mathfrak{J}} \def\R{\mathfrak{R}} \def\ff{{\boldsymbol f}} \def\gg{{\boldsymbol g}} \def\ww{{\boldsymbol w}} \def\II{{\boldsymbol I}} \def\JJ{{\boldsymbol J}} \def\O{\mathbf{\Omega}} \def\ph{\varphi} \def\ps{\psi} \def\Eta{{\boldsymbol\eta}} \newcommand{\norm}{\triangleleft} \newcommand{\C}{\mathfrak{C}} \newcommand{\N}{\mathbb{N}} \newcommand{\T}{\underline{\underline{\tau}}} \newcommand{\E}{\underline{\underline{e}}} \newenvironment{proofof}[1] {\par\noindent{\em {\it Proof of #1.}}}{\hfill $\square$\par\medskip} \newcommand{\dbin}[2]{\left(\kern-0.4em{\binom#1#2} \kern-0.4em\right)} %\newcommand{\qed}{\hfill \mbox{$\Box$}\vspace{\baselineskip}} %\newenvironment{proof}{\noindent {\bf Proof.}}{{\qed}} \begin{document} \title[Decomposable functors and the exponential principle, II] {Decomposable functors and the exponential principle, II} \newbox\Aut \setbox\Aut\vbox{ \centerline{\sc Peter J. Cameron$^\dagger$, Christian Krattenthaler$^{\ddagger}$, \rm and \sc Thomas W. M\"uller$^\dagger$} \vskip18pt \centerline{$^\dagger$ School of Mathematical Sciences,} \centerline{Queen Mary \& Westfield College, University of London,} \centerline{Mile End Road, London E1 4NS, United Kingdom.} \centerline{\footnotesize WWW: \tt http://www.maths.qmw.ac.uk/\lower0.5ex\hbox{\~{}}pjc/} \centerline{\footnotesize WWW: \tt http://www.maths.qmw.ac.uk/\lower0.5ex\hbox{\~{}}twm/} \vskip18pt \centerline{$^\ddagger$ Fakult\"at f\"ur Mathematik, Universit\"at Wien,} \centerline{Nordbergstra\ss e 15, A-1090 Vienna, Austria.} \centerline{\footnotesize WWW: \footnotesize\tt http://www.mat.univie.ac.at/\lower0.5ex\hbox{\~{}}kratt} } \author[P. J. Cameron, C. Krattenthaler and T. W. M\"uller]{\box\Aut} \address{School of Mathematical Sciences, Queen Mary \& Westfield College, University of London, Mile End Road, London E1 4NS, United Kingdom.\newline WWW: {\tt http://www.maths.qmw.ac.uk/\lower0.5ex\hbox{\~{}}pjc/}, \tt http://www.maths.qmw.ac.uk/\lower0.5ex\hbox{\~{}}twm/.} \address{Fakult\"at f\"ur Mathematik, Universit\"at Wien, Nordbergstra{\ss}e~15, A-1090 Vienna, Austria. WWW: \tt http://www.mat.univie.ac.at/\lower0.5ex\hbox{\~{}}kratt.} \keywords{labelled combinatorial structures, multisort species, exponential principle, functor decomposition, magic squares} \subjclass[2000]{Primary 05A15; Secondary 05A16 05A19 05C30} \dedicatory{Dedi\'e \`a la m\'emoire de Pierre Leroux} \thanks{$^\ddagger$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"} \begin{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. \end{abstract} \maketitle %First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire %--first part \thispagestyle{myheadings} \font\rms=cmr8 \font\its=cmti8 \font\bfs=cmbx8 \markright{\its S\'eminaire Lotharingien de Combinatoire \bfs 61A \rms (2010), Article~B61Am\hfill} \def\thepage{} \section{Introduction} One of the corner stones of combinatorial enumeration is a theory which runs under several different names, for instance {\it theory of species} \cite{BLL}, {\it theory of exponential structures} \cite[Ch.~5]{StanBI}, {\it theory of exponential families} \cite{Wilf}, {\it symbolic method} \cite[Part~A]{FlSeAA}, {\it th\'eorie du compos\'e partitionnel} \cite{FoatAZ}, {\it theory of prefabs} \cite{BG}, 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 \cite{Joyal} (with the functorial concept of species of structures going back to Ehresmann \cite{EhreAA}) 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. A fundamental theorem in each of these theories is the so-called {\it exponential formula}. Roughly speaking, given a family $\mathcal G$ of labelled combinatorial objects (``components"), one produces a larger family $\mathcal F$ (``composite objects") whose objects are obtained by putting together various elements of $\mathcal G$. The theorem then states that the (exponential) generating function for $\mathcal F$ equals the exponential of the (exponential) generating function for $\mathcal G$. The aim of the present article is to develop a setting, where one starts with a family $\mathcal F$ of labelled combinatorial objects (``composite objects") and a composition of such objects, and then identifies, in an intrinsic way, a subfamily $\mathcal G$ of indecomposable objects (``components"), such that each element of $\mathcal F$ can be decomposed into objects from $\mathcal G$, and such that the exponential formula holds for $\mathcal F$ and $\mathcal G$. The main point here is that, in contrast to the usual set-up for the exponential formula, indecomposable objects are {\it not\/} given in advance, but are defined {\it inherently} via the composition operation. In particular, our theory leads to a uniform definition of the property to be {\it 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 \cite{DM} on the basis of two axioms for the composition operator. In the present article, we extend this approach to {\it weighted multisort species}. Moreover, we show that, actually, one of the axioms in \cite{DM} 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 \cite[Sec.~6]{Joyal}, \cite[p.~104]{BLL}) 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~\ref{foot1}). %First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire %--restoring the headers and pagenumbering \pagenumbering{arabic} \addtocounter{page}{1} \markboth{\SMALL P. J. CAMERON, C. KRATTENTHALER AND T. W. M\"ULLER}{\SMALL DECOMPOSABLE FUNCTORS AND THE EXPONENTIAL PRINCIPLE, II} % % An exponential principle in a wider context, that encompasses multisort species as a particular case, has been defined by Menni in \cite{MennAA} (see \cite{MennAB} 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 \cite[Sec.~7.1]{Joyal} --- multisort species have the structure of a {\it symmetric monoidal category}. Now, in the focus of \cite{MennAA} there are {\it 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 \cite[Prop.~1.4]{MennAA}). 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 \cite[Ex.~3.2 and Ex.~3.5 with $I=1+1+\dots+1$]{MennAA}).\footnote{Strictly speaking, weights are not discussed in \cite{MennAA}. However, it would not be difficult to include them in the theory developed in \cite{MennAA}.} 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~\ref{ex:3} in Section~\ref{sec:illust} shows (see also Section~\ref{sec:commeta} 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. %More precisely, according to \cite[Ex.~3.5]{MennAA}, a weight-free %version of our Theorem~\ref{Thm:MainThm1} can be obtained by applying %\cite[Prop.1.10]{MennAA} to the discrete groupoid with $r$ elements. %It is conceivable that \cite[Prop.1.10]{MennAA} also implies a %weight-free version of Theorem~\ref{Thm:MainThm2}, since the case of %$r=1$ is indeed derived in \cite[Ex.~3.5]{MennAA}. For this case, %Menni also observes that Axiom~(D2) is implied by the set-up. %Notwithstanding, we believe our approach to have its own merits. %While Menni's arguments make heavy use of categorical notions and %constructions (symmetric monoidal categories, Day convolution, %Kleisli categories, etc.), our exposition is merely based on the %concepts of category, (covariant) functor, and natural %transformation. Moreover, our approach readily lends itself to a %more general weighted version, an idea not pursued in \cite{MennAA}. 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 $\Eta$ that are subject to a single axiom, which, in order to be consistent with \cite{DM}, we call (D1). Furthermore, in the same section, we present our main results. These are two exponential formulae, %one being the refinement of the other, see Theorems~\ref{Thm:MainThm1} and \ref{Thm:MainThm2}. Theorem~\ref{Thm:MainThm2} refines Theorem~\ref{Thm:MainThm1} by introducing another variable whose powers keep track of the number of ``components." The proof of Theorem~\ref{Thm:MainThm2} requires two general facts about our composition operators $\Eta$, which are presented in Propositions~\ref{lem:F->Fk} and \ref{prop:Disjoint}. (It is the latter, which, in the less general context of \cite{DM}, had been assumed as a separate axiom, (D2). As our proof of Proposition~\ref{prop:Disjoint} 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 \cite{MennAA}, Menni also observed that the axiom (D2) was not necessary; see \cite[Ex.~3.5]{MennAA}. 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~\ref{prop:Disjoint}, and Lemmas~\ref{lem:assoc} and \ref{lem:Feta-assoc}. This ``$m$-permutability" comes for free in the context of \cite{MennAA} 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~\ref{sec:commeta}, and in particular the paragraph containing \eqref{eq:passoc} and \eqref{eq:pcomm}.) The proofs of Theorems~\ref{Thm:MainThm1} and \ref{Thm:MainThm2}, and of Propositions~\ref{lem:F->Fk} and \ref{prop:Disjoint}, are given in Sections~\ref{sec:main1} and \ref{sec:main2}, respectively. They require a number of auxiliary results, which are established in Sections~\ref{sec:aux1} and \ref{sec:aux2}, respectively. Sections~\ref{sec:illust} and \ref{Sec:CMT1} offer illustrations for the theory developed in Sections~\ref{Sec:MainThm}--\ref{sec:main2}. Section~\ref{sec:illust} presents three simple examples highlighting different aspects of combinatorial situations covered by Theorems~\ref{Thm:MainThm1} and \ref{Thm:MainThm2}. In Section~\ref{Sec:CMT1}, 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~\ref{sec:commeta}, discusses the relationship between Menni's theory in \cite{MennAA} and ours. Moreover, there we make Menni's characterisation (see \cite[Sec.~2.6]{MennAA}) of the simple commutative monoids that are covered by his result \cite[Prop.~1.4]{MennAA} 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 \eqref{eq:passoc} and \eqref{eq:pcomm}). Menni's characterisation implies that a family $\mathcal F$ of labelled combinatorial objects equipped with such a composition operator can be re-constructed, in a sense made precise in Theorem~\ref{thm:commeta}, from the standard operation of forming the disjoint union in $E(\mathcal G)$ (the species of sets of objects from $\mathcal G$), where $\mathcal G$ denotes again the family of indecomposable objects in $\mathcal F$. We conclude our paper by ``twisting" this construction (see Theorem~\ref{thm:Etwist}), thereby obtaining a large family of examples that fit under our theory but not under Menni's. %aims to throw light on %the question how far a family $\mathcal F$ of labelled combinatorial %objects, equipped with a composition operator in the sense indicated %above, can be from the species $E(\mathcal G)$ %of sets of indecomposable objects in %$\mathcal F$. We find that, roughly speaking, whenever the composition %operator is pointwise associative and commutative, it can be %re-constructed, in a sense made precise in Theorem~\ref{thm:commeta}, %from the standard operation of forming the disjoint %union in $E(\mathcal G)$. \section{Set-up and main results} \label{Sec:MainThm} Denote by $\widehat{\bf Set}$ the category of finite sets and injective mappings, and by {\bf Set} the subcategory consisting of finite sets and bijective maps. Moreover, for a positive integer $r$, let $\mathfrak{D}_r$ be the full subcategory of ${\bf Set}^r\times{\bf Set}^r$ whose objects are given by \[ \Obj(\mathfrak{D}_r) = \Big\{(\O_1,\O_2)\in \Obj({\bf Set}^r \times{\bf Set}^r):\,\, \O_1 \cap \O_2 = \pmb{\emptyset}\Big\}, \] where $\pmb{\emptyset}=(\emptyset,\ldots,\emptyset)$ is the element of $\Obj({\bf Set}^r)$ all of whose components are empty, and intersection is componentwise. The ingredients needed for our theory are {\it $r$-sort species} and certain {\it composition operators} defined on them. Recall from \cite{Joyal} (or see \cite[Def.~4 on p.~102]{BLL} for a definition avoiding the language of category theory) that, for a positive integer $r$, an $r$-sort species is a covariant functor $F: {\bf Set}^r\rightarrow{\bf Set}$. Given $r$ and an $r$-sort species $F$, the composition operators we have in mind are certain natural transformations $\Eta$ from the functor\footnote{The introduction of the category $\mathfrak{D}_r$ corrects a slight imprecision in the set-up of \cite{DM}.} \[ F\times F:\, \mathfrak{D}_r \overset{(F,F)} {\longrightarrow} {\bf Set} \times {\bf Set} \overset{\times}{\longrightarrow} {\bf Set} \overset{\iota}{\longrightarrow} \widehat{\bf Set} \] to the functor \[ F\circ \amalg:\, \mathfrak{D}_r \overset{\amalg} {\longrightarrow}{\bf Set}^r \overset{F}{\longrightarrow} {\bf Set} \overset{\iota}{\longrightarrow} \widehat{\bf Set}; \] that is, families $\Eta=(\eta_{(\O_1,\O_2)})_{(\O_1,\O_2) \in\Obj(\mathfrak{D}_r)}$ of injective maps, \begin{equation} \label{eq:Eta} \eta_{(\O_1,\O_2)}: F[\O_1] \times F[\O_2] \hookrightarrow F[\O_1 \amalg \O_2], \end{equation} such that, for every morphism $\ff:(\O_1,\O_2)\longrightarrow (\widetilde{\O}_1,\widetilde{\O}_2)$ of $\mathfrak{D}_r$, the diagram \begin{equation} \label{Eq:NatDiag} \begin{CD} F[\O_1]\times F[\O_2] @>\eta_{(\O_1,\O_2)}>>F[\O_1\amalg \O_2]\\ @V{(F\times F)[\ff]}VV @VV{(F\circ\amalg)[\ff]}V\\ F[\widetilde{\O}_1]\times F[\widetilde{\O}_2] @>>{\eta_{(\widetilde{\O}_1,\widetilde{\O}_2)}}> F[\widetilde{\O}_1 \amalg \widetilde{\O}_2] \end{CD} \end{equation} commutes. Here, $\times$ is the natural product (Cartesian product) in the category of sets, $\amalg$ is the natural coproduct (componentwise disjoint union) in the category ${\bf Set}^r$ and in the category ${\bf Set}$ (relying on the context to clarify the intended meaning), and $\iota: {\bf Set}\rightarrow\widehat{\bf Set}$ is the inclusion functor. In what follows, the set-theoretic operations $\cap, \cup, -$ as well as the inclusion relation $\subseteq$ and $\vert$ (restriction of morphisms) in ${\bf Set}^r$ are all understood to be componentwise.\footnote{Throughout this paper, we use the symbol $-$ to denote the difference of sets.} We shall most of the time drop the indices of $\Eta$-maps when they are clear from the context, thus writing $\eta(F[\O_1]\times F[\O_2])$ instead of $\eta_{(\O_1,\O_2)}(F[\O_1]\times F[\O_2])$, for example. We shall think of the elements of a set $\eta(F[\O_1]\times F[\O_2])$ as {\it composite objects} within $F[\O_1\amalg\O_2]$. Given an $r$-sort species $F$ and a composition operator $\Eta$ as above, the next step is to identify the subset $F_\Eta[\O]$ of {\it``indecomposable" elements} of a set $F[\O]$. It is most natural to define $F_\Eta: \Obj({\bf Set}^r) \rightarrow \Obj({\bf Set})$ via \[ F_\Eta[\O]:= \begin{cases} F[\O]\,-\,\underset{\II \neq \pmb{\emptyset} \neq \JJ} {\underset{\II\amalg \JJ=\O} {\bigcup\limits_{(\II, \JJ)\in \Obj(\mathfrak{D}_r)}}}\hspace{.8mm} \eta\big(F[\II]\times F[\JJ]\big),&\O\neq\pmb{\emptyset}\\[2mm] \emptyset,&\O=\pmb{\emptyset} \end{cases}, \qquad \O\in\Obj({\bf Set}^r). \] At this point, $F_\Eta$ is just defined as a {\it map} from $\Obj({\bf Set}^r)$ to $\Obj({\bf Set})$. In Lemma~\ref{lem:funct} in Section~\ref{sec:aux1} we shall show that $F_\Eta$ is in fact a functor, that is, an $r$-sort species. Not every natural transformation $\Eta$ 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 $\Eta: F\times F\rightarrow F\circ\amalg$ a \textit{composition operator} of $F$, if Axiom~(D1) below holds. \medskip (D1) {\it For each $\O\in\Obj({\bf Set}^r)$ and any two partitions $(\O_1,\O_2),(\widetilde{\O}_1, \widetilde{\O}_2)\in\Obj(\mathfrak{D}_r)$ of $\O$ into disjoint parts, \[ \O_1 \amalg \O_2 = \O = \widetilde{\O}_1 \amalg \widetilde{\O}_2, \] we have that} \begin{equation} \label{Eq:DecompAx} \eta\big(F[\O_1] \times F[\O_2]\big) \cap \eta\big(F[\widetilde{\O}_1] \times F[\widetilde{\O}_2]\big) = \eta\big(\eta\big(F[\O_{11}] \times F[\O_{12}]\big) \times \eta\big(F[\O_{21}] \times F[\O_{22}]\big)\big), \end{equation} \textit{where $\O_{ij}:= \O_i \cap \widetilde{\O}_j$ for $i,j\in\{1,2\}$.} \medskip An $r$-sort species $F$ will be called \textit{decomposable}, if $F\neq\emptyset$ (that is, $F[\O]\neq\emptyset$ for some $\O\in\Obj({\bf Set}^r)$, and if $F$ admits some composition operator $\Eta$. Next, we define {\it weights} on $(F,\Eta)$. Fix a commutative ring $\Lambda$ which contains the rational numbers. A family $\ww=(w_{\O})_{\O\in\Obj({\bf Set}^r)}$ of maps $w_{\O}: F[\O]\rightarrow \Lambda$ is termed a \textit{$\Lambda$-weight} on $(F,\Eta)$, if the following three conditions hold: \medskip (W0) {\it For all $x\in F[\pmb\emptyset]$, we have $w_{\pmb{\emptyset}}(x)=1$.} \smallskip (W1) \textit{For each morphism $\ff: \O_1\rightarrow \O_2$ of ${\bf Set}^r,$ the diagram} \begin{equation*} \begin{CD} F[\O_1] @>w_{\O_1}>> \Lambda\\ @V{F[\ff]}VV @VV{\mathrm{id}_\Lambda}V\\ F[\O_2] @>>w_{\O_2}> \Lambda \end{CD} \end{equation*} \textit{commutes.} \smallskip (W2) \textit{For each pair $(\O_1,\O_2)\in\Obj(\mathfrak{D}_r),$ the diagram} \begin{equation*} \begin{CD} F_\eta[\O_1]\times F[\O_2] @>\eta_{(\O_1,\O_2)}\vert_{F_\Eta[\O_1]\times F[\O_2]}>> F[\O_1\amalg\O_2]\\ @V{w_{\O_1}\vert_{F_\Eta[\O_1]}\times w_{\O_2}}VV @VV{w_{\O_1\amalg\O_2}}V\\ \Lambda\times\Lambda @>>\mbox{\scriptsize multiplication in $\Lambda$}>\Lambda \end{CD} \end{equation*} \textit{commutes.} \medskip Here, (W0) and (W1) make $F$ a {\it weighted\/} $r$-sort species (cf.\ \cite[p.~104]{BLL}), whereas (W2) demands (in a weak form) the $\Lambda$-weight $\ww$ to be compatible with the composition operator $\Eta$.% \footnote{\label{foot1}% As 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[\O]$ needs to be finite, and requiring instead that each preimage $w^{-1}_\O(\lambda)$ is finite and that the ring $\Lambda$ is {\it multiplicatively finite}, in the sense that the number of different product representations of $\lambda\in \Lambda$ is always finite.} In Section~\ref{sec:commeta}, we shall also need the concept of a {\it weak $\Lambda$-weight}, by which we mean a collection $\ww=(w_\O)_{\O\in\Obj(\mathbf{Set}^r)}$ of mappings as above satisfying (W0) and (W1), but not necessarily (W2). Given a $\Lambda$-weight $\ww=(w_{\O})_{\O\in\Obj(\mathbf{Set}^r)}$ on $(F,\Eta)$, we define the corresponding {\it exponential generating functions} for $F$ and $F_\Eta$, respectively, by\footnote{For a non-negative integer $n$, we write $[n]$ for the standard set $\{1,2,\ldots,n\}$ of cardinality $n$.} \begin{align*} \GF_F(z_1,\ldots,z_r) &:= \sum_{n_1,\ldots,n_r\geq0}\ \sum_{x\in F[([n_1],\dots,[n_r])]} w_{([n_1],\dots,[n_r])}(x) \frac { z_1^{n_1} \cdots z_r^{n_r}} {n_1!\cdots n_r!},\\ \GF_{F_\Eta}(z_1,\ldots,z_r) &:= \sum_{n_1,\ldots,n_r\geq0}\ \sum_{x\in F_\Eta[([n_1],\dots,[n_r])]} w_{([n_1],\dots,[n_r])}(x) \frac {z_1^{n_1} \cdots z_r^{n_r}} {n_1!\cdots n_r!}, \end{align*} where we suppress the dependence on $\ww$ in the notation for better readability. We are now ready to state our first main result, an \textit{exponential principle}, which generalises Part~(a) of the main result in \cite{DM}. \begin{theorem} \label{Thm:MainThm1} Let $r$ be a positive integer, $F: {\bf Set}^r \rightarrow {\bf Set}$ an $r$-sort species, and let $\Eta: F\times F\rightarrow F\circ\amalg$ be a natural transformation. If $F$ is decomposable and $\Eta$ is a composition operator for $F,$ then the generating functions $\GF_F$ and $\GF_{F_\Eta}$ are connected via the relation \begin{equation} \label{Eq:MainThm1} \GF_F(z_1,\ldots,z_r) = \exp\big(\GF_{F_\Eta}(z_1,\ldots,z_r)\big). \end{equation} \end{theorem} The proof of Theorem~\ref{Thm:MainThm1} is given in Section~\ref{sec:main1}. It requires several preparatory results, which are established in the next section. \medskip In analogy to \cite{DM}, there is a refinement of Theorem~\ref{Thm:MainThm1} in the spirit of \cite{LaLeAZ,ScSoAA}, which we explain next. Making use of the map $F_\Eta$ defined above, we define a sequence of mappings \[ F_\Eta^{(k)}: \Obj({\bf Set}^r)\rightarrow\Obj({\bf Set}),\quad k\geq0, \] with the property that $F_\Eta^{(k)}[\O]\subseteq F[\O]$ by induction on $k$ via \[ F_\Eta^{(0)}[\O]:= \begin{cases} F[\pmb{\emptyset}],&\O=\pmb{\emptyset}\\[1mm] \emptyset,&\O\neq\pmb{\emptyset} \end{cases} \] and \begin{equation} \label{eq:Fetakdef} F_\Eta^{(k)}[\O]:=\underset{\O_1\subseteq\O}{\bigcup_{\O_1\in\Obj({\bf Set}^r)}}\hspace{.8mm}\eta\big(F_\Eta[\O_1]\times F_\Eta^{(k-1)}[\O - \O_1]\big),\quad k\geq1. \end{equation} As the definition suggests, one should think of $F_\Eta^{(k)}[\O]$ as the subset of objects in $F[\O]$ consisting of exactly $k$ ``indecomposable" elements (components). An immediate induction on \begin{equation} \label{eq:omabs} \|\O\| = \|(\Omega^{(1)},\Omega^{(2)},\ldots,\Omega^{(r)})\|:=\sum_{j=1} ^{r} |\Omega^{(j)}| \end{equation} shows that \begin{equation} \label{Eq:FetakBoundary} F_\Eta^{(k)}[\O] = \emptyset,\quad k>\|\O\|. \end{equation} Again, by definition, $F_\Eta^{(k)}$ is just a {\it map} from $\Obj({\bf Set}^r)$ to $\Obj({\bf Set})$. In Lemma~\ref{lem:kfunct} in Section~\ref{sec:aux2} we shall show that $F_\Eta^{(k)}$ is in fact a functor, that is, an $r$-sort species. It is not difficult to see that, for any $\O\in \Obj(\mathbf{Set}^r)$, the sets $F_\Eta^{(k)}[\O]$ with $k=0,1,2,\dots$ cover all of $F[\O]$. \begin{proposition} \label{lem:F->Fk} For every $\O\in\Obj({\bf Set}^r)$, we have \begin{equation} \label{Eq:FOmegaFilt} F[\O] = \bigcup_{k\geq0} F_\Eta^{(k)}[\O]. \end{equation} \end{proposition} The proof of Proposition~\ref{lem:F->Fk} can be found in Section~\ref{sec:main2}. In \cite{DM}, a second axiom, (D2), was imposed on the composition operators $\Eta$ for obtaining a refined exponential principle that takes into account the filtration given by the sets $F_\Eta^{(k)}[\O]$ appearing on the right-hand side of \eqref{Eq:FOmegaFilt} (for the case of $1$-sort species): it required pairwise disjointness of the sets $F_\Eta^{(k)}[\O]$ for $k=0,1,2,\dots$. 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. \begin{proposition} \label{prop:Disjoint} If $F:\mathrm{\bf Set}^r\rightarrow\mathrm{\bf Set}$ is an $r$-sort species and $\Eta$ is a composition operator for $F,$ then we have, for\footnote{We denote by $\N_0$ the set of non-negative integers.} $k,\ell\in\N_0$ and $k\neq \ell,$ \begin{equation} \label{Eq:Disjoint} F_\Eta^{(k)}[\O] \cap F_\Eta^{(\ell)}[\O] = \emptyset,\quad\O\in\Obj(\mathrm{\bf Set}^r). \end{equation} \end{proposition} Proposition~\ref{prop:Disjoint} is also proved in Section~\ref{sec:main2}. Its proof depends crucially on the fact that ``$\Eta$-bracketings" of $F$-sets and $F_\Eta$-sets do not depend on the order of the terms $F[\O]$ respectively $F_\Eta[\O]$ involved, nor on the type of bracketing used; see Lemmas~\ref{lem:assoc} and \ref{lem:Feta-assoc} in Sections~\ref{sec:aux1} and \ref{sec:aux2}, respectively. From a technical point of view, this is the decisive improvement over the results in \cite{DM}, and it is the reason that the dependence of Axiom~(D2) from Axiom~(D1) was not observed there. Given a $\Lambda$-weight $\ww$ on $(F,\Eta)$, the above propositions allow us to refine the weighting to $$\widetilde w_{\O}(x):=y^kw_{\O}(x),\quad \quad x\in F_\Eta^{(k)}[\O].$$ We then can define the refined generating function \begin{align*} \widetilde \GF_{F}(z_1,\ldots,z_r,y)&:= \sum_{n_1,\ldots,n_r\geq0} \sum_{x\in F[([n_1],\dots,[n_r])]} \widetilde w_{([n_1],\dots,[n_r])}(x)\, \frac{z_1^{n_1} \cdots z_r^{n_r} } {n_1!\cdots n_r!}\\ &\hphantom{:}=\sum_{n_1,\ldots,n_r\geq0}\ \sum_{k\geq0} \sum_{x\in F_\Eta^{(k)}[([n_1],\dots,[n_r])]} y^k\,w_{([n_1],\dots,[n_r])}(x)\, \frac{z_1^{n_1} \cdots z_r^{n_r} } {n_1!\cdots n_r!}. \end{align*} With the above notation, we have the following refinement of Theorem~\ref{Thm:MainThm1}, which is our second main result. \begin{theorem} \label{Thm:MainThm2} Under the hypotheses of Theorem~{\em \ref{Thm:MainThm1},} we have \begin{equation} \label{Eq:MainThm21} \widetilde \GF_{F}(z_1,\ldots,z_r,y) = \exp\big(y\GF_{F_\Eta}(z_1,\ldots,z_r)\big), \end{equation} as well as \begin{equation} \label{Eq:MainThm22} \widetilde \GF_{F}(z_1,\ldots,z_r,y) = \big(\GF_F(z_1,\ldots,z_r)\big)^y. \end{equation} \end{theorem} The proof of Theorem~\ref{Thm:MainThm2} is given in Section~\ref{sec:main2}, as a simple consequence of (the proof of) Proposition~\ref{prop:Disjoint}. \section{Auxiliary results, I} \label{sec:aux1} The purpose of this section is to establish several lemmas, which will be needed in the next section in the proof of Theorem~\ref{Thm:MainThm1}. At the same time, they also form the basis for the proofs of the auxiliary results in Section~\ref{sec:aux2}, which eventually will lead to proofs of Propositions~\ref{lem:F->Fk} and \ref{prop:Disjoint}, and of Theorem~\ref{Thm:MainThm2}, in Section~\ref{sec:main2}. In all of this section, we assume that $F$ is a decomposable $r$-sort species with composition operator $\Eta$. \begin{lemma} \label{lem:emptyset} We have $|F[\pmb{\emptyset}]| = 1$. \end{lemma} \begin{proof} By the injectivity of $\eta_{(\pmb{\emptyset},\pmb{\emptyset})}: F[\pmb{\emptyset}]\times F[\pmb{\emptyset}] \rightarrow F[\pmb{\emptyset}]$, the set $F[\pmb{\emptyset}]$ is either empty or a $1$-set. Suppose that $F[\pmb{\emptyset}] = \emptyset$. Choose $\O_1 = (\Omega_1^{(1)},\ldots, \Omega_1^{(r)}) \in \Obj({\bf Set}^r)$ with $F[\O_1]\neq\emptyset$, and $\O_2= (\Omega_2^{(1)}, \ldots, \Omega_2^{(r)})\in\Obj({\bf Set}^r)$ such that $\O_1 \cap \O_2 = \pmb{\emptyset}$ and $|\Omega_1^{(i)}| = |\Omega_2^{(i)}|$ for $1\leq i\leq r$. Now consider (D1) for the partition $\O:=\O_1 \amalg \O_2$, $\widetilde{\O}_i:= \O_i$ for $i=1,2$. By the functoriality of $F$, we also have $F[\O_2]\neq\emptyset$ and, consequently, the left-hand side of (\ref{Eq:DecompAx}) is non-empty, whereas the right-hand side of (\ref{Eq:DecompAx}) would be empty in case $F[\pmb{\emptyset}]=\emptyset$, a contradiction. \end{proof} \begin{lemma}[\sc Commutativity for $(F,\Eta)$] \label{lem:comm} For every pair $(\O_1,\O_2)\in\Obj(\mathfrak{D}_r)$, we have \begin{equation} \label{Eq:EtaComm} \eta\big(F[\O_1] \times F[\O_2]\big) = \eta\big(F[\O_2] \times F[\O_1]\big). \end{equation} \end{lemma} \begin{proof} Applying Axiom~(D1) to the partitions \[ \O:= \O_1 \amalg \O_2 = \O_2 \amalg \O_1, \] we find that \begin{align*} \mathfrak{I}&:= \eta\big(F[\O_1] \times F[\O_2]\big) \cap \eta\big(F[\O_2] \times F[\O_1]\big)\\[2mm] &= \eta\big(\eta\big(F[\O_1 \cap \O_2] \times F[\O_1]\big) \times \eta\big(F[\O_2] \times F[\O_1 \cap \O_2]\big)\big). \end{align*} By Lemma~\ref{lem:emptyset} and injectivity of the $\Eta$-maps, the map \[ \eta_{(\pmb{\emptyset},\O_1)}: F[\pmb{\emptyset}] \times F[\O_1] \rightarrow F[\O_1] \] is surjective; that is, \[ \eta\big(F[\O_1 \cap \O_2] \times F[\O_1]\big) = F[\O_1]. \] Similarly, we have \[ \eta\big(F[\O_2] \times F[\O_1 \cap \O_2]\big) = F[\O_2]. \] Thus, \[ \mathfrak{I} = \eta\big(F[\O_1] \times F[\O_2]\big). \] By an analogous application of (D1) and Lemma~\ref{lem:emptyset} to the partitions \[ \O = \O_2 \amalg \O_1 = \O_1 \amalg \O_2, \] we find that \[ \mathfrak{I} = \eta\big(F[\O_2] \times F[\O_1]\big), \] and the proof is complete. \end{proof} \begin{lemma}[\sc $3$-Associativity for $(F,\Eta)$] \label{lem:assoc3} For pairwise disjoint $\O_1,\O_2,\O_3\in\break\Obj({\bf Set}^r)$, we have \begin{equation} \label{Eq:EtaAss3} \eta\big(\eta\big(F[\O_1] \times F[\O_2]\big) \times F[\O_3]\big)= \eta\big(F[\O_1] \times \eta\big(F[\O_2]\times F[\O_3]\big)\big). \end{equation} \end{lemma} \begin{proof} We shall show that both sides of (\ref{Eq:EtaAss3}) equal the intersection \[ \mathfrak{I}:= \eta\big(F[\O_1 \amalg \O_2] \times F[\O_3]\big) \cap \eta\big(F[\O_1] \times F[\O_2 \amalg \O_3]\big). \] Applying (D1) to the partitions \[ \O:= (\O_1 \amalg \O_2) \amalg \O_3 = \O_1 \amalg (\O_2 \amalg \O_3), \] we find that \[ \mathfrak{I} = \eta\big(\eta\big(F[\O_1] \times F[\O_2]\big) \times \eta\big(F[\O_1 \cap \O_3] \times F[\O_3]\big)\big); \] and, arguing as in the proof of Lemma~\ref{lem:comm}, this equation simplifies to \[ \mathfrak{I} = \eta\big(\eta\big(F[\O_1] \times F[\O_2]\big)\times F[\O_3]\big). \] The same argument, when applied to the partitions \[ \O = \O_1 \amalg (\O_2 \amalg \O_3) = (\O_1 \amalg \O_2) \amalg \O_3, \] yields \[ \mathfrak{I} = \eta\big(F[\O_1] \times \eta\big(F[\O_2] \times F[\O_3]\big)\big), \] whence (\ref{Eq:EtaAss3}). \end{proof} For the sake of convenience, for pairwise disjoint elements $\O_1,\dots,\O_m\in \Obj(\mathbf{Set}^r)$, let us call expressions formed by applying $\Eta$-maps to $F[\O_1]$, \dots, $F[\O_m]$ (in any order), with each set $F[\O_i]$ occurring exactly once, an {\em $\Eta$-bracketing of $F[\O_1]$, \dots, $F[\O_m]$}. More formally, for any $\O\in\Obj(\mathbf{Set}^r)$, we call the set $F[\O]$ an $\Eta$-bracketing of $F[\O]$; and, given an $\Eta$-bracketing $B_1$ of $F[\O_{i_1}]$, \dots, $F[\O_{i_k}]$ and an $\Eta$-bracketing $B_2$ of $F[\O_{i_{k+1}}]$, \dots, $F[\O_{i_m}]$, with $1\le k\le n-1$ and $\{i_1,i_2,\dots,i_m\}=\{1,2,\dots,m\}$, the expression $\eta(B_1\times B_2)$ is, by definition, an $\Eta$-bracketing of $F[\O_1]$, \dots, $F[\O_m]$. For example, the left-hand side and the right-hand side of \eqref{Eq:EtaAss3} are two possible $\Eta$-bracketings of $F[\O_1]$, $F[\O_2]$, $F[\O_3]$, as are $$\eta\big(\eta\big(F[\O_3] \times F[\O_2]\big) \times F[\O_1]\big) \quad \text{and}\quad \eta\big(F[\O_3] \times \eta\big(F[\O_1]\times F[\O_2]\big)\big). $$ A simple consequence of Lemma~\ref{lem:comm} and (the proof of) Lemma~\ref{lem:assoc3} is the following fact. \begin{corollary} \label{cor:eta3} All $\Eta$-bracketings of $F[\O_1]$, $F[\O_2]$, $F[\O_3]$ are equal to \begin{equation} \label{eq:eta3} \eta\big(F[\O_1\amalg \O_2]\times F[\O_3]\big) \cap\eta\big(F[\O_1\amalg \O_3]\times F[\O_2]\big) \cap\eta\big(F[\O_2\amalg \O_3]\times F[\O_1]\big). \end{equation} \end{corollary} \begin{proof} From the proof of Lemma~\ref{lem:assoc3}, we know that \begin{equation*} \eta\big(\eta\big(F[\O_1] \times F[\O_2]\big) \times F[\O_3]\big)= \eta\big(F[\O_1 \amalg \O_2] \times F[\O_3]\big) \cap \eta\big(F[\O_1] \times F[\O_2 \amalg \O_3]\big). \end{equation*} If, in this equation, we interchange $\O_1$ and $\O_2$ and use Lemma~\ref{lem:comm} (commutativity), then we obtain \begin{equation*} \eta\big(\eta\big(F[\O_1] \times F[\O_2]\big) \times F[\O_3]\big)= \eta\big(F[\O_1 \amalg \O_2] \times F[\O_3]\big) \cap \eta\big(F[\O_2] \times F[\O_1 \amalg \O_3]\big). \end{equation*} Both equations together, plus another application of Lemma~\ref{lem:comm}, imply our claim. \end{proof} \begin{lemma}[\sc $4$-Permutability for $(F,\Eta)$] \label{lem:assoc4} If\/ $\O_1,\O_2,\O_3,\O_4$ are pairwise disjoint elements of\/ $\Obj(\mathbf{Set}^r)$, then all $\Eta$-bracketings of $F[\O_1]$, $F[\O_2]$, $F[\O_3]$, $F[\O_4]$ are equal to each other. \end{lemma} \begin{proof} The possible $\Eta$-bracketings of $F[\O_1]$, $F[\O_2]$, $F[\O_3]$, $F[\O_4]$ are \begin{gather} \label{eq:4A} \eta\big(\eta\big(\eta\big(F[\O_1]\times F[\O_2]\big) \times F[\O_3]\big)\times F[\O_4]\big),\\ \label{eq:4B} \eta\big(\eta\big(F[\O_1]\times \eta\big(F[\O_2] \times F[\O_3]\big)\big)\times F[\O_4]\big),\\ \label{eq:4C} \eta\big(\eta\big(F[\O_1]\times F[\O_2]\big) \times \eta\big(F[\O_3]\times F[\O_4]\big)\big),\\ \label{eq:4D} \eta\big(F[\O_1]\times \eta\big(\eta\big(F[\O_2] \times F[\O_3]\big)\times F[\O_4]\big)\big),\\ \label{eq:4E} \eta\big(F[\O_1]\times \eta\big(F[\O_2] \times \eta\big(F[\O_3]\times F[\O_4]\big)\big)\big), \end{gather} together with all expressions arising from the above by permuting $F[\O_1]$, $F[\O_2]$, $F[\O_3]$, $F[\O_4]$. By Lemma~\ref{lem:assoc3} (3-associativity), the bracketing \eqref{eq:4A} equals the bracketing \eqref{eq:4B}, and the bracketing \eqref{eq:4D} equals the bracketing \eqref{eq:4E}. It suffices therefore to prove the equality of \eqref{eq:4A}, \eqref{eq:4C}, \eqref{eq:4E}, and all expressions arising from these three by permuting $F[\O_1]$, $F[\O_2]$, $F[\O_3]$, $F[\O_4]$. Applying (D1) to the partitions $$\O:=(\O_1\amalg \O_2)\amalg (\O_3\amalg \O_4)= (\O_1\amalg \O_3)\amalg (\O_2\amalg \O_4),$$ we find that \begin{multline*} \eta\big(F[\O_1\amalg\O_2]\times F[\O_3\amalg \O_4]\big) \cap \eta\big(F[\O_1\amalg\O_3]\times F[\O_2\amalg \O_4]\big)\\ = \eta\big(\eta\big(F[\O_1]\times F[\O_2]\big) \times \eta\big(F[\O_3]\times F[\O_4]\big)\big). \end{multline*} Using this equation, as well as the one which arises by interchanging $\O_1$ and $\O_2$ and applying Lemma~\ref{lem:comm} (commutativity) on the resulting right-hand side, we obtain \begin{multline} \label{eq:eta22} \eta\big(\eta\big(F[\O_1]\times F[\O_2]\big) \times \eta\big(F[\O_3]\times F[\O_4]\big)\big)\\ = \eta\big(F[\O_1\amalg\O_2]\times F[\O_3\amalg \O_4]\big) \cap \eta\big(F[\O_1\amalg\O_3]\times F[\O_2\amalg \O_4]\big)\\ \cap \eta\big(F[\O_2\amalg\O_3]\times F[\O_1\amalg \O_4]\big) . \end{multline} On the other hand, by Corollary~\ref{cor:eta3}, the expression $$\eta\big(\eta\big(F[\O_1]\times F[\O_2]\big)\times F[\O_3]\big)$$ equals the expression \eqref{eq:eta3}. Therefore, ``bracketing" these two expressions by $\eta(\,.\,\times F[\O_4])$, using the injectivity of $\eta$, and applying Lemma~\ref{lem:assoc3} (3-associativity) to the expression resulting from \eqref{eq:eta3}, we arrive at \begin{multline} \label{eq:eta123} \eta\big(\eta\big(\eta\big(F[\O_1]\times F[\O_2]\big)\times F[\O_3]\big) \times F[\O_4]\big)\\ = \eta\big(F[\O_1\amalg \O_2]\times \eta\big(F[\O_3]\times F[\O_4]\big)\big) \cap\eta\big(F[\O_1\amalg \O_3]\times \eta\big(F[\O_2]\times F[\O_4]\big)\big)\\ \cap\eta\big(F[\O_2\amalg \O_3]\times \eta\big(F[\O_1]\times F[\O_4]\big)\big). \end{multline} Since $\eta\big(F[\O_3]\times F[\O_4]\big)\subseteq F[\O_3\amalg\O_4]$, and similar inclusions hold for other combinations of the $\O_i$'s, we have \begin{align*} \eta\big(F[\O_1\amalg \O_2]\times \eta\big(F[\O_3]\times F[\O_4]\big)\big) &\subseteq \eta\big(F[\O_1\amalg \O_2]\times F[\O_3\amalg\O_4]\big), \\ \eta\big(F[\O_1\amalg \O_3]\times \eta\big(F[\O_2]\times F[\O_4]\big)\big) &\subseteq \eta\big(F[\O_1\amalg \O_3]\times F[\O_2\amalg\O_4]\big), \\ \eta\big(F[\O_2\amalg \O_3]\times \eta\big(F[\O_1]\times F[\O_4]\big)\big) &\subseteq \eta\big(F[\O_2\amalg \O_3]\times F[\O_1\amalg\O_4]\big). \end{align*} Altogether, these inclusions imply that the right-hand side of \eqref{eq:eta123} is contained in the right-hand side of \eqref{eq:eta22}. We infer that \begin{equation} \label{eq:22eta123} \eta\big(\eta\big(\eta\big(F[\O_1]\times F[\O_2]\big)\times F[\O_3]\big) \times F[\O_4]\big)\subseteq \eta\big(\eta\big(F[\O_1]\times F[\O_2]\big) \times \eta\big(F[\O_3]\times F[\O_4]\big)\big). \end{equation} However, by injectivity of the $\Eta$-maps, both sides of \eqref{eq:22eta123} have cardinality $$\vert F[\O_1]\vert\cdot \vert F[\O_2]\vert\cdot \vert F[\O_3]\vert\cdot \vert F[\O_4]\vert.$$ Hence, they must be equal, which proves the equality of \eqref{eq:4A} and \eqref{eq:4C}. An analogous argument proves equality of \eqref{eq:4C} and \eqref{eq:4E}. Since, by Lemma~\ref{lem:comm} (commutativity), the right-hand side of \eqref{eq:eta22} is invariant under permutation of $\O_1,\O_2,\O_3,\O_4$, the proof is complete. \end{proof} The (proof of the) above lemma, combined with Lemma~\ref{lem:comm} and Corollary~\ref{cor:eta3}, leads to the following observation. \begin{corollary} \label{cor:eta4} All $\Eta$-bracketings of $F[\O_1]$, $F[\O_2]$, $F[\O_3]$, $F[\O_4]$ are equal to \begin{multline} \label{eq:eta4} \eta\big(F[\O_1\amalg\O_2]\times F[\O_3\amalg \O_4]\big) \cap \eta\big(F[\O_1\amalg\O_3]\times F[\O_2\amalg \O_4]\big)\\ \cap \eta\big(F[\O_2\amalg\O_3]\times F[\O_1\amalg \O_4]\big)\\ \cap\eta\big(F[\O_1] \times F[ \O_2\amalg \O_3 \amalg\O_4]\big) \cap\eta\big(F[\O_2] \times F[ \O_1\amalg \O_3 \amalg\O_4]\big)\\ \cap\eta\big(F[\O_3] \times F[ \O_1\amalg \O_2 \amalg\O_4]\big) \cap\eta\big(F[\O_4] \times F[ \O_1\amalg \O_2 \amalg\O_3]\big). \end{multline} \end{corollary} \begin{proof} By Corollary~\ref{cor:eta3}, we have \begin{multline*} \eta\big(F[\O_1\amalg \O_2]\times \eta\big(F[\O_3]\times F[\O_4]\big)\big)\\ = \eta\big(F[\O_1\amalg\O_2\amalg \O_3]\times F[\O_4]\big) \cap\eta\big(F[\O_1\amalg \O_2\amalg \O_4]\times F[\O_3]\big)\\ \cap\eta\big(F[\O_3\amalg \O_4]\times F[\O_1\amalg\O_2]\big). \end{multline*} Analogous identities hold for the other two terms on the right-hand side of \eqref{eq:eta123}. If we combine this with Lemma~\ref{lem:comm} (commutativity) and Lemma~\ref{lem:assoc4} (4-permutability), then the claim follows immediately. \end{proof} Before we state the general permutability result, let us introduce the following short-hand notation, which will be used in its proof. Given a subset $I$ of $[m]$, where $I=\{i_1,i_2,\dots,i_k\}$ with $i_10$, \begin{multline} \label{Eq:psiFEval1} w\big(F[([n_1],\ldots, [n_r])]\big)\\ = \underset{1\in\Omega_1^{(\rho)}}{\sum_{\Omega_1^{(i)} \subseteq [n_i]\,(1\leq i\leq r)}}\, w\big(F_\Eta[(\Omega_1^{(1)},\ldots, \Omega_1^{(r)})]\big)\cdot w\big(F [([n_1] - \Omega_1^{(1)},\ldots, [n_r]-\Omega_1^{(r)})]\big). \end{multline} Using the functoriality of $F$ and $F_\Eta$, together with Axiom~(W1), each $\O_1$ with \[ \O_1 = (\Omega_1^{(1)},\ldots,\Omega_1^{(r)})\subseteq ([n_1],\ldots, [n_r]), \] $(1,\rho)\in\O_1$, and cardinalities $|\Omega_1^{(i)}|=\mu_i$ ($1\leq i\leq r$), is seen to contribute \begin{equation} \label{Eq:IntCount} w\big(F_\Eta[([\mu_1],\ldots, [\mu_r])]\big)\cdot w\big(F [([n_1-\mu_1] ,\ldots, [n_r-\mu_r])]\big) \end{equation} to the right-hand side of (\ref{Eq:psiFEval1}). We observe that (\ref{Eq:IntCount}) does not depend upon $\O_1$ itself, but only on the cardinalities $\mu_1,\ldots, \mu_r$ of the components $\Omega_1^{(1)},\ldots, \Omega_1^{(r)}$. Therefore, the \[ \frac{\mu_\rho}{n_\rho} \prod_{1\leq i\leq r} \binom{n_i}{\mu_i} \] elements $\O_1\in\Obj(\mathbf{Set}^r)$ with $\O_1\subseteq ([n_1],\ldots,[n_r])$, $(1,\rho)\in\O_1$, and such that $|\Omega_1^{(i)}| = \mu_i$ for $1\leq i\leq r$, contribute \[ \frac{\mu_\rho}{n_\rho}\, \bigg(\prod_{1\leq i\leq r} \binom{n_i}{\mu_i}\bigg) w\big(F_\Eta[([\mu_1],\ldots, [\mu_r])]\big)\cdot w\big(F [([n_1-\mu_1] ,\ldots, [n_r-\mu_r])]\big) \] to the right-hand side of (\ref{Eq:psiFEval1}), and we obtain \begin{multline*} w\big(F[([n_1],\ldots, [n_r])]\big) = {\sum_{0\leq\mu_i\leq n_i\,(1\leq i\leq r)}}\, \frac{\mu_\rho}{n_\rho}\, \bigg(\prod_{1\leq i\leq r} \binom{n_i}{\mu_i}\bigg) w\big(F_\Eta[([\mu_1],\ldots, [\mu_r])]\big)\\ \kern7cm \cdot w\big(F [([n_1-\mu_1] ,\ldots, [n_r-\mu_r])]\big) ,\\ n_\rho>0, \end{multline*} or, equivalently, \begin{multline} \label{Eq:psiFEval2} n_\rho\cdot w\big(F[([n_1],\ldots, [n_r])]\big) = {\sum_{0\leq\mu_i\leq n_i\,(1\leq i\leq r)}}\, \mu_\rho \bigg(\prod_{1\leq i\leq r} \binom{n_i}{\mu_i}\bigg) w\big(F_\Eta[([\mu_1],\ldots, [\mu_r])]\big)\\ \kern7cm \cdot w\big(F [([n_1-\mu_1] ,\ldots, [n_r-\mu_r])]\big) , \end{multline} as long as $n_\rho>0$. However, Equation~\eqref{Eq:psiFEval2} holds as well for $n_\rho=0$, with both sides vanishing, so that we are allowed to drop the restriction $n_\rho>0$. Fix $\rho\in[r]$, multiply both sides of (\ref{Eq:psiFEval2}) by \[ {z_1^{n_1} \cdots z_{\rho-1}^{n_{\rho-1}} z_\rho^{n_\rho-1}z_{\rho+1}^{n_{\rho+1}} \cdots z_r^{n_r}} / {(n_1! \cdots n_r!)}, \] and sum over all tuples $(n_1,\ldots,n_r)\in\N_0^r$, to get \begin{multline} \label{Eq:PsiFEval1} {\sum_{n_1,\ldots,n_r\geq0}}\, w\big(F[([n_1],\ldots,[n_r])]\big)\,\frac { z_1^{n_1} \cdots z_{\rho-1}^{n_{\rho-1}} z_\rho^{n_\rho-1}z_{\rho+1}^{n_{\rho+1}} \cdots z_r^{n_r}} {n_1! \cdots n_{\rho-1}!\, (n_\rho-1)!\,n_{\rho+1}! \cdots n_r!}\\ \kern-4cm = {\sum_{n_1,\ldots,n_r\geq0}}\ {\sum_{0\leq\mu_i\leq n_i\,(1\leq i\leq r)}}\, \frac{w\big(F_\Eta[([\mu_1],\ldots,[\mu_r])]\big)} {\mu_1! \cdots \mu_{\rho-1}!\, (\mu_\rho-1)!\, \mu_{\rho+1}!\cdots \mu_r!}\\ \cdot\frac{w\big(F[([n_1-\mu_1], \ldots,[n_r-\mu_r])]\big)}{(n_1-\mu_1)! \cdots (n_r-\mu_r)!}\, z_1^{n_1} \cdots z_{\rho-1}^{n_{\rho-1}} z_\rho^{n_\rho-1}z_{\rho+1}^{n_{\rho+1}} \cdots z_r^{n_r}, \end{multline} where $1/(-1)!$ has to be interpreted as $0$. %The bracketed expression on the right-hand side of %(\ref{Eq:PsiFEval1}) is seen to equal\footnote{Given %$(n_1,\ldots,n_r)\in \N_0^r$ and a %formal series %\[ %F(z_1,\ldots,z_r)= \sum_{\nu_1,\ldots,\nu_r\geq0} %\,\sum_{\lambda\in\Lambda} %a_{\nu_1,\ldots,\nu_r,\lambda}\, z_1^{\nu_1} \cdots %z_r^{\nu_r} \lambda, %\] %we denote by %\[ %\left\langle F(z_1,\ldots,z_r)\,\Big\vert\, %z_1^{n_1} \cdots z_r^{n_r}\right\rangle %\] %the coefficient of $z_1^{n_1} \cdots z_r^{n_r}$ in %$F(z_1,\ldots,z_r)$.} %\[ %\Bigg\langle \frac{\partial \GF_{F_\Eta}} %{\partial z_\rho}\,\GF_F\, \Bigg\vert\, z_1^{n_1} % \cdots z_{\rho-1}^{n_{\rho-1}} %z_\rho^{n_\rho-1} z_{\rho+1}^{n_{\rho+1}} \cdots %z_r^{n_r}\Bigg\rangle. %\] The left-hand side equals \[ \frac{\partial \GF_F}{\partial z_\rho}, \] while the right-hand side is identified as \[ \frac{\partial \GF_{F_\Eta}}{\partial z_\rho} \,\GF_F; \] whence the equations \begin{equation} \label{Eq:PsiFEtaEval2} \frac{\partial \GF_F}{\partial z_\rho} = \frac{\partial \GF_{F_\Eta}}{\partial z_\rho} \,\GF_F, \qquad 1\leq\rho\leq r. \end{equation} Set \[ Q(z_1,\ldots,z_r):= \GF_F(z_1,\ldots,z_r) \exp\big(-\GF_{F_\Eta}(z_1,\ldots,z_r)\big). \] Then, in view of Equations (\ref{Eq:PsiFEtaEval2}), the series $Q$ satisfies \[ \frac{\partial Q}{\partial z_\rho} = 0, \qquad 1\leq\rho\leq r. \] These last equations force $Q$ to be independent of $z_1,z_2,\dots,z_r$. However, since\break $\GF_{F_\Eta}(0,\ldots,0) = 0$ by definition of $F_\Eta$, and since $\GF_F(0,\ldots,0)=1$ by Axiom~(W0) and Lemma~\ref{lem:emptyset}, direct inspection shows that \[ Q(0,0,\dots,0) = 1, \] and \eqref{Eq:MainThm1} follows. \qed \section{Auxiliary results, II} \label{sec:aux2} In this section, we complement the results of Section~\ref{sec:aux1} by establishing several further results which will be needed in the proofs of Proposition~\ref{prop:Disjoint} and Theorem~\ref{Thm:MainThm2}, to be given in the next section. The first lemma provides the analogue of Lemma~\ref{lem:assoc} for $F_\Eta$, namely that arbitrary permutability holds also for $\Eta$-bracketings of $F_\Eta$-images (see the subsequent paragraph for the precise definition). All the remaining lemmas concern the maps $F_\Eta^{(k)}$. In all of this section, we assume that $F$ is a decomposable $r$-sort species with composition operator $\Eta$. In complete analogy with the corresponding definition in Section~\ref{sec:aux1}, we define the\break concept of an {\em$\Eta$-bracketing of $F_\Eta[\O_1], \dots, F_\Eta[\O_m]$} for pairwise disjoint elements\break $\O_1,\dots,\O_m\in \Obj(\mathbf{Set}^r)$: simply replace $F$ by $F_\Eta$ everywhere in the definition just after the proof of Lemma~\ref{lem:assoc3}. \begin{lemma}[\sc $m$-Permutability for $(F_\Eta,\Eta)$] \label{lem:Feta-assoc} If\/ $\O_1,\dots,\O_m$ are pairwise disjoint elements of\/ $\Obj(\mathbf{Set}^r)$, then all $\Eta$-bracketings of $F_\Eta[\O_1]$, \dots, $F_\Eta[\O_m]$ are equal to each other. \end{lemma} \begin{proof} Since $F_\Eta[\pmb\emptyset]=\emptyset$ by definition of $F_\Eta$, our claim holds if at least one of $\O_1,\dots,\O_m$ equals $\pmb\emptyset$. Hence, we may assume that all of $\O_1,\dots,\O_m$ are non-empty. Next we note that, for sets $M_1,\dots,M_m,A_1,\dots,A_m$, we have \begin{multline} \label{eq:complement} (M_1- A_1)\times (M_2- A_2)\times\dots\times (M_m- A_m)\\=M_1\times M_2\times \cdots \times M_m- \Bigg(\bigcup_{k=1}^m M_1\times\cdots\times M_{k-1}\times A_k\times M_{k+1}\times \cdots \times M_m\Bigg). \end{multline} Now assume that we are given two $\Eta$-bracketings of $F_\Eta[\O_1],\dots,F_\Eta[\O_m]$, say $$B_\Eta\big(F_\Eta[\O_1],\dots,F_\Eta[\O_m]\big) \quad \text{and}\quad \bar B_\Eta\big(F_\Eta[\O_1],\dots,F_\Eta[\O_m]\big).$$ Substituting the definition of $F_\Eta$ into $B_\Eta\big(F_\Eta[\O_1],\dots,F_\Eta[\O_m]\big)$, and applying Ident\-ity~\eqref{eq:complement} plus injectivity of $\Eta$-maps, we find that \begin{multline*} B_\Eta\big(F_\Eta[\O_1],\dots,F_\Eta[\O_m]\big) =B_\Eta\big(F[\O_1],\dots,F[\O_m]\big)\\ - \bigcup_{k=1}^m B_\Eta\Bigg( F[\O_1],\dots, F[\O_{k-1}], \underset{\II \neq \pmb{\emptyset} \neq \JJ} {\underset{\II\amalg \JJ=\O_k} {\bigcup\limits_{(\II, \JJ)\in \Obj(\mathfrak{D}_r)}}}\hspace{.8mm} \eta\big(F[\II]\times F[\JJ]\big), F[\O_{k+1}], \dots, F[\O_m]\Bigg)\\ = B_\Eta\big(F[\O_1],\dots,F[\O_m]\big) \kern10.5cm\\ - \bigcup_{k=1}^m\ \underset{\II \neq \pmb{\emptyset} \neq \JJ} {\underset{\II\amalg \JJ=\O_k} {\bigcup\limits_{(\II, \JJ)\in \Obj(\mathfrak{D}_r)}}}\hspace{.8mm} B_\Eta\big( F[\O_1],\dots, F[\O_{k-1}], \eta\big(F[\II]\times F[\JJ]\big), F[\O_{k+1}], \dots, F[\O_m]\big). \end{multline*} The same argument shows that $\bar B_\Eta\big(F_\Eta[\O_1],\dots,F_\Eta[\O_m]\big)$ equals the last expression where every occurrence of $B_\Eta$ is replaced by $\bar B_\Eta$. By Lemma~\ref{lem:assoc} ($m$-permutability for $(F,\Eta)$), we have $$B_\Eta\big(F[\O_1],\dots,F[\O_m]\big) =\bar B_\Eta\big(F[\O_1],\dots,F[\O_m]\big)$$ and \begin{multline*} B_\Eta\big( F[\O_1],\dots, F[\O_{k-1}], \eta\big(F[\II]\times F[\JJ]\big), F[\O_{k+1}], \dots, F[\O_m]\big)\\ =\bar B_\Eta\big( F[\O_1],\dots, F[\O_{k-1}], \eta\big(F[\II]\times F[\JJ]\big), F[\O_{k+1}], \dots, F[\O_m]\big), \end{multline*} hence $$ B_\Eta\big(F_\Eta[\O_1],\dots,F_\Eta[\O_m]\big) =\bar B_\Eta\big(F_\Eta[\O_1],\dots,F_\Eta[\O_m]\big),$$ which establishes our claim. \end{proof} \begin{lemma}[\sc Functoriality of $F_\Eta^{(k)}$] \label{lem:kfunct} For each morphism $\ff: \O\rightarrow\widetilde\O$ in ${\bf Set}^r$ and every integer $k\geq0$, we have \[ F[\ff](F_\Eta^{(k)}[\O]) = F_\Eta^{(k)}[\widetilde\O]. \] \end{lemma} \begin{proof} We use induction on $k$, our claim being obvious for $k=0$. Suppose that the assertion holds for $0\leq kFk} and \ref{prop:Disjoint}, and of Theorem~\ref{Thm:MainThm2}} \label{sec:main2} We begin this section with the proof of Proposition~\ref{lem:F->Fk}. With Lemma~\ref{lem:Fkzerl} in hand, we are finally in the position to also establish Proposition~\ref{prop:Disjoint}. Theorem~\ref{Thm:MainThm2} is then a simple consequence of an identity on which the proof of Proposition~\ref{prop:Disjoint} rests (see \eqref{eq:GF-Fetak} 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~\ref{prop:Disjoint}. \begin{proof}[Proof of Proposition~{\em\ref{lem:F->Fk}}] We use induction on $\|\O\|$, where $\|\,.\,\|$ has been defined in \eqref{eq:omabs}. By (\ref{Eq:FetakBoundary}) and the definition of $F_\Eta^{(0)}$, the statement holds if $\|\O\|=0$, that is, if $\O=\pmb{\emptyset}$. Let $\O$ be such that $\|\O\|=N$ for some integer $N>0$, and suppose that (\ref{Eq:FOmegaFilt}) holds for all $\O'\in\Obj(\mathbf{Set}^r)$ of norm strictly less than $N$. Then we have $\O\neq\pmb{\emptyset}$, and therefore \begin{align*} \bigcup_{k\geq0} F_\Eta^{(k)}[\O] &= \bigcup_{k\geq1} F_\Eta^{(k)}[\O]\\[2mm] &= \bigcup_{k\geq1}\hspace{.8mm} \underset{\O_1\subseteq\O}{\bigcup_{\O_1\in\Obj({\bf Set}^r)}} \eta\big(F_\Eta[\O_1] \times F_\Eta^{(k-1)}[\O-\O_1]\big)\\[2mm] &= \underset{\O_1\subseteq\O}{\bigcup_{\O_1\in\Obj({\bf Set}^r)}} \eta\bigg(F_\Eta[\O_1] \times \Big(\bigcup_{k\geq1} F_\Eta^{(k-1)}[\O-\O_1]\Big)\bigg)\\[2mm] &= \underset{\pmb{\emptyset}\neq\O_1\subseteq\O}{\bigcup_{\O_1\in\Obj({\bf Set}^r)}} \eta\bigg(F_\Eta[\O_1] \times \Big(\bigcup_{k\geq0} F_\Eta^{(k)}[\O-\O_1]\Big)\bigg)\\[2mm] &= \underset{\O_1\subseteq\O}{\bigcup_{\O_1\in\Obj({\bf Set}^r)}} \eta\big(F_\Eta[\O_1] \times F[\O-\O_1]\big)\\[2mm] &= F[\O]. \end{align*} Here, we have used Lemma~\ref{lem:Fzerl} for the last equality, and the inductive hypothesis in the second but last step (here it is important that $\O_1\ne\pmb\emptyset$ in order to guarantee that $\|\O-\O_1\|<\|\O\|$). \end{proof} \begin{proof}[Proof of Proposition~{\em\ref{prop:Disjoint}} and of Theorem~{\em\ref{Thm:MainThm2}}] For $k\ge0$, let us define the generating function for $F_\Eta^{(k)}$ by $$ \GF_{F_\Eta^{(k)}}(z_1,\ldots,z_r) := \sum_{n_1,\ldots,n_r\geq0} \sum_{x\in F_\Eta^{(k)}[([n_1],\dots,[n_r])]} w_{([n_1],\dots,[n_r])}(x)\, \frac {z_1^{n_1} \cdots z_r^{n_r}} {n_1!\cdots 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 \begin{equation} \label{eq:GF-Fetak} \GF_{F_\Eta^{(k)}}(z_1,\ldots,z_r) =\frac {1} {k!} \big(\GF_{F_\Eta}(z_1,\ldots,z_r) \big)^k. \end{equation} By definition of $F_\Eta^{(0)}$, the left-hand side of \eqref{eq:GF-Fetak} equals $1$, so that \eqref{eq:GF-Fetak} holds for $k=0$. Therefore, we may in the sequel assume that $k\ge1$. We now proceed in a manner similar to the proof of Theorem~\ref{Thm:MainThm1} given in Section~\ref{sec:main1}. Here, however, we use Lemma~\ref{lem:Fkzerl} instead of Lemmas~\ref{lem:Fzerl} and \ref{lem:Fdisj}, and we also need the functoriality of $F_\Eta^{(m)}$ for $m=0,1,2,\dots$ established in Lemma~\ref{lem:kfunct}. In this way, we obtain from \eqref{Eq:FEtaKDec} the identity \begin{multline} \label{Eq:psiFEtaEval} n_\rho\cdot w\big(F_\Eta^{(k)}[([n_1],\ldots, [n_r])]\big) = {\sum_{0\leq\mu_i\leq n_i\,(1\leq i\leq r)}}\, \mu_\rho \bigg(\prod_{1\leq i\leq r} \binom{n_i}{\mu_i}\bigg) w\big(F_\Eta[([\mu_1],\ldots, [\mu_r])]\big)\\ \kern7cm \cdot w\big(F_\Eta^{(k-1)} [([n_1-\mu_1] ,\ldots, [n_r-\mu_r])]\big). \end{multline} Fixing $\rho\in[r]$, multiplying both sides of (\ref{Eq:psiFEtaEval}) by \[ {z_1^{n_1} \cdots z_{\rho-1}^{n_{\rho-1}} z_\rho^{n_\rho-1}z_{\rho+1}^{n_{\rho+1}} \cdots z_r^{n_r}} / {(n_1! \cdots n_r!)}, \] and summing over all tuples $(n_1, \ldots,n_r)\in\N_0^r$, gives \begin{multline} \label{Eq:PsiFEtaEval1} {\sum_{n_1,\ldots,n_r\geq0}}\, w\big(F_\Eta^{(k)}[([n_1],\ldots,[n_r])]\big)\,\frac { z_1^{n_1} \cdots z_{\rho-1}^{n_{\rho-1}} z_\rho^{n_\rho-1}z_{\rho+1}^{n_{\rho+1}} \cdots z_r^{n_r}} {n_1! \cdots n_{\rho-1}!\, (n_\rho-1)!\,n_{\rho+1}! \cdots n_r!}\\ \kern-4cm = {\sum_{n_1,\ldots,n_r\geq0}}\ {\sum_{0\leq\mu_i\leq n_i\,(1\leq i\leq r)}}\, \frac{w\big(F_\Eta[([\mu_1],\ldots,[\mu_r])]\big)} {\mu_1! \cdots \mu_{\rho-1}!\, (\mu_\rho-1)!\, \mu_{\rho+1}!\cdots \mu_r!}\\ \cdot\frac{w\big(F_\Eta^{(k-1)}[([n_1-\mu_1], \ldots,[n_r-\mu_r])]\big)}{(n_1-\mu_1)! \cdots (n_r-\mu_r)!}\, z_1^{n_1} \cdots z_{\rho-1}^{n_{\rho-1}} z_\rho^{n_\rho-1}z_{\rho+1}^{n_{\rho+1}} \cdots z_r^{n_r}, \end{multline} where, again, $1/(-1)!$ has to be interpreted as $0$. The left-hand side equals \[ \frac{\partial \GF_{F_\Eta^{(k)}}}{\partial z_\rho}, \] while the right-hand side is identified as \[ \frac{\partial \GF_{F_\Eta}}{\partial z_\rho} \GF_{F_\Eta^{(k-1)}}, \] whence the equations \begin{equation} \label{eq:Fetadiff} \frac{\partial \GF_{F_\Eta^{(k)}}}{\partial z_\rho} = \frac{\partial \GF_{F_\Eta}}{\partial z_\rho} \GF_{F_\Eta^{(k-1)}}, \quad \quad 1\le \rho\le r. \end{equation} Assuming inductively that $$\GF_{F_\Eta^{(k-1)}}=\frac {1} {(k-1)!} \big(\GF_{F_\Eta}\big)^{k-1},$$ we infer from \eqref{eq:Fetadiff} that $$ \GF_{F_\Eta^{(k)}}=\frac {1} {k!}\big(\GF_{F_\Eta}\big)^{k}+ C, $$ where $C$ is independent of $z_1,z_2,\dots,z_r$. Making use of the facts that $\GF_{F_\Eta^{(k)}}(0,\ldots,0) = 0$ (since $k\ge1$) and that $\GF_{F_\Eta}(0,\ldots,0) = 0$, we see that $C=0$, which proves \eqref{eq:GF-Fetak}. On the other hand, by Theorem~\ref{Thm:MainThm1}, we know that $$\GF_F(z_1,z_2,\dots,z_r)=\exp\big(\GF_{F_\Eta}(z_1,z_2,\dots,z_r)\big),$$ or, equivalently, \begin{equation} \label{eq:GF-F-Fk} \GF_F(z_1,z_2,\dots,z_r)= \sum _{k\ge0} ^{}\frac {1} {k!} \big(\GF_{F_\Eta}(z_1,z_2,\dots,z_r)\big)^{k}. \end{equation} If there were a non-empty intersection between $F_\Eta^{(k_1)}[\O]$ and $F_\Eta^{(k_2)}[\O]$, for some $k_1,k_2$ with $k_1Fk} would contradict \eqref{eq:GF-F-Fk} and \eqref{eq:GF-Fetak}. This proves the assertion of Proposition~\ref{prop:Disjoint}. \medskip The proof of Theorem~{\ref{Thm:MainThm2}} is now easily completed. By definition of $\widetilde \GF_{F}(z_1,\ldots,z_r,y)$, we have $$ \widetilde \GF_{F}(z_1,\ldots,z_r,y)= \sum _{k\ge0} ^{}y^k\GF_{F_\Eta^{(k)}}(z_1,\ldots,z_r).$$ If we now substitute \eqref{eq:GF-Fetak}, then we immediately obtain \eqref{Eq:MainThm21}. Identity~\eqref{Eq:MainThm22} results from using Theorem~\ref{Thm:MainThm1} to express $\GF_{F_\Eta}(z_1,\ldots,z_r)$ in terms of $\GF_{F}(z_1,\ldots,z_r)$ and substituting the result in \eqref{Eq:MainThm21}. \end{proof} \section{Illustrations, I: Three examples} \label{sec:illust} We give here three illustrations for the application of our theory. In the first and second example below, bipartite graphs are considered. Example~\ref{ex:1} is, in some sense, ``standard," since it addresses the case where the composition operator $\Eta$ 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~\ref{ex:2}, however, the composition operator $\Eta$ is different, ``non-standard," so that classical species theory does not apply, but our (extension of species) theory does. On the other hand, we shall see in Section~\ref{sec:commeta} that this composition operator is pointwise associative and commutative (for the precise definition see \eqref{eq:passoc} and \eqref{eq:pcomm}), and that this is equivalent to the fact that this case is also covered by Menni's theory in \cite{MennAA}. As a consequence, this family of composition operators is closely related to the classical operation of ``putting objects together." (See Theorem~\ref{thm:commeta} for the precise statement.) Our last example in this section, Example~\ref{ex: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 \cite{MennAA}. A particular aspect demonstrated by Examples~\ref{ex:1} and \ref{ex:2} that we want to highlight is that composition operators need not be unique. \begin{example}[\sc Bipartite graphs I] \label{ex:1} Let the $2$-sort species $F: {\bf Set}^2\rightarrow{\bf Set}$ be defined by $$F[\O]=F[(\Omega^{(1)},\Omega^{(2)})]:= 2^{\Omega^{(1)}\times \Omega^{(2)}},\quad \O=(\Omega^{(1)},\Omega^{(2)})\in\Obj(\mathbf{Set}^2).$$ Thus, $F[(\Omega^{(1)},\Omega^{(2)})]$ can be considered as set of all bipartite graphs, where the set of ``white" vertices is $\Omega^{(1)}$ and the set of ``black" vertices is $\Omega^{(2)}$. For $(\O_1,\O_2)\in\Obj(\mathfrak D_2)$, $b_1\in F[\O_1]$ and $b_2\in F[\O_2]$, put $$\eta_{(\O_1,\O_2)}\big((b_1,b_2)\big):=b_1\amalg b_2.$$ This means that $\eta_{(\O_1,\O_2)}$ merely forms the disjoint union of the bipartite graphs $b_1$ and $b_2$. Then it is not difficult to see that $\Eta$ is a natural transformation satisfying (D1). Moreover, $F_\Eta[\O]$ consists of the {\it connected\/} bipartite graphs with bipartition $\O=(\Omega^{(1)},\Omega^{(2)})$. For a weight, we choose $\Lambda=\mathbb Z[t]$ and $$w_\O(b):=t^{|b|},\quad b\in F[\O].$$ Again, it is not difficult to see that $\ww$ satisfies Axioms~(W0)--(W2); that is, $\ww$ is a $\Lambda$-weight on $(F,\Eta)$. Theorem~\ref{Thm:MainThm1} then says that \begin{equation} \label{eq:bip1} \GF_F(z_1,z_2) = \exp\big(\GF_{F_\Eta}(z_1,z_2)\big), \end{equation} where $$ \GF_F(z_1,z_2) = \sum_{n_1,n_2\geq0}\ \sum_{b\in F[([n_1],[n_2])]}\, t^{|b|} \frac { z_1^{n_1}z_2^{n_2}} {n_1!\, n_2!} $$ and $$ \GF_{F_\Eta}(z_1,z_2) = \sum_{n_1,n_2\geq0}\ \sum_{b\in F_\Eta[([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) = \sum_{n_1,n_2\geq0} (1+t)^{n_1n_2} \frac { z_1^{n_1}z_2^{n_2}} {n_1!\, n_2!}. $$ From \eqref{eq:bip1}, it then follows that the generating function for connected bipartite graphs is given by $$ \GF_{F_\Eta}(z_1,z_2) = \log\left(\sum_{n_1,n_2\geq0} (1+t)^{n_1n_2} \frac { z_1^{n_1}z_2^{n_2}} {n_1!\, n_2!}\right), $$ while \eqref{Eq:MainThm22} implies that \begin{align} \notag \widetilde\GF_{F}(z_1,z_2) &:= \sum_{n_1,n_2\geq0}\ \sum_{b\in F[([n_1],[n_2])]}\, t^{|b|}y^{\#(\text{connected components of }b)} \frac { z_1^{n_1}z_2^{n_2}} {n_1!\, n_2!}\\ \label{eq:bip2} &= \left(\sum_{n_1,n_2\geq0} (1+t)^{n_1n_2} \frac { z_1^{n_1}z_2^{n_2}} {n_1!\, n_2!}\right)^y. \end{align} This example can be considered as a $2$-dimensional analogue of the example in \cite[Sec.~3]{DM} (with the first of the two composition operators considered there). The knowledgeable reader will recognise \eqref{eq:bip2} as the exponential generating function for the Tutte polynomials of complete bipartite graphs (cf.\ e.g.\ \cite[Eq.~(3.10)]{ScSoAA}). \end{example} \begin{example}[\sc Bipartite graphs II] \label{ex:2} Let $F: {\bf Set}^2\rightarrow{\bf Set}$ be as in Example~\ref{ex:1}. Here, for $(\O_1,\O_2)\in\Obj(\mathfrak D_2)$, where $\O_i=(\Omega_i^{(1)},\Omega_i^{(2)})$, $i=1,2$, for $b_1\in F[\O_1]$ and $b_2\in F[\O_2]$, we put $$\eta'_{(\O_1,\O_2)}\big((b_1,b_2)\big):=b_1\amalg b_2\amalg \left(\Omega_1^{(1)}\times \Omega_2^{(2)}\right)\amalg \left(\Omega_1^{(2)}\times \Omega_2^{(1)}\right).$$ The graph $\eta'_{(\O_1,\O_2)}\big((b_1,b_2)\big)$ 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 $\Eta'$ is a natural transformation satisfying (D1). Moreover, $F_{\Eta'}(\O)$ consists of the {\it complements\/} of connected bipartite graphs with bipartition $\O=(\Omega^{(1)},\Omega^{(2)})$, where the complement $b^c$ of a bipartite graph $b\in F[\O]$ is defined as $b^c:=\big(\Omega^{(1)}\times \Omega^{(2)}\big)-b$. If we now were to choose the weight of Example~\ref{ex:1}, then Axiom~(W2) would be violated. Instead, with $\Lambda=\mathbb Z[t]$, we set $$w'_\O(b):=t^{|\Omega^{(1)}|\cdot |\Omega^{(2)}|-|b|},\quad b\in F[\O]=F\big[(\Omega^{(1)},\Omega^{(2)})\big].$$ Then it is not difficult to see that $\ww'$ does satisfy Axioms~(W0)--(W2); that is, $\ww'$ is a $\Lambda$-weight on $(F,\Eta')$. Theorem~\ref{Thm:MainThm1} then says that \begin{equation} \label{eq:bip3} \GF_F(z_1,z_2) = \exp\big(\GF_{F_{\Eta'}}(z_1,z_2)\big), \end{equation} where $$ \GF_F(z_1,z_2) = \sum_{n_1,n_2\geq0}\ \sum_{b\in F[([n_1],[n_2])]}\, t^{n_1n_2-|b|} \frac { z_1^{n_1}z_2^{n_2}} {n_1!\, n_2!} $$ and $$ \GF_{F_{\Eta'}}(z_1,z_2) = \sum_{n_1,n_2\geq0}\ \sum_{b\in F_{\Eta'}([n_1],[n_2])}\, t^{n_1n_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) = \sum_{n_1,n_2\geq0} (1+t)^{n_1n_2} \frac { z_1^{n_1}z_2^{n_2}} {n_1!\, n_2!}, $$ and we obtain the formulae $$ \GF_{F_{\Eta'}}(z_1,z_2) = \log\left(\sum_{n_1,n_2\geq0} (1+t)^{n_1n_2} \frac { z_1^{n_1}z_2^{n_2}} {n_1!\, n_2!}\right) $$ and \begin{align} \notag \widetilde\GF_{F}(z_1,z_2) &:= \sum_{n_1,n_2\geq0}\ \sum_{b\in F[([n_1],[n_2])]}\, t^{n_1n_2-|b|} y^{\#(\text{connected components of }b^c)} \frac { z_1^{n_1}z_2^{n_2}} {n_1!\, n_2!}\\ \label{eq:bip4} &= \left(\sum_{n_1,n_2\geq0} (1+t)^{n_1n_2} \frac { z_1^{n_1}z_2^{n_2}} {n_1!\, n_2!}\right)^y. \end{align} This example can be viewed as a $2$-dimensional analogue of the example in \cite[Sec.~3]{DM} (with the second of the two composition operators considered there). The alert reader will have noticed that the $\Eta'$-maps could have been alternatively defined by \begin{equation} \label{eq:eta'c} \eta'_{(\O_1,\O_2)}\big((b_1,b_2)\big):=\big(b_1^c\amalg b_2^c\big)^c, \end{equation} where the complements have to be taken in the appropriate complete bipartite graphs. This construction will be generalised in Section~\ref{sec:commeta}. \end{example} \begin{example}[\sc Binary functions] \label{ex:3} Let the ($1$-sort) species $F: {\bf Set}\rightarrow{\bf Set}$ be defined by $$F[\O]:= \{0,1\}^{\O},\quad \O\in\Obj(\mathbf{Set}).$$ For $(\O_1,\O_2)\in\Obj(\mathfrak D_1)$, $f_1\in F[\O_1]$, and $f_2\in F[\O_2]$, put $$\big(\eta_{(\O_1,\O_2)} \big((f_1,f_2)\big)\big)(\omega):=\begin{cases} f_1(\omega),&\text{if }\omega\in\O_1,\\ 1-f_2(\omega),&\text{if }\omega\in\O_2. \end{cases}$$ Then it is easy to see that $\Eta$ is a natural transformation satisfying (D1). Moreover, $$F_\Eta[\O]=\begin{cases} \{0_\O,1_\O\},&\text{if }|\O|=1,\\ \{\},&\text{otherwise,}\end{cases}$$ where $0_\O$ and $1_\O$ are the constant functions on $\O$ taking the value $0$ and $1$, respectively. We note that, in contrast to Examples~\ref{ex:1} and \ref{ex:2}, the $\Eta$-maps of the present example are {\it pointwise non-associative and non-commutative} (cf.\ Section~\ref{sec:commeta}); to be precise, in general we have $$ \eta_{(\O_1\amalg\O_2,\O_3)} \Big(\big(\eta_{(\O_1,\O_2)}\big((f_1,f_2)\big),f_3\big)\Big)\ne \eta_{(\O_1,\O_2\amalg\O_3)} \Big(\big(f_1,\eta_{(\O_2,\O_3)}\big((f_2,f_3)\big)\big)\Big) $$ and $$ \eta_{(\O_1,\O_2)}\big((f_1,f_2)\big)\ne \eta_{(\O_2,\O_1)}\big((f_2,f_1)\big). $$ For the sake of completeness, we remark that, choosing the trivial weighting $$w_\O(f):=1,\quad f\in F[\O],$$ Theorem~\ref{Thm:MainThm1} yields the trivial identity \begin{equation*} \GF_F(z) = \sum _{n\ge0} ^{}2^n\frac {z^n} {n!} =\exp\big(\GF_{F_\Eta}(z)\big)=\exp(2z). \end{equation*} 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~\ref{thm:Etwist} in Section~\ref{sec:commeta}. \end{example} \section{Illustrations, II: Magic squares} \label{Sec:CMT1} 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 {\em combinatorial matrix} on $\O=(\Omega^{(1)},\Omega^{(2)})\in\Obj({\bf Set}^2)$ we shall mean any map \[ m: \Omega^{(1)}\times\Omega^{(2)}\rightarrow\N_0. \] The pair of sets $\O$ is called the {\em support} of $m$. Let $m_1, m_2$ be two combinatorial matrices with supports $\O_1=(\Omega_1^{(1)},\Omega_1^{(2)})$ and $\O_2=(\Omega_2^{(1)},\Omega_2^{(2)})$, respectively, and suppose that $\O_1\cap\O_2=\pmb{\emptyset}$. Then we define their {\em direct sum} $m=m_1\oplus m_2$ to be the combinatorial matrix with support $\O:=\O_1\amalg\O_2$ given by \[ m(\omega_1,\omega_2):=\begin{cases} m_1(\omega_1,\omega_2),&(\omega_1,\omega_2) \in\Omega_1^{(1)}\times\Omega_1^{(2)},\\ m_2(\omega_1,\omega_2),&(\omega_1,\omega_2) \in\Omega_2^{(1)}\times\Omega_2^{(2)},\\ 0,&\mbox{otherwise}. \end{cases} \] A combinatorial matrix $m$ on $\O$ is termed $s$-{\em magic},\footnote{Strictly 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.\ \cite{BCCGAA}. However, we prefer the term ``$s$-magic" for the sake of brevity.} $s$ a positive integer, if \[ \sum_{\omega_2\in\Omega^{(2)}} m(\omega_1,\omega_2) = s,\quad\omega_1\in\Omega^{(1)}, \] and \[ \sum_{\omega_1\in\Omega^{(1)}} m(\omega_1,\omega_2) =s,\quad\omega_2\in\Omega^{(2)}. \] Computing the sum of entries, we find that an $s$-magic matrix is necessarily square, $|\Omega^{(1)}|=|\Omega^{(2)}|$. The enumeration of $s$-magic squares has a long history, going back to MacMahon \cite[\S404--419]{MacMAA}. A good account of the enumerative theory of magic squares can be found in \cite[Sec.~4.6]{StanAP}, with many pointers to further literature. For more recent work, see for instance \cite{BCCGAA,LoLYAA}. For $s\in\N$ and $\O\in \Obj({\bf Set}^2)$, denote by $F_s(\O)$ the set of all $s$-magic matrices on $\O$, and by $\bar{F}_s(\O)$ the set of those $s$-magic matrices on $\O$ which do not contain $s$ as an entry. We thus have mappings \[ F_s, \bar{F}_s: \Obj({\bf Set}^2) \rightarrow \Obj({\bf Set}), \] which we turn into functors $F_s, \bar{F}_s: {\bf Set}^2\rightarrow{\bf Set}$ by assigning to a morphism \[ \ff = (f_1,f_2): \O\rightarrow\widetilde\O \] in ${\bf Set}^2$ the map (denoted $F_s[\ff]$ respectively $\bar{F}_s[\ff]$) sending a combinatorial matrix $m$ in the respective domain to $m\circ(f_1^{-1}\times f_2^{-1})$. Moreover, given $s$ and a finite set $\Omega$, let $F^\ast_s(\Omega)$ be the set of {\em symmetric} $s$-magic matrices on $\O=(\Omega,\Omega)$; that is, combinatorial matrices satisfying \[ m(\omega_1,\omega_2) = m(\omega_2,\omega_1),\quad (\omega_1,\omega_2)\in\Omega^2; \] and denote by $\bar{F}^\ast_s(\Omega)$ the subset of $F^\ast_s(\Omega)$ consisting of those matrices with no entry equal to $s$. Just as above, the maps \[ F_s^\ast, \bar{F}_s^\ast: \Obj({\bf Set})\rightarrow \Obj({\bf Set}) \] become functors $F_s^\ast, \bar{F}_s^\ast: {\bf Set}\rightarrow{\bf Set}$ by assigning to a morphism $f:\Omega\rightarrow\widetilde\Omega$ in ${\bf Set}$ the map sending a combinatorial matrix $m$ in the respective domain to $m\circ(f^{-1}\times f^{-1})$. Next, given $s\in\N$, a pair $(\O_1,\O_2)\in\Obj(\mathfrak{D}_2)$, and a pair $(\Omega_1,\Omega_2)\in\Obj(\mathfrak{D}_1)$, the direct sum construction provides us with injective maps \begin{align*} (\eta_{s})_{(\O_1,\O_2)}&: F_s(\O_1) \times F_s(\O_2) \rightarrow F_s(\O_1\amalg \O_2),\\ (\bar{\eta}_s)_{(\O_1,\O_2)}&: \bar{F}_s(\O_1) \times \bar{F}_s(\O_2) \rightarrow \bar{F}_s(\O_1\amalg \O_2),\\ ({\eta}_{s}^\ast)_{(\Omega_1,\Omega_2)}&: F^\ast_s(\Omega_1) \times F^\ast_s(\Omega_2) \rightarrow F^\ast_s(\Omega_1\amalg \Omega_2),\\ {(\bar{\eta}}_{s}^\ast)_{(\Omega_1,\Omega_2)}&: \bar{F}_s^\ast(\Omega_1)\times \bar{F}_s^\ast(\Omega_2)\rightarrow\bar{F}_s^\ast(\Omega_1\amalg\Omega_2). \end{align*} A certain amount of checking is required in order to convince oneself that these definitions fit into the framework of Theorems~\ref{Thm:MainThm1} and \ref{Thm:MainThm2}. The next lemma states the corresponding result. We leave its proof, which essentially amounts to a routine verification, to the reader. \begin{lemma} \label{Lem:CombMat} \begin{itemize} \item[(i)] For each $s \in\N,$ the collection of maps \[ \Eta_{s}= \big((\eta_{s})_{(\O_1,\O_2)}\big)_{(\O_1,\O_2)\in\Obj(\mathfrak{D}_2)} \] is a natural transformation from the functor $F_s\times F_s$ to the functor $F_s\circ\amalg$. Analogous statements hold for the functors $\bar{F}_s, F_s^\ast, \bar{F}_s^\ast,$ and the families of maps \begin{align*} \bar{\Eta}_{s} &= \big((\bar{\eta}_{s})_{(\O_1,\O_2)}\big) _{(\O_1,\O_2)\in\Obj(\mathfrak{D}_2)},\\ {\Eta}_{s}^\ast &= \big(({\eta}_{s}^\ast) _{(\Omega_1,\Omega_2)}\big)_{(\Omega_1,\Omega_2)\in\Obj(\mathfrak{D}_1)},\\ {\bar{\Eta}}_{s}^\ast &= \big(({\bar{\eta}}_{s}^\ast) _{(\Omega_1,\Omega_2)}\big)_{(\Omega_1,\Omega_2)\in\Obj(\mathfrak{D}_1)}. \end{align*} \item[(ii)] For each $s,$ the pair $(F_s,\Eta_{s})$ satisfies Axiom~{\em (D1),} an analogous statement holding for each of the other pairs $(\bar{F}_s,\bar{\Eta}_{s}),$ $(F_s^\ast,{\Eta}_{s}^\ast),$ and $(\bar{F}^\ast_s,{\bar{\Eta}}_{s}^\ast)$. \end{itemize} \end{lemma} %\begin{proof} %We shall prove (i) and (ii) for the pair $(F_s,\Eta_{s})$. The %proof in the other cases presents nothing new. % %(i) We have to show that, for each morphism %\[ %\ff: (\O_1,\O_2)\rightarrow %(\widetilde{\O}_1,\widetilde{\O}_2) %\] %of $\mathfrak{D}_2$, diagram (\ref{Eq:NatDiag}), with $F$ and %$\eta$ replaced by $F_s$ respectively $\eta^{(s)}$, commutes. %Indeed, let $\ff=(\ff_1,\ff_2)$ and %$f_j=(f_j^{(1)},f_j^{(2)})$ with bijections $f_j^{(i)}: %\Omega_j^{(i)}\rightarrow\widetilde{\Omega}_j^{(i)}$ for %$i,j\in[2]$. Then a pair $(m_1,m_2)$ of $s$-magic matrices with %supports $\O_1$ respectively $\O_2$ is mapped under %$((F_s\circ\amalg)(\ff))\circ\eta^{(s)}_{(\O_1,\O_2)}$ %to the $s$-magic matrix %\[ %\tilde{m} = (m_1\oplus m_2)\circ((f_1^{(1)}\oplus f_2^{(1)})^{-1} %\times (f_1^{(2)} \oplus f_2^{(2)})^{-1}) %\] %on $\widetilde{\O}_1\amalg\widetilde{\O}_2$, whose entries are %given explicitly by %\[ %\tilde{m}(\tilde{\omega}_1,\tilde{\omega}_2) =\begin{cases} % %m_1((f_1^{(1)})^{-1}(\tilde{\omega}_1),(f_1^{(2)})^{-1}(\tilde{\omega}_2)),& % (\tilde{\omega}_1,\tilde{\omega}_2)\in\widetilde{\Omega}_1^{(1)} % \times\widetilde{\Omega}_1^{(2)}\\ % %m_2((f_2^{(1)})^{-1}(\tilde{\omega}_1),(f_2^{(2)})^{-1}(\tilde{\omega}_2)),& % (\tilde{\omega}_1,\tilde{\omega}_2)\in\widetilde{\Omega}_2^{(1)} % \times\widetilde{\Omega}_2^{(2)}\\ % 0,&\mbox{otherwise} % \end{cases}. %\] %On the other hand, the pair $(m_1,m_2)$ is mapped under %$\eta^{(s)}_{(\widetilde{\O}_1,\widetilde{\O}_2)} \circ (F_s\times %F_s)(\ff)$ to the $s$-magic matrix %\[ %\tilde{\tilde{m}} = \big(m_1\circ(f_1^{(1)}\times %f_1^{(2)})^{-1}\big) \oplus \big(m_2 \circ (f_2^{(1)}\times %f_2^{(2)})^{-1}\big), %\] %whose entries are seen to be the same as those of $\tilde{m}$. % %(ii) Let $m$ be an $s$-magic matrix on %$\O=(\Omega^{(1)},\Omega^{(2)})$, and let %\[ %\O_1\amalg\O_2 = \O = \widetilde{\O}_1\amalg\widetilde{\O}_2 %\] %be two partitions of $\O$. Set %$\O_i=(\Omega_i^{(1)},\Omega_i^{(2)})$ and %$\widetilde{\O}_j=(\widetilde{\Omega}_j^{(1)},\widetilde{\Omega}_j^{(2)})$. %We have to show that %\begin{equation} %\label{Eq:D1Ass1} m\in\eta^{(s)}\big(F_s(\O_1)\times %F_s(\O_2)\big)\cap \eta^{(s)}\big(F_s(\widetilde{\O}_1)\times %F_s(\widetilde{\O}_2)\big) %\end{equation} %if and only if %\begin{equation} %\label{Eq:D1Ass2} %m\in\eta^{(s)}\big(\eta^{(s)}\big(F_s(\O_{11})\times %F_s(\O_{12})\big)\times\eta^{(s)} \big(F_s(\O_{21})\times %F_s(\O_{22})\big)\big), %\end{equation} %where $\O_{ij}=\O_i\cap\widetilde{\O}_j$. Consider %$(\omega_1,\omega_2)\in(\Omega^{(1)},\Omega^{(2)})$. Condition %(\ref{Eq:D1Ass1}) is equivalent to the conjunction of the two %assertions %\[ %(\omega_1,\omega_2)\not\in(\Omega_1^{(1)}\times\Omega_1^{(2)})\cup %(\Omega_2^{(1)}\times\Omega_2^{(2)}) \Longrightarrow %m(\omega_1,\omega_2)=0 %\] %and %\[ %(\omega_1,\omega_2)\not\in(\widetilde{\Omega}_1^{(1)} %\times\widetilde{\Omega}_1^{(2)})\cup %(\widetilde{\Omega}_2^{(1)}\times\widetilde{\Omega}_2^{(2)}) %\Longrightarrow m(\omega_1,\omega_2)=0, %\] %while (\ref{Eq:D1Ass2}) is equivalent to the assertion that %\[ %(\omega_1,\omega_2)\not\in \bigcup_{i,j\in[2]}\big((\Omega_i^{(1)} %\cap\widetilde{\Omega}_j^{(1)}) %\times(\Omega_i^{(2)}\cap\widetilde{\Omega}_j^{(2)})\big) %\Longrightarrow m(\omega_1,\omega_2)=0. %\] %$(\ref{Eq:D1Ass1})\Rightarrow(\ref{Eq:D1Ass2})$. Suppose that %$\omega_1\in\Omega^{(1)}_{i_0}\cap\widetilde{\Omega}_{j_0}^{(1)}$, %and that %\[ %(\omega_1,\omega_2)\not\in \bigcup_{i,j\in[2]}\big((\Omega_i^{(1)} %\cap\widetilde{\Omega}_j^{(1)}) %\times(\Omega_i^{(2)}\cap\widetilde{\Omega}_j^{(2)})\big). %\] %Then $\omega_2 %\not\in\Omega_{i_0}^{(2)}\cap\widetilde{\Omega}_{j_0}^{(2)}$; that %is, $\omega_2\not\in\Omega_{i_0}^{(2)}$ or %$\omega_2\not\in\widetilde{\Omega}_{j_0}^{(2)}$. In the first %case, we have %\[ %(\omega_1,\omega_2)\not\in(\Omega_1^{(1)}\times\Omega_1^{(2)})\cup %(\Omega_2^{(1)}\times\Omega_2^{(2)}), %\] %while in the second case %\[ %(\omega_1,\omega_2) %\not\in(\widetilde{\Omega}_1^{(1)}\times\widetilde{\Omega}_1^{(2)})\cup %(\widetilde{\Omega}_2^{(1)}\times\widetilde{\Omega}_2^{(2)}). %\] %In both cases, the desired conclusion $m(\omega_1,\omega_2)=0$ %follows from (\ref{Eq:D1Ass1}). % %$(\ref{Eq:D1Ass2})\Rightarrow(\ref{Eq:D1Ass1})$. Suppose that %$\omega_1\in\Omega^{(1)}_{i_0}\cap\widetilde{\Omega}_{j_0}^{(1)}$, %and that %\[ %(\omega_1,\omega_2)\not\in(\Omega_1^{(1)}\times\Omega_1^{(2)})\cup %(\Omega_2^{(1)}\times\Omega_2^{(2)}) %\] %or that %\[ %(\omega_1,\omega_2) %\not\in(\widetilde{\Omega}_1^{(1)}\times\widetilde{\Omega}_1^{(2)})\cup %(\widetilde{\Omega}_2^{(1)}\times\widetilde{\Omega}_2^{(2)}). %\] %In the first case, we have $\omega_2\not\in \Omega_{i_0}^{(2)}$, %while in the second case $\omega_2\not\in %\widetilde{\Omega}_{j_0}^{(2)}$, so %$\omega_2\not\in\Omega_{i_0}^{(2)}\cap\widetilde{\Omega}_{j_0}^{(2)}$ %in any case. From this, we infer that %\[ %(\omega_1,\omega_2)\not\in \bigcup_{i,j\in[2]}\big((\Omega_i^{(1)} %\cap\widetilde{\Omega}_j^{(1)}) %\times(\Omega_i^{(2)}\cap\widetilde{\Omega}_j^{(2)})\big), %\] %and $m(\omega_1,\omega_2)=0$ follows from (\ref{Eq:D1Ass2}). %\end{proof} It follows from Lemma~\ref{Lem:CombMat} and Theorem~\ref{Thm:MainThm2}, that Equations (\ref{Eq:MainThm21}) and (\ref{Eq:MainThm22}) hold for each of the pairs $(F_s,\Eta_{s})$, $(\bar{F}_s,\bar{\Eta}_{s})$, $(F_s^\ast, {\Eta}_{s}^\ast)$, and $(\bar{F}^\ast,{\bar{\Eta}}_{s}^\ast)$; in particular, we find that \begin{align} \widetilde\GF_{F_s}(z_1,z_2,y) &= \exp\big(y \GF_{(F_s)_{\Eta_{s}}}(z_1,z_2)\big),\label{Eq:CombMat1}\\ \widetilde\GF_{\bar{F}_s}(z_1,z_2,y) &= \exp\big(y \GF_{(\bar{F}_s)_{\bar\Eta_{s}}}(z_1,z_2)\big),\label{Eq:CombMat2}\\ \widetilde\GF_{F_s^\ast}(z,y) &= \exp\big(y \GF_{(F_s^\ast)_{{\Eta}_{s}^\ast}}(z)\big),\label{Eq:CombMat3}\\ \widetilde\GF_{\bar{F}^\ast_s}(z,y) &= \exp\big(y\GF_{(\bar{F}^\ast_s)_{ {\bar{\Eta}}_{s}^\ast}}(z)\big)\label{Eq:CombMat4}. \end{align} 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 \eqref{Eq:CombMat1} and \eqref{Eq:CombMat2} can be viewed as formal power series in $z_1z_2$ and $y$; that is, $z_1z_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 $\widetilde\GF_{F_s}$, $\widetilde\GF_{\bar{F}_s}$, $\widetilde\GF_{F_s^\ast}$, $\widetilde\GF_{\bar{F}^\ast_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 \begin{equation*} \big|(F_s)_{\Eta_{s}}([n_1],[n_2])\big| = \begin{cases} 1+\big|(\bar{F}_s)_{\bar{\Eta}_{s}}([1],[1])\big|,& n_1=n_2=1,\\[2mm] \big|(\bar{F}_s)_{\bar{\Eta}_{s}}([n_1],[n_2])\big|,&\mbox{otherwise}, \end{cases} \end{equation*} and hence, by Equations~(\ref{Eq:CombMat1}) and (\ref{Eq:CombMat2}), \begin{equation} \label{Eq:CombMat5} \widetilde\GF_{\bar{F}_s}(z_1,z_2,y) =e^{-z_1z_2y}\,\widetilde\GF_{F_s}(z_1,z_2,y). \end{equation} Similarly, we have \begin{equation} \label{Eq:CombMat6} \widetilde\GF_{\bar{F}_s^\ast}(z,y) = e^{-y(z+z^2/2)} \widetilde\GF_{F_s^\ast}(z,y). \end{equation} Indeed, for $n=1,2$, there exist indecomposable symmetric $s$-magic matrices on $([n],[n])$ containing an entry $s$: \[ (s)\, \text{ and }\, \left(\begin{matrix}0&s\\s&0\end{matrix}\right). \] Now let $m$ be a symmetric $s$-magic matrix on $([n],[n])$ with $n\geq3$, and suppose that $m$ contains an entry equal to $s$ in position $(i,j)$. Then, if $i=j$, we have $m=(s)\oplus m^\prime$, where $m^\prime$ has support $([n]-\{i\},[n]-\{i\})$. If, on the other hand, $i\neq j$, then, by symmetry, $m$ also contains $s$ in position $(j,i)$, and we find that $m$ splits as \[ m=\left(\begin{matrix}0&s\\s&0\end{matrix}\right)\oplus m^\prime, \] where $m^\prime$ has support $([n]-\{i,j\},[n]-\{i,j\})$, and is non-empty since $n\geq3$. Thus, in both cases, $m$ is in fact decomposable. Hence, \begin{equation*} \big|(F_s^\ast)_{{\Eta}_{s}^\ast}([n])\big| = \begin{cases} 1 + \big|(\bar{F}^\ast_s)_{{\bar{\Eta}}_{s}^\ast}([n])\big|,&n=1,2,\\[2mm] \big|(\bar{F}^\ast_s)_{{\bar{\Eta}}_{s}^\ast}([n])\big|, &\text{otherwise,} \end{cases} \end{equation*} and (\ref{Eq:CombMat6}) follows from Equations~(\ref{Eq:CombMat3}) and (\ref{Eq:CombMat4}). The enumeration can be done exactly if $s=2$. For, according to Birkhoff's Theorem (cf.\ \cite{Birkhoff} or \cite[Corollary~8.40]{Aig}), 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 \[\big|(F_2)_{\Eta_{2}}([n_1],[n_2])\big| = \begin{cases} 1, & n_1=n_2=n=1,\\ \frac{n!(n-1)!}{2}, & n_1=n_2=n>1,\\ 0, & n_1\neq n_2, \end{cases} \] that is, \[ \GF_{(F_2)_{\Eta_{2}}}(z_1,z_2) = \frac{1}{2}z_1z_2 - \frac{1}{2}\log(1-z_1z_2), \] and therefore \begin{equation} \label{Eq:CombMat7} \widetilde\GF_{F_2}(z_1,z_2,y) = (1-z_1z_2)^{-y/2}\,e^{z_1z_2y/2} \end{equation} by Equation~(\ref{Eq:CombMat1}). Also, \begin{equation} \label{Eq:CombMat8} \widetilde\GF_{\bar{F}_2}(z_1,z_2,y) = (1 - z_1z_2)^{-y/2}\,e^{-z_1z_2y/2}, \end{equation} making use of Equation~(\ref{Eq:CombMat5}) and the last result. Special cases of Identities~\eqref{Eq:CombMat7} and \eqref{Eq:CombMat8} appear in \cite[Sections~8.1 and 8.3]{ADG} (see also \cite[Eqs.~(23) and (24) in Example~6.11]{Stan2}). For $s>2$, enumeration is more difficult; see Stanley's paper \cite{Stan1} and Comtet \cite[pp.~124--125]{Comtet} for comments in this direction; also Goulden and Jackson~\cite[Sections~3.4 and 3.5]{GJ} for some variations on this counting problem.\footnote{Note however, that the formula given in \cite{Comtet} for $s=3$ is erroneous.} 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\leq2$, we obtain \[ \GF_{(F_2^\ast)_{{\Eta}_{2}^\ast}}(z) = \frac {z^2} {4}+\frac{z}{2(1-z)}-\frac {1} {2}\log(1-z), \] and, hence \begin{equation} \label{Eq:CombMat9} \widetilde\GF_{F^*_2}(z,y) = (1-z)^{-y/2}\,\exp\Big(\frac {yz^2} {4}+\frac{y z}{2(1-z)}\Big), \end{equation} as well as \begin{equation} \label{Eq:CombMat10} \widetilde\GF_{\bar{F}_2^\ast}(z,y) = (1-z)^{-y/2}\,\exp\Big(-\frac {yz^2} {4}-yz+\frac{yz}{2(1-z)}\Big). \end{equation} Identity~\eqref{Eq:CombMat9} generalises \cite[Eq.~(6.3)]{Gup}, whereas \eqref{Eq:CombMat10} generalises \cite[Eq.~(6.4)]{Gup}. \section{Simple commutative monoids in species} %Characterisation of %pointwise associative and commutative composition %operators} \label{sec:commeta} In this final section, we address the natural question: {\it`Can one characterise all possible composition operators in $r$-sort species?{}'} In particular: how far can the composition operator $\Eta$ 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~\ref{ex:1} in Section~\ref{sec:illust} 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 \cite{MennAA}. Already Joyal pointed out in \cite[Sec.~7.1]{Joyal} that ($r$-sort) species are endowed with the structure of a {\it symmetric monoidal category}. The main objects in Menni's theory \cite{MennAA} are {\it simple commutative monoids} in an {\it arbitrary} symmetric monoidal category. He defines the notion of a {\it decomposition} as a simple commutative monoid that satisfies a certain pullback condition (see \cite[Def.~2.1]{MennAA}), 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~\ref{Sec:MainThm}. 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 \cite[Prop.~1.4, Ex.~3.2, and Ex.~3.5 with $I=1+1+\dots+1$, the summand $1$ appearing $r$ times in the sum]{MennAA}). He then moves on to characterise decompositions in symmetric monoidal categories (see \cite[Sec.~2.6]{MennAA}). 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~\ref{Sec:MainThm} 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 \eqref{eq:passoc} and \eqref{eq:pcomm}). For the sake of being self-contained, and for including the case of weighted species as well (weights not being addressed in \cite{MennAA}, 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~\ref{thm:Etwist}), generalising Example~\ref{ex:3}, that are {\it 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 \cite{MennAA}, which shows that our axiomatic set-up is wider than Menni's theory in the special case of $r$-sort species. \medskip Let $\Sp_r$ denote the category of $r$-sort species. Given two species $F$ and $G$ in $\Obj(\Sp_r)$ and $\O\in\Obj({\bf Set}^r)$, we define their product $*$ (a special case of the more general concept of Day convolution; cf.~\cite{ImKeAA} and \cite[Sec.~3.1]{MennAC}) by $$ (F* G)[\O]:=\coprod_{\O_1\amalg \O_2=\O}F[\O_1]\times G[\O_2], $$ with the obvious morphisms. In order to discuss monoids in species, we need to introduce the ``unit" species $\mathbf 1$ by $$\mathbf 1[\O]:=\begin{cases} \{1\}&\text {if }\O=\emptyset,\\ \emptyset&\text {if }\O\ne\emptyset. \end{cases}$$ Here, $1$ denotes a ``canonical" element, and the morphisms are the obvious ones. Then the triple $(\Sp_r,*,\mathbf 1)$ forms a {\it symmetric monoidal category} (see \cite[Sec.~7.1]{Joyal}). We refer the reader to \cite{KellAA} (see also \cite{MacLAA}) 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) $$ \alpha=\alpha_{F,G,H}:F* (G* H)\to (F* G)* H $$ given by $$ \alpha:(x,(y,z))\to ((x,y),z),\quad \text {for } x\in F[\O_1],\ y\in G[\O_2],\ z\in H[\O_3],\ $$ where $F,G,H\in\Obj(\Sp_r)$, and where $\O_1,\O_2,\O_3\in \Obj({\bf Set}^r)$ are pairwise disjoint, the natural transformation(s) $$ \beta=\beta_{F,G}:F* G\to G* F $$ given by $$ \beta:(x,y)\to (y,x),\quad \text {for } x\in F[\O_1],\ y\in G[\O_2],\ $$ the natural transformation(s) $$ \lambda=\lambda_{F}:\mathbf 1* F\to F $$ given by $$ \lambda:(1,x)\to x,\quad \text {for } x\in F[\O_1],\ $$ and the natural transformation(s) $$ \rho=\rho_{F}:F* \mathbf 1\to F $$ given by $$ \rho=\rho_F:(x,1)\to x,\quad \text {for } x\in F[\O_1],\ $$ so that --- roughly speaking --- all association and commutation laws that one may think of are satisfied. A {\it monoid\/} in the symmetric monoidal category $\Sp_r$ is by definition a triple $(F,*,\mathbf 1)$, where $F\in\Obj(\Sp_r)$, such that there are natural transformations $\mu:F* F\to F$ and $\nu:\mathbf 1\to F$ such that the diagrams \begin{equation} \label{diag:1} \begin{diagram} F*(F* F)&\rTo^{\hbox{$\kern10pt \alpha\kern10pt $}}& (F* F)* F&\rTo^{\mu*\id}&F* F\\ \dTo^{\id* \mu}& & & &\dTo_{\mu}\\ F* F& &\rTo^{\mu}& &F \end{diagram} \end{equation} and \begin{equation} \label{diag:2} \begin{diagram} \mathbf 1* F&\rTo^{\nu*\id}& F* F&\rTo^{\id*\nu}&F* \mathbf 1\\ &\rdTo _\lambda& \dTo^{\mu} &\ldTo >{\rho}\\ & &F& & \end{diagram} \end{equation} commute. A monoid $(F,*,\mathbf 1)$ is {\it commutative} if the diagram \begin{equation} \label{diag:3} \begin{diagram} F* F&&\rTo^{\beta}&& F* F\\ &\rdTo _\mu& &\ldTo >{\mu}\\ & &F& & \end{diagram} \end{equation} commutes. It is called {\it simple} if the natural transformation $\nu:\mathbf 1\to F$ is unique. As Menni explains in \cite[Example~3.2]{MennAA}, a natural transformation $\Eta$ from $F\times F$ to $F\circ \amalg$ as in Section~\ref{Sec:MainThm} induces a natural transformation $\mu:F*F\to F$ by $$ F[\O_1]\times F[\O_2] \overset {\eta_{(\O_1,\O_2)}} \longrightarrow F[\O_1\amalg \O_2] \overset\id\longrightarrow F[\O] $$ (where, as usual, $\O=\O_1\amalg\O_2$ is a partition of $\O$) and by the universality property of coproducts. Conversely, a natural transformation $\mu:F*F\to F$ induces a natural transformation $\Eta$ from $F\times F$ to $F\circ\amalg$ by $$ F[\O_1]\times F[\O_2] \longrightarrow (F*F)[\O_1\amalg \O_2] \overset\mu\longrightarrow F[\O_1\amalg \O_2] $$ In this precise sense, natural transformations $\mu:F*F\to F$ and natural transformations $\Eta:F\times F\to F\circ \amalg$ are equivalent notions. Under this equivalence, commutativity of the diagrams~\eqref{diag:1} and \eqref{diag:3} is equivalent to the composition operator $\Eta$ being {\it pointwise associative} and {\it pointwise commutative}, respectively. Here, we say that $\Eta$ is pointwise associative if, for all pairwise disjoint $\O_1,\O_2,\O_3\in\Obj(\mathbf{Set}^r)$, and all elements $x_1\in F[\O_1]$, $x_2\in F[\O_2]$, $x_3\in F[\O_3]$, we have \begin{equation} \label{eq:passoc} \eta_{(\O_1\amalg\O_2,\O_3)} \Big(\big(\eta_{(\O_1,\O_2)}\big((x_1,x_2)\big),x_3\big)\Big)= \eta_{(\O_1,\O_2\amalg\O_3)} \Big(\big(x_1,\eta_{(\O_2,\O_3)}\big((x_2,x_3)\big)\big)\Big), \end{equation} and we say that $\Eta$ is pointwise commutative if, for all $(\O_1,\O_2)\in\Obj(\mathfrak D_r)$, and all elements $x_1\in F[\O_1]$, $x_2\in F[\O_2]$, we have \begin{equation} \label{eq:pcomm} \eta_{(\O_1,\O_2)}\big((x_1,x_2)\big)= \eta_{(\O_2,\O_1)}\big((x_2,x_1)\big). \end{equation} The $\Eta$-maps in Examples~\ref{ex:1} and \ref{ex:2} are instances of pointwise associative and commutative composition operators, while the composition operator in Example~\ref{ex:3} is neither pointwise associative nor pointwise commutative. The notion of pointwise commutativity and associativity should {\it not\/} be confused with the commutativity and the $3$-associativity proved in Lemmas~\ref{lem:comm} and \ref{lem:assoc3}, respectively, which are (in general) strictly weaker assertions. In particular, if $(F,*,\mathbf 1)$ is a monoid, then all ``permutabilities" in Lemmas~\ref{lem:comm}, \ref{lem:assoc3}, \ref{lem:assoc4}, \ref{lem:assoc}, \ref{lem:Feta-assoc} come for free since they hold already on a functorial level, but, as Theorem~\ref{thm:Etwist} shows, the converse is not true; that is, these ``permutabilities" do {\it not\/} guarantee that $(F,*,\mathbf 1)$ forms a monoid. Finally, it is easy to see that there is a unique natural transformation $\nu:\mathbf 1\to F$ if and only if $\vert F[\emptyset]\vert =1$, a condition automatically satisfied by a composition operator (see Lemma~\ref{lem:emptyset}), and it is also easy to see that the diagram~\eqref{diag:2} always commutes. To summarise the above discussion: the notion of $(F,*,\mathbf 1)$ being a simple commutative monoid is equivalent to the corresponding composition operator $\Eta$ being pointwise associative and commutative. \medskip Now that we have discussed the precise relationship between the theory in \cite{MennAA} (specialised to $r$-sort species) and our setting laid down in Section~\ref{Sec:MainThm}, 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 {\it species isomorphism} between two $r$-sort species $F_1$ and $F_2$ is a collection of maps $\boldsymbol\ph=(\ph_\O)_{{\O\in\Obj(\mathbf{Set}^r)}}$, where, for each $\O\in\Obj(\mathbf{Set}^r)$, $$\ph_\O:F_1[\O]\to F_2[\O]$$ is a bijection, with the property that, for every morphism $\ff:\O\to\widetilde\O$ in the category $\mathbf{Set}^r$, the diagram \begin{equation} \label{eq:phinat} \begin{CD} F_1[\O] @>F_1[\ff]>>F_1[\widetilde\O]\\ @V{\ph_\O}VV @VV{\ph_{\widetilde\O}}V\\ F_2[\O] @>>{F_2[\ff]}> F_2[\widetilde\O] \end{CD} \end{equation} commutes. If $F_1$ carries a weak $\Lambda_1$-weight $\ww_1$ and $F_2$ carries a weak $\Lambda_2$-weight $\ww_2$, where, by ``weak," we mean that $\ww_1$ and $\ww_2$ satisfy Axioms~(W0) and (W1), but not necessarily (W2) (cf.\ Section~\ref{Sec:MainThm}), then an isomorphism $\boldsymbol\ph:F_1\to F_2$ is called {\it weight-preserving}, if there exists a ring homomorphism $\lambda:\Lambda_1\to\Lambda_2$ such that the diagram \begin{equation} \label{eq:phiweight} \begin{CD} F_1[\O] @>(w_1)_{\O}>>\Lambda_1\\ @V{\ph_\O}VV @VV{\lambda}V\\ F_2[\O] @>>{(w_2)_{\O}}> \Lambda_2 \end{CD} \end{equation} 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 $\Eta_1$, then $\Eta_1$ can be lifted to a composition operator for $F_2$, demonstrating that $F_2$ is decomposable as well. \begin{lemma} \label{lem:etatrans} Let $F_1$ and $F_2$ be two isomorphic $r$-sort species, where $F_1$ is decomposable with composition operator $\Eta_1$. Furthermore, let $\boldsymbol\ph$ be an isomorphism between $F_1$ and $F_2$. Then $F_2$ is decomposable, and the family of maps $\Eta_2=((\eta_2)_{(\O_1,\O_2)})_{ (\O_1,\O_2)\in\Obj(\mathfrak D_r)}$ defined by \begin{multline*} (\eta_2)_{(\O_1,\O_2)}(x_1,x_2):= \ph_{\O_1\amalg \O_2} \Big((\eta_1)_{(\O_1,\O_2)} \big((\ph^{-1}_{\O_1}(x_1),\ph^{-1}_{\O_2}(x_2))\big)\Big), \\ x_1\in F_2[\O_1],\ x_2\in F_2[\O_2], \end{multline*} is a composition operator for $F_2$. \end{lemma} \begin{proof} We have to show that $\Eta_2$ is a natural transformation from $F_2\times F_2$ to $F_2\circ\amalg$, and that the pair $(F_2,\Eta_2)$ satisfies Axiom~(D1). The former follows immediately from the corresponding property for $(F_1,\Eta_1)$ and the naturality condition \eqref{eq:phinat}. In order to verify (D1), we start with the left-hand side of \eqref{Eq:DecompAx} for the pair $(F_2,\Eta_2)$, suppressing the indices of $\eta_1,\eta_2,\ph$ for better readability: \begin{align*} \eta_2&\big(F_2[\O_1] \times F_2[\O_2]\big) \cap \eta_2\big(F_2[\widetilde{\O}_1] \times F_2[\widetilde{\O}_2]\big)\\ &=\ph\Big(\eta_1 \big(\ph^{-1}(F_2[\O_1])\times\ph^{-1}(F_2[\O_2])\big)\Big) \cap \ph\Big(\eta_1 \big(\ph^{-1}(F_2[\widetilde\O_1]) \times\ph^{-1}(F_2[\widetilde\O_2])\big)\Big)\\ &=\ph\Big(\eta_1\big( F_1[\O_1]\times F_1[\O_2]\big)\Big) \cap \ph\Big(\eta_1\big( F_1[\widetilde\O_1] \times F_1[\widetilde\O_2]\big)\Big)\\ &=\ph\Big(\eta_1\big( F_1[\O_1]\times F_1[\O_2]\big) \cap \eta_1\big( F_1[\widetilde\O_1] \times F_1[\widetilde\O_2]\big)\Big). \end{align*} Here we have used the injectivity of $\ph$ to obtain the last line. Now we substitute the right-hand side of \eqref{Eq:DecompAx} for the pair $(F_1,\Eta_1)$, to obtain \begin{multline*} \eta_2\big(F_2[\O_1] \times F_2[\O_2]\big) \cap \eta_2\big(F_2[\widetilde{\O}_1] \times F_2[\widetilde{\O}_2]\big)\\ =\ph\Big( \eta_1\big(\eta_1\big(F_1[\O_{11}] \times F_1[\O_{12}]\big) \times \eta_1\big(F_1[\O_{21}] \times F_1[\O_{22}]\big)\big)\Big), \end{multline*} where $\O_{ij}:= \O_i \cap \widetilde{\O}_j$ for $i,j\in\{1,2\}$. Using $F_1[\O_{ij}]=\ph^{-1}(F_2[\O_{ij}])$ at each possible place, and inserting $\text{id}=\ph^{-1}\circ\ph$ at two places, we arrive at \begin{align*} \eta_2\big(F_2[\O_1] \times &F_2[\O_2]\big) \cap \eta_2\big(F_2[\widetilde{\O}_1] \times F_2[\widetilde{\O}_2]\big)\\ &=\ph\Big( \eta_1\big(\ph^{-1}\big(\ph\big(\eta_1\big(\ph^{-1}(F_2[\O_{11}]) \times \ph^{-1}(F_2[\O_{12}])\big)\big)\big) \\ &\kern3cm \times \ph^{-1}\big(\ph\big(\eta_1\big(\ph^{-1}(F_2[\O_{21}]) \times \ph^{-1}(F_2[\O_{22}])\big)\big)\big)\big)\Big)\\ &= \eta_2\big(\eta_2\big(F_2[\O_{11}] \times F_2[\O_{12}]\big) \times \eta_2\big(F_2[\O_{21}] \times F_2[\O_{22}]\big)\big), \end{align*} which is exactly \eqref{Eq:DecompAx} for the pair $(F_2,\Eta_2)$. \end{proof} The second preparatory result, Proposition~\ref{lem:E(Feta)} below, states that, given a decomposable $r$-sort species $F$ with pointwise associative and commutative composition operator $\Eta$, $F$ is isomorphic to $E(F_\Eta)$, where $E(F_\Eta)$ denotes the species of sets of $F_\Eta$-structures (cf.\ \cite[p.~8]{BLL} for the definition of the species of sets, $E$, and \cite[p.~41]{BLL} for the definition of composition of species). In rigorous terms, for $\O\in\Obj(\mathbf{Set}^r)$, the set $E(F_\Eta)[\O]$ can be defined by \begin{multline*} E(F_\Eta)[\O]:=\Big\{\big\{(x_1,\O_1),\dots,(x_k,\O_k)\big\}:x_i\in F_\Eta[\O_i],\ i=1,\dots,k,\\ \text{for some $k\in\mathbb N_0$ and }\O_1\amalg\cdots\amalg \O_k=\O,\ \text{all $\O_i$'s being non-empty}\Big\}, \end{multline*} with the obvious notion of induced morphisms. If $F$ carries a weak $\Lambda$-weight $\ww$, then $\ww$ can be lifted to a weak $\Lambda$-weight of $E(F_\Eta)$ by setting $$w_\O\Big(\big\{(x_1,\O_1),\dots,(x_k,\O_k)\big\}\Big):= w_{\O_1}(x_1)\cdots w_{\O_k}(x_k).$$ \begin{proposition} \label{lem:E(Feta)} Let $F$ be a decomposable weighted $r$-sort species with composition operator $\Eta$, where $\Eta$ is pointwise associative and commutative. Then there exists a weight-preserving isomorphism between $F$ and $E(F_\Eta)$. \end{proposition} \begin{proof} The starting point is the combination of Lemmas~\ref{lem:Fzerl} and \ref{lem:Fdisj}. It says that, for each non-empty $\O \in \Obj({\bf Set}^r)$ and every choice of base point $(\omega,\rho)\in\O,$ we have \begin{equation} \label{eq:FOmegaDecomp} F[\O]= \underset{(\omega,\rho)\in\O_1\subseteq\O} {\coprod_{\O_1\in\Obj({\bf Set}^r)}} \eta_{(\O_1,\O-\O_1)}\big(F_\Eta[\O_1] \times F[\O -\O_1]\big). \end{equation} We are now going to construct bijective maps $\ps_\O:F[\O]\to E(F_\Eta)[\O]$ by induction on $\|\O\|$, where $\|\,.\,\|$ has been defined in \eqref{eq:omabs}. For $\O=\pmb\emptyset$, we have $|F[\O]|=|E(F_\Eta)[\O]|=1$ by Lemma~\ref{lem:emptyset} respectively the definition of $E(F_\Eta)$, whence the construction of $\ps_{\pmb\emptyset}$ is trivial. Henceforth, we shall suppose that $\|\O\|\ge1$, and we assume that we have constructed maps $\ps_{\widetilde\O}$ for all $\widetilde\O\in\Obj(\mathbf{Set}^r)$ with $\|\widetilde\O\|