2. Combinatorial species and functional digraphs

A $\mathbb{B}$-species (or simply species) is a functor $F:\mathbb{B}\to\mathbb{B}$, where $\mathbb{B}$ is the category of finite sets with bijections as morphisms. A species defines both a class of labeled combinatorial structures – $F[U]$ – and how relabeling of the underlying set affects these structures – the transport of structure $F[\sigma]$. Since the transport of structure is a bijection, the cardinality of $F[U]$ depends solely on the cardinality of $U$, not on the nature of the elements of $U$. The generating series of a species $F$ is the formal power series

\begin{equation*} F(x)=\sum_{n\ge 0}|F[n]|\frac{x^n}{n!}, \end{equation*}

where $F[n]$ is short for $F[[n]]$ and $[n]=\{1,2,\dots,n\}$ (in particular, $[0]=\emptyset$).

Throughout this paper, we use the following species, whose formal definitions can be found in Joyal’s seminal paper [Reference Joyal13] or in the book by Bergeron, Labelle, and Leroux [Reference Bergeron, Labelle and Leroux2]. These are the main references for combinatorial species theory. Shorter introductions can be found in our papers [Reference Cerbai and Claesson9–Reference Claesson11].

$1=E_0$ is the species characteristic of the empty set.

$X=E_1$ is the species characteristic of singletons.

$E$ is the species of sets.

$L$ is the species of linear orders.

$\mathcal{S}$ is the species of permutations.

$\mathcal{C}$ is the species of cyclic permutations (cycles).

Their generating series are $1(x)=1$, $X(x)=x$,

\begin{equation*} E(x)=e^x,\; L(x)=\mathcal{S}(x)=1/(1-x)\,\text{and }\, \mathcal{C}(x)=-\log\bigl(1-x\bigr). \end{equation*}

Two species $F$ and $G$ are (combinatorially) equal, written $F=G$, if there is a natural isomorphism between them. Equality implies $F(x)=G(x)$, but not conversely: $L(x)=\mathcal{S}(x)$ while $L\neq \mathcal{S}$.

The species $G$ is a subspecies of $F$, written $G\subseteq F$, if for each pair of finite sets $U,V$ and bijection $\sigma:U\to V$ we have $G[U]\subseteq F[U]$ and $G[\sigma]=F[\sigma]|_{G[U]}$. We denote by $F_+$ and $F_n$ the subspecies of $F$ consisting of $F$-structures on nonempty sets and on sets with cardinality $n$, respectively.

Species can be viewed as a categorification of exponential generating series: each operation on formal power series – sum, product, composition, differentiation – has a canonical lift to species that recovers the original operation upon taking generating series. We now describe these lifts, defining only the set of structures; the transport of structure is implicit in each case, and a formal treatment can be found in the book by Bergeron et al. [Reference Bergeron, Labelle and Leroux2].

Given two species $F$ and $G$, an $(F+G)$-structure is either an $F$-structure or a $G$-structure:

\begin{equation*} (F+G)[U]=F[U] \sqcup G[U], \end{equation*}

where $\sqcup$ denotes disjoint union. An $(F\cdot G)$-structure on $U$ is a pair $(s,t)$ such that $s$ is an $F$-structure on a subset $U_1\subseteq U$ and $t$ is a $G$-structure on $U_2=U\setminus U_1$:

\begin{equation*} (F \cdot G)[U] = \bigsqcup_{(U_1,U_2)} F[U_1] \times G[U_2], \end{equation*}

where $U=U_1 \sqcup U_2$ and ‘ $\times$’ denotes Cartesian product.

An $(F\circ G)$-structure, where $G[\emptyset] = \emptyset$, is a generalized partition where each block carries a $G$-structure and the set of blocks is structured by $F$:

\begin{equation*} (F \circ G)[U] = \bigsqcup_{\beta\in\mathrm{Par}[U]} F[\beta]\times \prod_{B\in\beta}G[B], \end{equation*}

where $\mathrm{Par}[U]$ denotes the set of partitions of $U$. For instance, the species of ballots (ordered set partitions) is defined by $\mathrm{Bal} = L\circ E_+$ and hence $\mathrm{Bal}(x)=1/(2-e^x)$; here $|\mathrm{Bal}[n]|$ is the $n$th Fubini number (A000670 [Reference Sloane15]).

The derivative $F'$, defined by $F'[U] = F[U \sqcup \{\star\}]$, adds an element to the underlying set. Pointing $F^{\bullet}$, defined by $F^{\bullet}[U] = F[U]\times U$, distinguishes an element of the set. The two are related by $F^{\bullet} = X\cdot F'$.

The species of endofunctions is defined by

\begin{equation*} \mathrm{End}[U]=\{f:U\to U\} \quad\text{and}\quad \mathrm{End}[\sigma](f)=\sigma\circ f\circ\sigma^{-1} \end{equation*}

for any finite sets $U$ and $V$ and any bijection $\sigma:U\to V$. Throughout this paper, we identify an endofunction $f\in\mathrm{End}[U]$ with its functional digraph, defined as the directed graph with vertex set  $U$ and directed edges $(u,f(u))$, or $u\mapsto f(u)$, $u\in U$. Alternatively, the species of functional digraphs is the subspecies of directed graphs where each node has outdegree one. The transport of structures is inherited from the transport on directed graphs: a directed graph on  $U$ with edges $\{(x,y)\}$ is mapped by the transport of structure along  $\sigma$ to the directed graph on  $V$ with edges $\{(\sigma(x),\sigma(y)\}$. Identifying an endofunction with its functional digraph is a natural isomorphism, and thus the species of endofunctions and functional digraphs are combinatorially equal. An instance of a functional digraph can be found in Figure 1.

Figure 1.

The functional digraph of $f=985776326459548\in\mathrm{End}[15]$, where the $i$th letter of  $f$ is $f(i)$. Internal nodes are black while leaves are white.

Figure 1 Long description

The image shows three separate directed graphs. The first graph has nodes labeled 3, 5, 7, 4, 10, 14, 11 and 13. Node 3 connects to nodes 5 and 7, forming a cycle with node 5. Node 7 connects to node 4, which branches out to nodes 10 and 14. Node 5 connects to nodes 11 and 13. The second graph includes nodes 6, 9, 1 and 12. Node 6 has a loop and connects to node 9, which branches out to nodes 1 and 12. The third graph features nodes 2, 8 and 15. Node 2 connects to node 8, forming a cycle and node 8 connects to node 15.

Let $u\in U$ be a node in the functional digraph of  $f$. We say that $u$ is internal if it has positive indegree, that is, if $u\in\mathrm{Im}(f)$. Otherwise, $u$ is a leaf. A fixed point of  $f$ is an element $u\in U$ such that $f(u)=u$, which corresponds to a loop in the functional digraph.

The species of permutations $\mathcal{S}\subseteq\mathrm{End}$ consists of bijective endofunctions, and cycles $\mathcal{C}\subseteq\mathcal{S}$ are permutations whose functional digraph is a single cycle. Every permutation decomposes uniquely into disjoint cycles, giving $\mathcal{S} = E(\mathcal{C})$ and

\begin{equation*} \mathcal{C}(x)=\log\mathcal{S}(x)=\log\frac{1}{1-x}. \end{equation*}

A derangement is a fixed-point-free permutation; the species $\mathrm{Der}\subseteq\mathcal{S}$ satisfies $\mathcal{S} = E\cdot\mathrm{Der}$ since a permutation is a set of fixed points together with a derangement of the rest. Solving for $\mathrm{Der}(x)$ yields

\begin{equation*} \mathrm{Der}(x)= \frac{e^{-x}}{1-x} \quad\text{and}\quad |\mathrm{Der}[n]|=n!\sum_{i=0}^n\frac{(-1)^i}{i!}. \end{equation*}

The species $\mathcal{A}$ of rooted trees plays a key role in this paper. A tree is a connected acyclic simple graph, and we let $\mathfrak{a}$ denote the species of trees. A rooted tree is a tree with a distinguished node, called its root; equivalently, a pointed tree, $\mathcal{A}=\mathfrak{a}^{\bullet}$. A rooted tree consists of a root (an $X$-structure) to which is appended a set of rooted trees (an $E(\mathcal{A})$-structure). That is,

\begin{equation*} \mathcal{A} \,=\, X\cdot E(\mathcal{A}). \end{equation*}

A slight tweak of the above definition allows us to see rooted trees as a subspecies of functional digraphs. Note that there is exactly one cycle in every connected component of a functional digraph. We identify rooted trees with connected functional digraphs whose only cycle is a loop (a fixed point); this loop plays the role of root, and the edges lose their orientation. Conversely, by putting a loop around the root of a tree and orienting the edges from the leaves toward the root, we obtain a connected functional digraph whose only cycle is a loop. A rooted tree and its digraph counterpart are depicted in Figure 2.

Figure 2.

The functional digraph of $f=693163933\in \mathrm{End}[9]$, on the left, and the corresponding rooted tree, on the right.

Figure 2 Long description

The image shows two diagrams. On the left is a functional digraph with nodes labeled 1 to 9. Node 3 has a loop and arrows point from nodes 6, 8 and 9 towards it. Node 6 connects to nodes 1 and 5, with node 1 connecting to node 4. Node 9 connects to nodes 2 and 7. On the right is a corresponding rooted tree. Node 3 is the root, connected to nodes 6, 8 and 9. Node 6 connects to nodes 1 and 5, with node 1 connecting to node 4. Node 9 connects to nodes 2 and 7. The loop in the digraph is represented by a circle around node 3 in the tree.

A formula first discovered by Borchardt [Reference Borchardt3] and later attributed to Cayley [Reference Cayley5] shows that there are $n^{n-2}$ labeled trees on $[n]$. Joyal [Reference Joyal13] exploited the interplay between rooted trees and endofunctions to prove Cayley’s formula (see also Bergeron et al. [Reference Bergeron, Labelle and Leroux2, Section 2.1]). We recall the core idea, which we extend to two-sort species in Section 7. First, observe that an endofunction is a permutation of rooted trees:

(1)\begin{equation} \mathrm{End}=\mathcal{S}(\mathcal{A}). \end{equation}

To see this, let us distinguish two types of points in its functional digraph:

• • Recurrent points: $u$ such that $f^k(u)=u$ for some $k\ge 1$; they are the points on cycles. Together they form a set of cycles, that is, a permutation.

• • Nonrecurrent points: $u$ such that $f^k(u)\neq u$ for every $k\ge 1$; they are arranged in (rooted) trees each of which hangs from a recurrent point, which can be seen as its root.

The underlying set $U$ is thus partitioned into a set of rooted trees, structured by a permutation of recurrent points. For example, the permutation of the recurrent points of the endofunction in Figure 1 is

\begin{equation*} \begin{array}{llllll} 2\mapsto 8;& 3\mapsto 5;& 5\mapsto 7;& 6\mapsto 6;& 7\mapsto 3;& 8\mapsto 2. \end{array} \end{equation*}

Joyal proved that doubly-rooted trees and nonempty linear orders of rooted trees are combinatorially equal. Indeed, let $t$ be a structure of $\mathcal{A}^{\bullet}=\mathfrak{a}^{\bullet\bullet}$; that is, a tree where two nodes (not necessarily distinct) are distinguished. Define the spine of  $t$ as the directed path from the first distinguished node, the tail, to the second distinguished node, the head. Joyal used the suggestive name ‘vertebrates’ for the species of doubly-rooted trees. The spine determines a nonempty linear order, with a (rooted) tree hanging from each of its nodes. The resulting structure is a nonempty linear order of rooted trees:

\begin{equation*}\mathcal{A}^{\bullet}=L_+(\mathcal{A}). \end{equation*}

Two species $F$ and $G$ are equipotent, written $F\equiv G$, if $F(x)=G(x)$. Since $L\equiv\mathcal{S}$ we have

\begin{equation*} \mathcal{A}^{\bullet}=L_+(\mathcal{A})\equiv\mathcal{S}_+(\mathcal{A})=\mathrm{End}_+ \end{equation*}

so $|\mathcal{A}^{\bullet}[n]|=|\mathrm{End}[n]|=n^n$ for $n\ge 1$. Finally,

\begin{equation*} n^n=|\mathcal{A}^{\bullet}[n]|=|\mathfrak{a}^{\bullet\bullet}[n]|=n^2\cdot|\mathfrak{a}[n]| \end{equation*}

from which Cayley’s formula immediately follows.

If we assume that $U=\{u_1,\ldots,u_n\}$ is totally ordered, with $u_1 \lt u_2 \lt \cdots \lt u_n$, then Joyal’s proof induces a bijection between doubly-rooted trees on $U$ and functional digraphs on $U$. In this case, we map the spine  $s\in L[U]$ of a doubly-rooted tree to the permutation $g\in\mathcal{S}[U]$ such that $g(u_i)=u_j \Leftrightarrow s(i)=u_j$, leaving the rooted trees attached to the spine untouched. This way we obtain a permutation of rooted trees, that is, an endofunction. For instance, the doubly-rooted tree associated with the endofunction of Figure 1 is depicted in Figure 3.

Figure 3.

The doubly-rooted tree associated with the endofunction of Figure 1 under Joyal’s bijection. The spine is colored in blue and dashed; tail and head are distinguished with one and two circles, respectively.

Figure 3 Long description

The diagram shows a doubly-rooted tree with nodes labeled from 1 to 15. The spine is represented by a dashed line connecting nodes 8, 5, 7, 6, 3 and 2. Node 8 has an arrow pointing to node 15. Node 5 connects to nodes 11 and 13. Node 7 connects to nodes 10 and 14. Node 6 connects to nodes 1 and 12. The spine starts at node 8, marked with a single circle and ends at node 2, marked with a double circle.

By adjusting equation (1), one obtains species identities for several classes of endofunctions defined in terms of properties of their functional digraph. For instance, the recurrent points of a connected endofunction form a cyclic permutation, and hence the species of connected endofunctions is $\mathcal{C}(\mathcal{A})$. Similarly, if the recurrent points are structured in a set, we obtain forests (acyclic functional digraphs), $E(\mathcal{A})$. If the permutation of recurrent points is a derangement, we obtain functional digraphs with no fixed points, $\mathrm{Der}(\mathcal{A})$. In some cases, pairing these equations with Cayley’s formula leads to explicit enumeration of the corresponding digraphs. These examples are well known; see Table 1 (A-numbers refer to the OEIS [Reference Sloane15]).

Table 1.

Enumeration of functional digraphs of permutations and endofunctions, where $\delta$ is the Kronecker delta.

Table 1 Long description

The table presents enumeration formulas for permutations and endofunctions across different structures, including all structures, trees, forests, connected structures, and derangements. For permutations, the formulas mainly use factorial-based expressions. “All structures” is given by n factorial. “Connected structures” is given by (n minus 1) factorial multiplied by (1 minus delta of n and 0), where delta represents the Kronecker delta function. “Derangements” reference integer sequence A000166. For endofunctions, the formulas mainly use power-based expressions. “All structures” is given by n raised to the power n. “Trees” is given by n raised to the power (n minus 1), while “Forests” is given by (n plus 1) raised to the power (n minus 1). “Connected structures” reference integer sequence A001865, and “Derangements” are given by (n minus 1) raised to the power n. The table emphasizes the contrast between permutations and endofunctions, with permutations typically relying on factorial calculations and endofunctions relying on exponential or power-based calculations.

3. Cayley permutations

We now define the species of Cayley permutations [Reference Cerbai, Claesson, Ernst and Golab10]. A Cayley permutation on  $U$ is a function $f:U\rightarrow [n]$ where $\mathrm{Im}(f)=[k]$ for some $k\leq n=|U|$. The transport of structure along a bijection $\sigma: U \to V$ is given by

\begin{equation*} \mathrm{Cay}[\sigma](f)=f\circ\sigma^{-1}. \end{equation*}

Cayley permutations and ballots are combinatorially equal [Reference Cerbai, Claesson, Ernst and Golab10]. In the special case where $U=[n]$, we have the inclusions

\begin{equation*} \mathcal{S}[n]\subseteq\mathrm{Cay}[n]\subseteq\mathrm{End}[n] \end{equation*}

and each of these structures can be identified with its functional digraph. There is, however, no obvious way to define the functional digraph of Cayley permutations on an arbitrary finite set  $U$. Furthermore, the transport of structure on $\mathcal{S}$ and $\mathrm{End}$ is conjugation, which cannot be extended to Cayley permutations due to the requirement $\mathrm{Im}(f)=[k]$. For these reasons, we now assume $\mathbb{L}$-species, defined below.

Let $\mathbb{L}$ denote the category of finite totally ordered sets with order-preserving bijections as morphisms. An $\mathbb{L}$-species is a functor $F:\mathbb{L}\to\mathbb{B}$. Since there is a unique order-preserving bijection between any pair of finite totally ordered sets of the same cardinality, transport of structure is immaterial in the context of $\mathbb{L}$-species. We often assume that the underlying total order is $[n]$ with the standard order and regard permutations and Cayley permutations as subspecies of endofunctions. This allows us to identify all these structures with their functional digraph. Another consequence of having a unique order-preserving bijection between totally ordered sets with the same cardinality is that for $\mathbb{L}$-species $F=G$ if and only if $F(x)=G(x)$. For example, $L=\mathcal{S}$ as $\mathbb{L}$-species even though $L\neq\mathcal{S}$ as $\mathbb{B}$-species. In this case, a permutation $f\in\mathcal{S}[n]$ is naturally identified with the linear order $f(1)f(2)\ldots f(n)$ in $L[n]$.

Operations on $\mathbb{B}$-species extend naturally to $\mathbb{L}$-species. New operations also become possible. Given two totally ordered sets $\ell_1=(U_1, \preceq_1)$ and $\ell_2=(U_2,\preceq_2)$, their ordinal sum $\ell=\ell_1 \oplus \ell_2$ is the totally ordered set $\ell=(U,\preceq)$ where $U=U_1\sqcup U_2$, $\preceq$ respects $\preceq_1$ and $\preceq_2$, and all elements of $U_1$ are smaller than the elements of $U_2$. The totally ordered sets obtained by adding a new minimum or maximum element to $\ell$ are denoted by $1\oplus\ell$ and $\ell \oplus 1$, respectively. Given a totally ordered set $\ell=(U,\preceq)$, the derivative $F'$ of an $\mathbb{L}$-species $F$ is defined by $F'[\ell]=F[1\oplus\ell]$. Additionally, the integral of $F$, denoted $\int_0^X F(T) dT$ or $\int F$, is defined by

\begin{equation*} \left( \int F \right) [\ell] = \begin{cases} \emptyset & \text{if }\ell = \emptyset, \\ F[\ell \setminus \{\min(\ell)\}] & \text{if } \ell \neq \emptyset. \end{cases} \end{equation*}

In other words, an $F'$-structure is an $F$-structure on a total order endowed with a new minimum, and an $\int\! F$-structure is an $F$-structure on a total order deprived of its minimum. Derivative and integral can be alternatively defined in terms of maximum elements: $F'[\ell]=F[\ell\oplus 1]$ and $(\int F)[\ell]=F[\ell\setminus \{\max(\ell)\}]$ for $\ell\neq\emptyset$. Similarly to $\mathbb{B}$-species, operations on $\mathbb{L}$-species behave well with respect to generating series, including a species version of the fundamental theorem of calculus [Reference Bergeron, Labelle and Leroux2,  equation 35]:

\begin{equation*} \int F' = F_+; \qquad \left(\int F\right)' = F; \qquad \left( \int_0^X F(T) dT \right)(x) = \int_0^x F(t) dt. \end{equation*}

Let us now return to Cayley permutations. We have observed in Section 2 that functional digraphs of endofunctions are precisely those directed graphs where each node has outdegree one. It is easy to see that a functional digraph is the functional digraph of a permutation if and only if each node has both indegree and outdegree equal to one. The following lemma holds because the internal nodes of $f\in\mathrm{End}[n]$ are labeled by $\mathrm{Im}(f)$, and we omit its proof. It characterizes the functional digraphs of Cayley permutations as those whose internal nodes are labeled with the smallest elements of the underlying total order.

Equivalently, $\mathrm{Cay}$ as an $\mathbb{L}$-species is isomorphic to the species of functional digraphs of endofunctions  $f\colon\ell\to\ell$ such that each internal node is smaller than each leaf. Although $\mathbb{L}$-species address some of the cosmetic issues of Cayley permutations, there are structural problems that require a more sophisticated approach. As an example, consider the following functional digraph:

It is the functional digraph of the endofunction  $f\in\mathrm{End}[3]$ where $f(1)=f(2)=1$ and $f(3)=3$. In each connected component, every internal node is smaller than every leaf, yet this property fails for the full functional digraph: node  $3$ is internal but larger than the leaf  $2$. Thus, $f$ is not a Cayley permutation. More generally, an endofunction is a permutation of rooted trees, but a Cayley permutation is not a permutation of rooted trees of Cayley permutations. Similarly, we cannot use composition to obtain species equations for Cayley permutations whose functional digraph is connected, a forest, or a derangement. Generalizing the equation $\mathcal{S}=E\cdot\mathrm{Der}$ is also not possible: a Cayley permutation is not a pair consisting of the set of its fixed points together with a Cayley permutation without fixed points.

To circumvent these issues, we assume that internal nodes and leaves are nodes of different sorts. This can be formalized using two-sort species.

A two-sort $\mathbb{B}$-species (or $\mathbb{B}$-species of two sorts) is a functor $F:\mathbb{B}\times\mathbb{B}\to\mathbb{B}$, where $\mathbb{B}\times\mathbb{B}$ denotes the product category with pairs of finite sets as objects and pairs of bijections as arrows. Composition of arrows is componentwise, and the identity arrow on the pair $(U,V)$ is $\mathrm{id}_{(U,V)}=(\mathrm{id}_U,\mathrm{id}_V)$. Two-sort species allow us to build combinatorial structures whose underlying set contains elements of two different sorts: those belonging to  $U$ and those belonging to  $V$. For a two-sort species  $F$, we write $F=F(X,Y)$ to indicate that the two sorts are called  $X$ and  $Y$. The letters  $X$ and  $Y$ also serve as singleton species of the corresponding sort:

\begin{align*} X[U,V]&=\begin{cases} \{u\}, & \text{if}\ U=\{u\}\ \text{and}\ V=\emptyset;\\ \emptyset, & \text{otherwise}. \end{cases}\\[1.5ex] Y[U,V]&=\begin{cases} \{v\}, & \text{if}\ U=\emptyset\ \text{and}\ V=\{v\};\\ \emptyset, & \text{otherwise}. \end{cases} \end{align*}

The generating series of $F(X,Y)$ is

\begin{equation*} F(x,y)= \sum_{i,j\ge 0}|F[i,j]|\frac{x^i}{i!}\frac{y^j}{j!}, \end{equation*}

where we let $F[i,j]=F[[i],[j]]$. Most of the operations introduced for unisort species can be naturally extended to the two-sort context, and definitions can be found in the usual references [Reference Bergeron, Labelle and Leroux2, Reference Claesson11]. An example relevant in the next sections is partial differentiation:

\begin{equation*} \left(\displaystyle{\frac{\partial{F}}{\partial X}}\right)[U,V]=F[U\cup\{*\},V]; \qquad \left(\displaystyle{\frac{\partial{F}}{\partial Y}}\right)[U,V]=F[U,V\cup\{*\}]. \end{equation*}

Similarly, we have two pointing operations:

(2)\begin{equation} F^{^{\bullet_X}}=X\cdot\left(\displaystyle{\frac{\partial{F}}{\partial X}}\right); \qquad F^{^{\bullet_Y}}=Y\cdot\left(\displaystyle{\frac{\partial{F}}{\partial Y}}\right). \end{equation}

Composition of two-sort species is more delicate and requires additional care. We define it below in the only case needed in this paper. Let $F$ be a unisort species and let $G=G(X,Y)$ be a two-sort species. Then $F\circ G=(F\circ G)(X,Y)$ is the two-sort species with structures

\begin{equation*} \left(F\circ G\right)[U,V]= \bigcup_{\beta\in\mathrm{Par}[U \sqcup V]}F[\beta]\times\prod_{B\in\beta}G[B\cap U,B\cap V]. \end{equation*}

An $\bigl(F\circ G\bigr)$-structure is thus a generalized partition on elements of two sorts, where each block carries a $G$-structure (of two-sorts), and the blocks are structured by the (unisort) species  $F$. For example, $E\circ(X+Y)=E(X)\cdot E(Y)$ is the species of sets of elements of two sorts. A more substantial example opens the next section.

4. R-recurrent functional digraphs

Recall from Section 2 that rooted trees of one sort are defined by the species equation

\begin{equation*} \mathcal{A}(X) \,=\, X\cdot E\bigl(\mathcal{A}(X)\bigr). \end{equation*}

We use the same letter here to denote the two-sort species $\mathcal{A}=\mathcal{A}(X,Y)$ of rooted trees with internal nodes of sort  $X$ and leaves of sort  $Y$. Then

(3)\begin{equation} \mathcal{A}(X,Y) \,=\, X\cdot E\bigl(\mathcal{A}(X,Y)-X+Y\bigr), \end{equation}

where $\mathcal{A}(X,0)=X$ is the tree consisting of a single root (of sort  $X$). Indeed – as in the unisort case – a rooted tree of two sorts is obtained by appending a set of rooted trees of two sorts to the root  $X$. There is one caveat: when we append a single node  $X$, it becomes a leaf in the resulting tree and thus its sort changes from  $X$ to  $Y$. This explains the additional term $-X+Y$ in equation (3).

In the unisort case, an endofunction is a permutation of rooted trees, $\mathrm{End}=\mathcal{S}\circ\mathcal{A}$. More precisely, functional digraphs of endofunctions are obtained by structuring the roots of a set of rooted trees in an $\mathcal{S}$-structure. Since this construction preserves internal nodes and leaves, the composition $ \mathcal{S}\circ\mathcal{A}(X,Y) $ yields functional digraphs of two sorts where internal nodes have sort  $X$ and leaves have sort  $Y$. The same holds for the species of Table 1 if we replace $\mathcal{S}$ with $E$ (forests, that is, acyclic functional digraphs), $\mathcal{C}$ (connected functional digraphs), and $\mathrm{Der}$ (derangements, that is, functional digraphs with no fixed points). This brings us to the following definition of $R$-recurrent functional digraphs of two sorts (see also Figure 4).

Definition 4.1. Let $R$ be a unisort species. The species $\Psi_R=\Psi_R(X,Y)$ of $R$-recurrent functional digraphs of two sorts is defined by

(4)\begin{equation} \Psi_R(X,Y)=R\circ\mathcal{A}(X,Y). \end{equation}

Figure 4.

An $R$-recurrent functional digraph of two sorts. Nodes of sort  $X$ (internal nodes) are black and labeled by numbers; nodes of sort  $Y$ (leaves) are white and labeled by letters.

Figure 4 Long description

The diagram depicts a functional digraph with nodes labeled by numbers and letters. Internal nodes are represented by black circles and labeled with numbers, while leaves are represented by white circles and labeled with letters. The digraph is structured within a rectangular box labeled 'R'. Node 1 connects to nodes 10 and a, with node 10 further connecting to nodes 2, d and g. Node 5 connects to node 6, which branches to nodes 7, c, f and 3, b. Node 8 connects to node e. Node 9 is isolated within the box. The structure illustrates the hierarchical relationships between nodes and leaves.

In other words, a $\Psi_R$-structure is obtained by putting an $R$-structure on the roots of a set of rooted trees of two sorts; in this context, the $R$-structure is called the recurrent part and its points are said to be recurrent. Some significant choices of  $R$ are listed in Table 2. Note also that $\Psi_X(X,Y)=\mathcal{A}(X,Y)$, which gives

(5)\begin{equation} \Psi_R = R\circ\Psi_X. \end{equation}

Table 2.

Unisort species of endofunctions and Cayley permutations for different choices of the recurrent structure  $R$ in $\Psi_R(X,Y)$.

Table 2 Long description

The table compares endofunctions and Cayley permutations for different recurrent structures denoted by R in the context of “C subscript R of X comma Y structures.” The categories include all structures, trees, forests, connected structures, and derangements. For each category, corresponding endofunctions and Cayley permutations are listed. For example, the tree category associates endofunctions with “C subscript X” structures and Cayley permutations with “Cay subscript X.” Similar pairings are shown for forests, connected structures, and derangements, each linked to a specific recurrent structure represented by R. The table emphasizes the variety of mathematical structures and the relationships between endofunctions and Cayley permutations, clearly distinguishing how each recurrent structure corresponds to different mathematical functions and structural properties.

The two-sort species $\Psi_R$ simultaneously encompasses (subspecies of) Cayley permutations and endofunctions, allowing us to enumerate functional digraphs of both types at once. From an enumerative standpoint, using different sorts for internal nodes and leaves is equivalent to labeling the internal nodes with the smallest elements of the underlying total order (and the remaining elements with the largest), which characterizes functional digraphs of Cayley permutations by Lemma 3.1. On the other hand, using the same sort $X=Y$ for internal nodes and leaves yields all functional digraphs, that is, all endofunctions. We shall make this observation more formal, but first, a couple of definitions.

Let $F=F(X,Y)$ be a two-sort species. The unisort species $F(X,X)$ is obtained by identifying the sorts  $X$ and  $Y$. Note that

(6)\begin{equation} F(X,X)[U] = \bigcup_{U_1\sqcup U_2=U}F[U_1,U_2] \end{equation}

and

(7)\begin{equation} |F(X,X)[n]| =\sum_{i+j=n}\binom{n}{i}|F[i,j]|. \end{equation}

Assuming $\mathbb{L}$-species, we also let $\widehat{F}(Z)$ be the unisort species whose structures are

(8)\begin{equation} \widehat{F}[\ell]=\bigcup_{\ell_1\oplus \ell_2=\ell}F[\ell_1,\ell_2]. \end{equation}

That is, an $\widehat{F}$-structure on  $\ell$ is simply an $F(X,Y)$-structure on $[\ell_1,\ell_2]$, where $\ell=\ell_1\oplus\ell_2$. As a result,

(9)\begin{equation} |\widehat{F}[n]| =\sum_{i+j=n}|F[i,j]|. \end{equation}

Now, a $\Psi_{\mathcal{S}}$-structure where internal nodes and leaves have the same sort is simply a functional digraph of one sort, and we have the combinatorial equality

\begin{equation*} \Psi_{\mathcal{S}}(X,X)=\mathrm{End}(X). \end{equation*}

On the other hand, by Lemma 3.1 there is a bijection between $\widehat{\Psi}_{\mathcal{S}}[n]$ and $\mathrm{Cay}[n]$. More precisely, structures in $\Psi_{\mathcal{S}}[i,j]$ correspond to functional digraphs of Cayley permutations on $[n]=[i+j]$ that have  $i$ internal nodes and  $j$ leaves. Therefore,

\begin{equation*} \widehat{\Psi}_{\mathcal{S}}(X)=\mathrm{Cay}(X). \end{equation*}

This motivates the following definition.

Definition 4.2. Let $R$ be a unisort species. The species of $R$-recurrent endofunctions and the species of $R$-recurrent Cayley permutations are defined as follows:

\begin{align*} \mathrm{End}_R(X) &\,=\, \Psi_R(X,X); \\ \mathrm{Cay}_R(X) &\,=\, \widehat{\Psi}_R(X). \end{align*}

Our main goal is to find a formula for $|\Psi_R[i,j]|$. Then, by choosing $R$ as one of $\mathcal{S}$, $X$, $E$, $\mathcal{C}$, or $\mathrm{Der}$, and letting $F=\Psi_R$ in equations (7) and (9), we obtain counting formulas for the endofunctions and Cayley permutations of Table 2. Comparing (7) and (9) also shows that the number of endofunctions with  $i$ internal nodes and  $j$ leaves is simply obtained by multiplying the corresponding number of Cayley permutations by the binomial coefficient $\binom{i+j}{i}$; this additional term accounts for the possibility of labeling internal nodes and leaves of endofunctions without the constraint of using the smallest  $i$ labels for the internal nodes.

In Section 3, we observed that neither the equation $\mathrm{End} = \mathcal{S}\circ \mathcal{A}$ nor the equation $\mathcal{S} = E\cdot\mathrm{Der}$ readily extends to Cayley permutations. Both constructions are, however, valid for the two-sort species $\Psi_{\mathcal{S}}$. Indeed, $\Psi_{\mathcal{S}}=\mathcal{S}\circ \Psi_X$ by definition, and using $\mathcal{S}=E\cdot\,\mathrm{Der}$ it follows that

\begin{align*} \Psi_{\mathcal{S}} &= (E\cdot\mathrm{Der})\circ\Psi_X \\ &= E(\Psi_X)\cdot\mathrm{Der}(\Psi_X) = \Psi_{E}\cdot \Psi_{\mathrm{Der}}. \end{align*}

Therefore, in the two-sort sense, functional digraphs are permutations of rooted trees. They are also products of sets of rooted trees (forests) and functional digraphs with no fixed points.

5. A differential equation

Equation (4) defines $\Psi_R(X,Y)$ as the composition of $R$ with rooted trees of two sorts. Our goal is a formula for the coefficients $|\Psi_R[i,j]|$. While the definition is transparent, it does not readily yield these coefficients. We give an alternative recursive construction leading to a differential equation from which they can be extracted.

To build any $\Psi_R$-structure, we first build its recurrent part, an $R$-structure of recurrent points of sort  $X$. The nonrecurrent points are located on rooted trees of two sorts, each of which hangs from a recurrent point. Such a rooted tree can be obtained recursively. Starting from its root, one repeatedly appends to a specified internal node a path of internal nodes that ends with a leaf; that is, a structure of $L(X)\cdot Y$, which we call a branch. This recursive construction of $\Psi_R$-structures is described by the differential equation

(10)\begin{equation} \displaystyle{\frac{\partial}{\partial Y}}\Psi_R(X,Y) = L(X)\cdot\Psi_R^{\bullet_X}(X,Y),\qquad \Psi_R(X,0)=R(X). \end{equation}

The initial condition determines the recurrent structure. On the left-hand side of the main equation, we have a structure of $(\partial/\partial Y)\Psi_R$; that is, a $\Psi_R$-structure with an additional leaf. Equivalently, consider the maximal path starting from the additional leaf (excluded) that consists of internal nodes with indegree at most one. It is an $L(X)$-structure, which is appended to an internal node of a $\Psi_R$-structure. By pointing to that internal node, we obtain a $\Psi_R^{\bullet_X}$-structure.

Assuming $\mathbb{L}$-species, we can rewrite equation (10) using the integral operator as

\begin{equation*} \Psi_R(X,Y) = R(X) + \int L(X)\cdot\Psi_R^{\bullet_X}(X,Y)dY. \end{equation*}

Figure 5 illustrates this construction. We give a formal proof of equation (10) next. The proof uses the virtual species identity $L^{-1} = 1-X$; see [Reference Bergeron, Labelle and Leroux2, Section 2.5] for background on virtual species.

Proof. Recall from equations (3) and (5) that $\Psi_R=R\circ\Psi_X$ and $\Psi_X=X\cdot E\bigl(\Psi_X-X+Y\bigr)$, where $\Psi_X=\mathcal{A}(X,Y)$ and $\Psi_X(X,0)=X$. That $\Psi_R$ satisfies the initial condition of (10) is easy to see:

\begin{equation*} \Psi_R(X,0)=R\circ\Psi_X(X,0)=R(X). \end{equation*}

Next, we calculate the partial derivatives of $\Psi_X$. On differentiating the equation $\Psi_X=X\cdot E\bigl(\Psi_X-X+Y\bigr)$ we get

\begin{equation*} \displaystyle{\frac{\partial{\Psi_X}}{\partial X}} \,=\, \Bigl(\displaystyle{\frac{\partial{\Psi_X}}{\partial X}} + X - 1\Bigr)\cdot E(\Psi_X-X+Y) \end{equation*}

or, equivalently,

\begin{equation*} X\cdot(1-\Psi_X)\cdot \displaystyle{\frac{\partial{\Psi_X}}{\partial X}} \,=\, (1-X)\cdot \Psi_X. \end{equation*}

Since $L\cdot (1-X) = 1$ and $L_+ = XL$ we can rewrite this as

\begin{equation*} L_+(X)\cdot \displaystyle{\frac{\partial{\Psi_X}}{\partial X}} = L_+\bigl(\Psi_X\bigr). \end{equation*}

By a similar calculation, we find that

\begin{equation*} \displaystyle{\frac{\partial{\Psi_X}}{\partial Y}} = L_+\bigl(\Psi_X\bigr) \end{equation*}

and putting these last two equations together, we arrive at

\begin{equation*} \displaystyle{\frac{\partial{\Psi_X}}{\partial Y}} = L_+(X) \cdot \displaystyle{\frac{\partial{\Psi_X}}{\partial X}}. \end{equation*}

Finally, we differentiate $\Psi_R=R\circ\Psi_X$ to obtain

\begin{align*} \displaystyle{\frac{\partial{\Psi_R}}{\partial Y}} &= \displaystyle{\frac{\partial{\Psi_X}}{\partial Y}} \cdot R'(\Psi_X) \\ &= L_+(X) \cdot \displaystyle{\frac{\partial{\Psi_X}}{\partial X}} \cdot R'(\Psi_X) \\ &= L_+(X) \cdot \displaystyle{\frac{\partial{\Psi_R}}{\partial X}} = L(X)\cdot \Psi_R^{\bullet_X}, \end{align*}

which concludes the proof.

Figure 5.

The construction manifested in equation (10). On the left, a $\Psi_R$-structure with an additional leaf, denoted by  $\star$. On the right, its decomposition into a linear order together with a $\Psi_R$-structure in which an internal node is pointed (circled). The path from  $\star$ through internal nodes of indegree one gives the linear order $5\,4\,7\,2$; it attaches at  $6$, which becomes the pointed node. The boxed region denotes the $R$-structure on the recurrent nodes.

Figure 5 Long description

The diagram illustrates a mathematical relationship between two structures. On the left, the expression partial derivative of Psi subscript R over partial derivative of Y is shown with a structure labeled R containing a node labeled 3, connected to nodes labeled 1, 6 and others. Nodes 1, a, b, 2, c, 7, 4, 5 and a star are connected with arrows indicating direction. On the right, the expression L left parenthesis X right parenthesis times Psi superscript bullet X subscript R is shown with a similar structure. The node labeled 6 is circled and nodes 2, 7, 4 and 5 are vertically aligned with arrows. The diagram uses arrows to indicate equivalence between the two structures, highlighting the transformation or relationship between them.

Equation (10) immediately leads to a recursive formula for $|\Psi_R[i,j]|$.

Lemma 5.2. We have

\begin{equation*} |\Psi_R[i,j]|= \begin{cases} |R[i]| & j=0;\\ 0 & j\ge 1,i=0;\\ i\cdot\bigl(|\Psi_R[i,j-1]|+|\Psi_R[i-1,j]|\bigr) & i,j\ge 1. \end{cases} \end{equation*}

Proof. It is easy to see that the first two identities hold. Next, we rewrite equation (10) of Theorem 5.1 as follows:

\begin{align*} \displaystyle{\frac{\partial{\Psi_R}}{\partial Y}} = L\cdot X\cdot \displaystyle{\frac{\partial{\Psi_R}}{\partial X}} &\;\,\iff\;\, \displaystyle{\frac{\partial{\Psi_R}}{\partial Y}}\cdot (1-X) = X\displaystyle{\frac{\partial{\Psi_R}}{\partial X}} \\ &\;\,\iff\;\, \displaystyle{\frac{\partial{\Psi_R}}{\partial Y}} = X\cdot \left(\displaystyle{\frac{\partial{\Psi_R}}{\partial X}}+\displaystyle{\frac{\partial{\Psi_R}}{\partial Y}}\right). \end{align*}

Identifying coefficients of the last equation gives the third identity.

Next, we use Lemma 5.2 to obtain the anticipated formula for $|\Psi_R[i,j]|$. It involves the $r$-Stirling numbers of the second kind, defined as follows. Let $n,m,r\ge 0$. The $r$-Stirling number of the second kind $\genfrac{\{}{\}}{0pt}{}{{n}}{{m}}_{{r}}$ is the number of set partitions of $[n]$ with  $m$ blocks such that the numbers $1,2,\ldots,r$ are contained in distinct blocks. Broder [Reference Broder4, Theorem 2] showed that these numbers obey a recurrence analogous to the one satisfied by the classic Stirling numbers:

(11)\begin{equation} \genfrac{\{}{\}}{0pt}{}{{n}}{{m}}_{{r}}=m\genfrac{\{}{\}}{0pt}{}{{n-1}}{{m}}_{{r}}+\genfrac{\{}{\}}{0pt}{}{{n-1}}{{m-1}}_{{r}}, \quad r \lt n, \end{equation}

with initial conditions $\genfrac{\{}{\}}{0pt}{}{{n}}{{m}}_{{n}}=\delta_{m,n}$, and $\genfrac{\{}{\}}{0pt}{}{{n}}{{m}}_{{r}}=0$ if $r \gt n$. We defineFootnote ¹

\begin{equation*} \genfrac{\{}{\}}{}{}{{n}}{{m}}_{{r}}:=\genfrac{\{}{\}}{0pt}{}{{n}}{{m}}_{{r}}-\genfrac{\{}{\}}{0pt}{}{{n}}{{m}}_{{r+1}}. \end{equation*}

This difference of $r$-Stirling numbers counts set partitions of $[n]$ with  $m$ blocks such that the numbers $1,2,\ldots,r$ are contained in distinct blocks, but $1,2,\ldots,r,r+1$ are not. In other words, $r$ is maximal such that $1,2,\ldots,r$ appear in distinct blocks. From (11) it follows that

(12)\begin{equation} \genfrac{\{}{\}}{}{}{{n}}{{m}}_{{r}}=m\genfrac{\{}{\}}{}{}{{n-1}}{{m}}_{{r}}+\genfrac{\{}{\}}{}{}{{n-1}}{{m-1}}_{{r}}, \quad r \lt n \end{equation}

except $\genfrac{\{}{\}}{}{}{{n}}{{n}}_{{n-1}}=0$, with initial conditions $\genfrac{\{}{\}}{}{}{{n}}{{m}}_{{n}}=\delta_{m,n}$, and $\genfrac{\{}{\}}{}{}{{n}}{{m}}_{{r}}=0$ if $r \gt n$. In Table 3, we give the numbers $\genfrac{\{}{\}}{}{}{{n}}{{m}}_{{r}}$ for $r = 1,2,3,4$, $n=1,2,\ldots,8$ and $m=1,2,\ldots,8$.

Table 3.

Triangles of the numbers $\genfrac{\{}{\}}{}{}{{n}}{{k}}_{{r}}$, for $r=1,2,3,4$.

Table 3 Long description

The table presents triangular arrays of numbers for r values equal to 1, 2, 3, and 4, showing how the combinatorial values increase as both n and k grow. For r equals 1, the sequence begins with 1 and increases steadily, reaching 301 at n equals 8 and k equals 2. For r equals 2, the values begin at 0 and grow more rapidly, reaching 422 at n equals 8 and k equals 2. For r equals 3, the numbers also begin at 0 and rise to 243 at n equals 8 and k equals 2, displaying a more varied growth pattern. For r equals 4, the values start at 0 and increase to 256 at n equals 8 and k equals 3, representing the largest spread and most complex arrangement among the four arrays. The table demonstrates how the numerical values expand rapidly as the r value increases, with each triangular array exhibiting distinct combinatorial growth trends across the n and k indices.

Theorem 5.3. For $i,j,r\ge 0$, we have

\begin{equation*} |\Psi_{R_r}[i,j]|=\frac{i!|R[r]|}{r!}\genfrac{\{}{\}}{}{}{{i+j}}{{i}}_{{r}}. \end{equation*}

Proof. We shall prove that the term on the right-hand side satisfies the recursion of Lemma 5.2 with $R=R_r$. The initial conditions are easy to verify, so let us assume that $i,j\ge 1$. We need to prove that

\begin{equation*} \frac{i!|R[r]|}{r!}\genfrac{\{}{\}}{}{}{{i+j}}{{i}}_{{r}} =\, i\cdot\left( \frac{(i-1)!|R[r]|}{r!}\genfrac{\{}{\}}{}{}{{i+j-1}}{{i-1}}_{{r}} \;+\;\frac{i!|R[r]|}{r!}\genfrac{\{}{\}}{}{}{{i+j-1}}{{i}}_{{r}} \right). \end{equation*}

But this is equivalent to $\genfrac{\{}{\}}{}{}{{i+j}}{{i}}_{{r}} = \genfrac{\{}{\}}{}{}{{i+j-1}}{{i-1}}_{{r}}+i\genfrac{\{}{\}}{}{}{{i+j-1}}{{i}}_{{r}}$, which follows from (12).

Using Theorem 5.3 and summing over  $r$, we arrive at the following corollary.

Corollary 5.4. For $i,j\ge 0$, we have

(13)\begin{equation} |\Psi_R[i,j]| = i!\sum_{r=0}^i \frac{|R[r]|}{r!}\left\{\frac{i+j}{i}\right\}_{r}. \end{equation}

Recall from Definition 4.2 that $\mathrm{End}_R(X)=\Psi_R(X,X)$ and $\mathrm{Cay}_R(X)=\widehat{\Psi}_R(X)$. The number of $R$-recurrent endofunctions and Cayley permutations on $[n]=[i+j]$ are now obtained by combining equation (13) with identities (7) and (9).

Corollary 5.5. For $n\ge 0$, we have

\begin{align*} |\mathrm{End}_{R}[n]| &= \sum_{r=0}^n\frac{|R[r]|}{r!}\sum_{i=0}^n(n)_{i} \genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}} \end{align*}

and

\begin{align*} |\mathrm{Cay}_{R}[n]| &= \sum_{r=0}^n\frac{|R[r]|}{r!}\sum_{i=0}^ni!\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}}. \end{align*}

The expression $(n)_{i}$, above, is the falling factorial; it is defined by

\begin{equation*} (n)_{i} = n(n-1)(n-2)\cdots(n-i+1) = \binom{n}{i}i!. \end{equation*}

Letting $R=E_r$ in Corollary 5.5, we obtain two identities for the number of forests of $r$ rooted trees of endofunctions and Cayley permutations:

\begin{align*} |\mathrm{End}_{E_r}[n]| &= \sum_{i=0}^n\frac{(n)_{i}}{r!}\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}}; \\ |\mathrm{Cay}_{E_r}[n]| &= \sum_{i=0}^n\frac{i!}{r!}\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}}. \end{align*}

These allow us to rewrite the formulas of Corollary 5.5 as

(14)\begin{equation} |\mathrm{End}_{R}[n]| = \sum_{r=0}^n|R[r]|\cdot|\mathrm{End}_{E_r}[n]|; \end{equation}

(15)\begin{equation} |\mathrm{Cay}_{R}[n]| = \sum_{r=0}^n|R[r]|\cdot|\mathrm{Cay}_{E_r}[n]|. \end{equation}

The combinatorics underlying equations (14) and (15) is clear: An $\mathrm{End}_R$-structure is obtained by putting an $R$-structure over a set of rooted trees. The same holds for $\mathrm{Cay}_R$-structures. Furthermore, a forest of endofunctions is a set of rooted trees: $\mathrm{End}_{E}=E\circ\mathrm{End}_X$ and $\mathrm{End}_{E_r} = E_r\circ\mathrm{End}_X = \frac{1}{r!}(\mathrm{End}_X)^r$. Thus, hidden underneath equation (14) we find the species composition $\mathrm{End}_R = R\circ\mathrm{End}_X$, which is equation (4) when $Y=X$. On the other hand, $\mathrm{Cay}_{E}\neq E\circ\mathrm{Cay}_X$.

Alternatively, letting $R=\mathcal{S}_r$ we obtain

\begin{align*} |\mathrm{End}_{R}[n]| &= \sum_{r=0}^n\frac{|R[r]|}{r!}|\mathrm{End}_{S_r}[n]|; \\ |\mathrm{Cay}_{R}[n]| &= \sum_{r=0}^n\frac{|R[r]|}{r!}|\mathrm{Cay}_{S_r}[n]|, \end{align*}

where $|\mathrm{End}_{S_r}[n]|$ and $|\mathrm{Cay}_{S_r}[n]|$ are simply the number of endofunctions and Cayley permutations with $r$ recurrent points.

By substituting the number $|R[r]|$ of $R$-structures of size  $r$ into Theorem 5.3, we obtain counting formulas for the two-sort version of the species of Table 2. Using Corollary 5.5, we also obtain identities for the corresponding unisort structures listed in Table 4. A noteworthy example is a formula for the number of Cayley-derangements, the main result of this paper:

Theorem 5.6. The number of fixed-point-free Cayley permutations of $[n]$ is

\begin{equation*} |\mathrm{Cay}_{\mathrm{Der}}[n]| \,=\, \sum_{r=0}^n\frac{|\mathrm{Der}[r]|}{r!}\sum_{i=0}^ni!\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}}. \end{equation*}

Table 4.

Number of $R$-recurrent functional digraphs with  $r$ recurrent points, $i$ internal nodes and $j$ leaves.

Table 4 Long description

The table compares R-recurrent functional digraphs across several categories, including all structures, trees, forests, connected graphs, and derangements. The comparison is based on the number of recurrent points, internal nodes, and leaves, with each category defined by specific mathematical expressions. For all structures, the counting formula is given by i factorial multiplied by the r-associated Stirling number of the second kind with parameters i plus j and i. Tree structures use a modified version of this formula that includes delta subscript r comma 1. Additional formulas are provided for the cardinalities of End subscript R of n and Cay subscript R of n. The table shows that all structures correspond to n raised to the power n, while trees correspond to n raised to the power n minus 1. Forests, connected graphs, and derangements each use related expressions adapted to their structural properties. Derangements specifically incorporate the cardinality of Der subscript r in their calculations. The table highlights how different graph structures affect the enumeration and mathematical representation of recurrent functional digraphs, with references to propositions and theorems provided for additional mathematical context.

The first few numbers of this sequence are

\begin{equation*} 1, 0, 1, 4, 25, 184, 1617, 16492, 191721, 2503040, 36267393, 577560596. \end{equation*}

At the time of writing, this sequence is not in the OEIS [Reference Sloane15].

We highlight three additional noteworthy instances of Corollary 5.5 below.

Proposition 5.7. The number of Cayley permutations of $[n]$ whose functional digraph is a tree equals the number of all Cayley permutations of $[n-1]$. That is,

\begin{equation*} |\mathrm{Cay}_{X}[n]| = |\mathrm{Cay}[n-1]|. \end{equation*}

The number of Cayley permutations of $[n]$ whose functional digraph is a forest equals

\begin{align*} |\mathrm{Cay}_E[n]| &= \sum_{r=0}^n\frac{1}{r!}\sum_{i=0}^ni!\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}}. \end{align*}

The number of Cayley permutations of $[n]$ whose functional digraph is connected equals

\begin{align*} |\mathrm{Cay}_{\mathcal{C}}[n]| &= \sum_{r=1}^n\frac{1}{r}\sum_{i=0}^ni!\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}}. \end{align*}

Proof. Setting $R=X$ in Corollary 5.5 we get the first identity:

\begin{equation*} |\mathrm{Cay}_{X}[n]| = \sum_{r=0}^n\frac{|X[r]|}{r!}\sum_{i=0}^ni!\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}} = \sum_{i=0}^ni!\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{1}} = |\mathrm{Cay}[n-1]|, \end{equation*}

where in the last step $\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{1}}$ equals the $(n-1,i)$th Stirling number of the second kind. The second and third identities are immediate consequences of Corollary 5.5.

In Section 7, we generalize Joyal’s bijection between doubly-rooted trees and endofunctions to the two-sort setting.

6. Asymptotic proportion of Cayley-derangements

We opened this paper by recalling the answer to the hat-check problem: the probability that a permutation chosen uniformly at random is a derangement converges to $1/e$ as its size grows to infinity. In this section, we prove that Cayley-derangements have the same asymptotic behavior.

Theorem 6.1. Let $\mathfrak{f}(n) = |\mathrm{Cay}[n]|$ denote the $n$th Fubini number. Then

\begin{equation*} \lim_{n\to\infty} \frac{|\mathrm{Cay}_{\mathrm{Der}}[n]|}{\mathfrak{f}(n)} = \frac{1}{e}. \end{equation*}

Define

\begin{equation*} \mathfrak{f}_{r}(n) = \sum_{i \geq 0} i!\, \genfrac{\{}{\}}{0pt}{}{{n}}{{i}}_{{r}} \quad\text{and}\quad \bar{\mathfrak{f}}_{r}(n) = \sum_{i \geq 0} i!\, \genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}}. \end{equation*}

In particular, $\bar{\mathfrak{f}}_{r}(n) = \mathfrak{f}_{r}(n) - \mathfrak{f}_{r+1}(n)$, $\mathfrak{f}_{0}(n)=\mathfrak{f}(n)$ and $\bar{\mathfrak{f}}_{0}(n) = 0$. Next, define the weights

\begin{equation*} w_r = \frac{|\mathrm{Der}[r]|}{r!} = \sum_{k=0}^{r} \frac{(-1)^k}{k!}, \end{equation*}

so that Theorem 5.6 takes the form

\begin{equation*} |\mathrm{Cay}_{\mathrm{Der}}[n]| = \sum_{r\ge 0} w_r\,\bar{\mathfrak{f}}_{r}(n). \end{equation*}

Define the error $\epsilon_r = w_r - 1/e$.

Lemma 6.2. We have

\begin{equation*} \epsilon_r = \frac{(-1)^r}{(r+1)!} + O\!\left(\frac{1}{(r+2)!}\right). \end{equation*}

In particular, $|\epsilon_r| \leq 1/(r+1)!$.

Denote by

\begin{align*} p_r(n) &= \frac{\bar{\mathfrak{f}}_{r}(n)}{\mathfrak{f}(n)}\nonumber \end{align*}

the proportion of ballots in which $r$ is maximal such that $1,\ldots,r$ are in distinct blocks. Then

(16)\begin{equation} \frac{|\mathrm{Cay}_{\mathrm{Der}}[n]|}{\mathfrak{f}(n)} = \sum_{r \geq 0} w_r\, p_r(n). \end{equation}

Lemma 6.4. For all $n \geq 0$,

\begin{equation*} \frac{|\mathrm{Cay}_{\mathrm{Der}}[n]|}{\mathfrak{f}(n)} - \frac{1}{e} = \sum_{r \geq 0} \left(\frac{|\mathrm{Der}[r]|}{r!} - \frac{1}{e}\right) p_r(n) = \sum_{r \geq 0} \epsilon_r\, p_r(n). \end{equation*}

For $n \geq 2$ and distinct $a, b \in [n]$, let $S(a,b;n,i)$ denote the set of partitions of  $[n]$ into $i$ blocks in which $a$ and  $b$ lie in the same block. For instance, the set of partitions of  $[4]=\{1,2,3,4\}$ into two blocks in which $1$ and  $2$ lie in the same block is

\begin{equation*} S(1,2;4,2) = \bigl\{\, \{1,2\}\{3,4\},\; \{1,2,3\}\{4\},\; \{1,2,4\}\{3\} \,\bigr\} \end{equation*}

and by deleting $2$ from its block, we obtain all set partitions of $\{1,3,4\}$ into two blocks:

\begin{equation*} \bigl\{\, \{1\}\{3,4\},\; \{1,3\}\{4\},\; \{1,4\}\{3\} \,\bigr\}. \end{equation*}

This process is clearly invertible, and more generally, we obtain the following simple lemma.

Lemma 6.5. For $n \geq 2$ and distinct $a, b \in [n]$, set partitions of  $[n]$ into $i$ blocks in which $a$ and  $b$ lie in the same block are in one-to-one correspondence with set partitions of $[n]\setminus\{b\}$ into $i$ blocks. In particular,

\begin{equation*} \bigl|S(a,b;n,i)\bigr| = \genfrac{\{}{\}}{0pt}{}{{n-1}}{{i}}. \end{equation*}

To bound the tail $\sum_{r=0}^{K-1} p_r(n)$ that appears in the proof of Theorem 6.1, we need an upper bound on  $\mathfrak{f}(n) - \mathfrak{f}_{K}(n)$. Lemma 6.5 provides one by summing over the $\binom{K}{2}$ pairs in  $[K]$.

Lemma 6.6. For $2 \leq K \leq n$,

\begin{equation*} \mathfrak{f}(n) - \mathfrak{f}_{K}(n) \leq \binom{K}{2}\, \mathfrak{f}(n-1). \end{equation*}

Proof. The difference $\genfrac{\{}{\}}{0pt}{}{{n}}{{i}} - \genfrac{\{}{\}}{0pt}{}{{n}}{{i}}_{{K}}$ counts partitions of  $[n]$ into $i$ blocks in which at least one pair from  $[K]$ shares a block. Thus,

\begin{align*} \genfrac{\{}{\}}{0pt}{}{{n}}{{i}} - \genfrac{\{}{\}}{0pt}{}{{n}}{{i}}_{{K}} &= \Biggl|\,\bigcup_{\{a,b\} \subseteq [K]}S(a,b;n,i)\,\Biggr|\\[1ex] &\leq \sum_{\{a,b\} \subseteq [K]} |S(a,b;n,i)| \leq \binom{K}{2}\, \genfrac{\{}{\}}{0pt}{}{{n-1}}{{i}}. \end{align*}

Multiplying by $i!$ and summing over $i$ yields $\mathfrak{f}(n) - \mathfrak{f}_{K}(n) \leq \binom{K}{2}\, \mathfrak{f}(n-1)$.

The asymptotic behavior of the Fubini numbers is well known and readily obtainable from the generating series $\sum_{n \geq 0} \mathfrak{f}(n)\, x^n/n! = 1/(2 - e^x)$ by singularity analysis [Reference Flajolet and Sedgewick12].

Lemma 6.7. We have

\begin{equation*} \mathfrak{f}(n) = \frac{n!}{2(\log 2)^{n+1}} \bigl(1+O(r_1^{\,n})\bigr), \quad\text{where}\quad r_1 = \frac{\log 2}{\sqrt{(\log 2)^2+(2\pi)^2}} \lt 1. \end{equation*}

In particular, $\mathfrak{f}(n-1)/\mathfrak{f}(n) \sim (\log 2)/n \to 0$.

Proof of Theorem 6.1.

By Lemma 6.4,

\begin{equation*} \frac{|\mathrm{Cay}_{\mathrm{Der}}[n]|}{\mathfrak{f}(n)} - \frac{1}{e} = \sum_{r \geq 0} \epsilon_r\, p_r(n), \end{equation*}

where $(p_r(n))_{r \geq 0}$ is the probability distribution of Lemma 6.3 and $|\epsilon_r| \leq 1/(r+1)!$ (Lemma 6.2). Fix an integer $K \geq 2$ and apply the triangle inequality:

\begin{equation*} \left|\sum_{r \geq 0} \epsilon_r\, p_r(n)\right| \leq \sum_{r=0}^{K-1} |\epsilon_r|\, p_r(n) + \sum_{r \geq K} |\epsilon_r|\, p_r(n). \end{equation*}

Bounding $|\epsilon_r| \leq 1$ in the first sum and $|\epsilon_r| \leq 1/(K+1)!$ in the second gives

\begin{equation*} \left|\sum_{r \geq 0} \epsilon_r\, p_r(n)\right| \leq \sum_{r=0}^{K-1} p_r(n) + \frac{1}{(K+1)!}. \end{equation*}

Since $\bar{\mathfrak{f}}_{r}(n) = \mathfrak{f}_{r}(n) - \mathfrak{f}_{r+1}(n)$, the sum telescopes:

\begin{align*} \sum_{r=0}^{K-1} p_r(n) &= \frac{1}{\mathfrak{f}(n)} \sum_{r=0}^{K-1} \bigl(\mathfrak{f}_{r}(n) - \mathfrak{f}_{r+1}(n)\bigr) \\ &= \frac{\mathfrak{f}_{0}(n) - \mathfrak{f}_{K}(n)}{\mathfrak{f}(n)} = \frac{\mathfrak{f}(n) - \mathfrak{f}_{K}(n)}{\mathfrak{f}(n)}. \end{align*}

Applying Lemma 6.6 yields

\begin{equation*} \left|\frac{|\mathrm{Cay}_{\mathrm{Der}}[n]|}{\mathfrak{f}(n)} - \frac{1}{e}\right| \leq \binom{K}{2}\frac{\mathfrak{f}(n-1)}{\mathfrak{f}(n)} + \frac{1}{(K+1)!}. \end{equation*}

By Lemma 6.7, $\mathfrak{f}(n-1)/\mathfrak{f}(n) \to 0$. Given $\varepsilon \gt 0$, first choose $K$ so that $1/(K+1)! \lt \varepsilon/2$, then choose $N$ so that $\binom{K}{2} \mathfrak{f}(n-1)/\mathfrak{f}(n) \lt \varepsilon/2$ for all $n \geq N$. The result follows.

Proposition 6.8. The rate of convergence in Theorem 6.1 is

\begin{equation*} \frac{|\mathrm{Cay}_{\mathrm{Der}}[n]|}{\mathfrak{f}(n)} - \frac{1}{e} \sim -\frac{\log 2}{2en}. \end{equation*}

The proof is similar to that of Theorem 6.1 but more involved; see Appendix 10.1.

For comparison, recall from Lemma 6.2 that the analogous error for permutations is

\begin{equation*} \frac{|\mathrm{Der}[n]|}{n!} - \frac{1}{e} \sim \frac{(-1)^{n}}{(n+1)!}, \end{equation*}

which decays super-exponentially, while for endofunctions the ratio is exactly $(1-1/n)^n$ and

\begin{equation*} \left(1-\frac{1}{n}\right)^n - \frac{1}{e} \sim -\frac{1}{2en}. \end{equation*}

The Cayley-derangement and endofunction errors are both eventually negative, and since $\log 2 \lt 1$, the former is eventually smaller in magnitude. The permutation error is negligible compared to either. This gives the ordering

\begin{equation*} \frac{|\mathrm{Der}[n]|}{n!} \gt \frac{|\mathrm{Cay}_{\mathrm{Der}}[n]|}{\mathfrak{f}(n)} \gt \left(1-\frac{1}{n}\right)^n \end{equation*}

for large  $n$.

7. A two-sort species extension of Joyal’s bijection

Recall from Section 2 Joyal’s bijection between doubly-rooted trees and functional digraphs of endofunctions. It identifies the spine of a doubly-rooted tree with a nonempty permutation, leaving the rooted trees that hang from the spine untouched. This bijection implies the unisort $\mathbb{L}$-species identity

(17)\begin{equation} \mathcal{A}^{\bullet} = \mathrm{End}_+. \end{equation}

We shall extend Joyal’s construction to the two-sort case by revealing a link between functional digraphs $\Psi_{\mathcal{S}}$ and rooted trees $\Psi_X=\mathcal{A}(X,Y)$. In the proof of Theorem 5.1, we showed that

\begin{equation*} \displaystyle{\frac{\partial{\Psi_X}}{\partial Y}} = L_+\bigl(\Psi_X\bigr). \end{equation*}

Assuming $\mathbb{L}$-species, we have $L=\mathcal{S}$ and hence $L_+(\mathcal{A}) = \mathcal{S}_+(\mathcal{A})=\Psi_{\mathcal{S}_+}$. That is,

(18)\begin{equation} \displaystyle{\frac{\partial{\Psi_X}}{\partial Y}}=\Psi_{\mathcal{S}_+}. \end{equation}

We have found a combinatorial proof of (18) in the spirit of Joyal’s proof of (17). On the left-hand side, we have a rooted tree of two sorts with an additional leaf. Define its spine as the path from this leaf to the root. Ignoring the initial leaf, this path is a nonempty linear order of (internal) nodes of sort  $X$, where a rooted tree of two-sorts hangs from each of its nodes. Identifying the spine with a permutation in the usual way yields a nonempty permutation of rooted trees, that is, a structure of $\mathcal{S}_+\circ\Psi_X=\Psi_{\mathcal{S}_+}$, the species on the right-hand side. In other words, the additional leaf of a structure of $(\partial/\partial Y)\Psi_X$ plays the role of tail, while the root plays the role of head. A two-sort vertebrate is born in the process, and by reading a permutation off its spine, we obtain a permutation of rooted trees of two sorts; that is, a structure of $\Psi_{\mathcal{S}_+}$. This construction – an instance of which can be found in Figure 6 – is easily invertible, and thus it yields a combinatorial proof of equation (18).

Figure 6.

A rooted tree of two sorts with an additional leaf, denoted $y^\star$, and the corresponding functional digraph under the extension of Joyal’s construction. The spine of the tree, dashed in blue, is the linear order $5243$; it is mapped to the recurrent part of the functional digraph on the right.

Figure 6 Long description

The left diagram shows a rooted tree with nodes labeled a, b, c, d and e. The spine of the tree is a linear order from y superscript star to node three, with nodes labeled five, two and four along the path. Node five connects to nodes one, a and b. Node four connects to nodes c and e. The right diagram shows a functional digraph with nodes labeled one to five. Node two forms a loop with node three, which connects to node d. Node five connects to nodes one, a and b. Node four connects to nodes c and e.

8. Unisort species of Cayley functional digraphs

In this section, we build on the enumerative results obtained for $\Psi_R$ in the two-sort case to obtain species equations for its unisort counterpart $\mathrm{Cay}_R$. These rely on the ordinal product of $\mathbb{L}$-species, defined as

\begin{equation*} (F \odot G)[\ell] \,= \sum_{\ell=\ell_1 \oplus \ell_2} F[\ell_1] \times G[\ell_2]. \end{equation*}

An $F\odot G$- structure is thus obtained by putting an $F$-structure on the initial segment $\ell_1$ and a $G$-structure on the terminal segment $\ell_2$.

We shall use $\mathbb{L}$-species to show that

\begin{equation*} \mathrm{Cay}_R =\frac{1}{2}\sum_{r\ge 0} R_r\odot(1+E^r\mathrm{Bal}^r). \end{equation*}

This specializes to give expressions for the unisort species of Cayley-derangements and the other species in Table 2:

(19)\begin{equation} \mathrm{Cay}_{\mathrm{Der}} =\frac{1}{2}\sum_{r\ge 0} \mathrm{Der}_r\odot\left(1+E^r\mathrm{Bal}^r\right). \end{equation}

Let us start with a simple lemma.

Lemma 8.1. For $r\ge 1$, we have

\begin{equation*} \sum_{i\ge 0}i!\cdot\genfrac{\{}{\}}{}{}{{n+r+1}}{{i}}_{{r}} =r!\cdot r\cdot |\bigl(E^r\mathrm{Bal}^{r+1}\bigr)[n]|. \end{equation*}

Proof. The left-hand side counts ballots of $[n+r+1]$ with  $i$ blocks, where  $r$ is maximal such that $1,\dots,r$ are contained in distinct blocks. Any such ballot is structured

\begin{equation*} \beta_1\;\{u_1,\ldots \}\; \beta_2\;\{u_2,\ldots \}\; \dots\; \beta_r\;\{u_r,\ldots\}\; \beta_{r+1}, \end{equation*}

where $u_1u_2\dots u_r$ is a permutation of $1,\ldots,r$ and the $\beta_i$’s are ballots filling the space between the blocks containing the $u_i$’s. The permutation of $1,\ldots,r$ gives the $r!$ term on the right-hand side. Since $r+1$ belongs to one of the blocks containing the $u_i$’s, we have  $r$ choices to arrange it. Finally, the remaining elements, $r+2,r+3,\ldots,n+r+1$, are arranged in a structure of $E^r\cdot\mathrm{Bal}^{r+1}$ (of size $n$): elements in the same block as some $u_j$ determine an $E^r$-structure, while the other elements determine the ballots $\beta_1,\dots,\beta_{r+1}$, that is, a structure of $\mathrm{Bal}^{r+1}$.

Theorem 8.2. We have the $\mathbb{L}$-species identity

\begin{equation*} \mathrm{Cay}_{R} = R + \sum_{r\ge 1} (R_r)^{\bullet}\odot\left(\int E^r\mathrm{Bal}^{r+1}\right). \end{equation*}

Proof. Let $F$ denote the species on the right-hand side. To prove the desired $\mathbb{L}$-species identity, it suffices to show that $|F[n]|=|\mathrm{Cay}_{R}[n]|$ for $n\ge 0$. Expanding the definition of  $F$ yields

\begin{align*} |F[n]| &= |R[n]| + \sum_{r=1}^n |R^{\bullet}[r]|\cdot \left|\left(\int E^r\mathrm{Bal}^{r+1}\right)[n-r]\right|\\ &= |R[n]| + \sum_{r=1}^{n-1} r|R[r]|\cdot \left|\left(E^r\mathrm{Bal}^{r+1}\right)[n-r-1]\right|\cdot\frac{r!}{r!}\\ &= |R[n]| + \sum_{r=1}^{n-1}\frac{|R[r]|}{r!}\sum_{i\ge 0}i!\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}} && \text{(by Lemma~8.1)}\\ &= \sum_{r=1}^{n}\frac{|R[r]|}{r!}\sum_{i\ge 0}i!\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}} \\ &=|\mathrm{Cay}_{R}[n]| && \text{(by Corollary~5.5)} \end{align*}

where in the penultimate equality we used that the term corresponding to $r=n$ in the summation equals

\begin{equation*} \frac{|R[n]|}{n!}\sum_{i\ge 0}i!\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{n}} = \frac{n!|R[n]|}{n!}\genfrac{\{}{\}}{}{}{{n}}{{n}}_{{n}} = |R[n]|. \end{equation*}

This concludes the proof.

An arguably simpler species equation for $\mathrm{Cay}_R$ is provided in the next result.

Corollary 8.3. We have

\begin{equation*} \mathrm{Cay}_R =\frac{1}{2}\sum_{r\ge 0} R_r\odot\left(1+E^r\mathrm{Bal}^r\right). \end{equation*}

Proof. The $\mathbb{L}$-species identity

(20)\begin{equation} \int E^r\mathrm{Bal}^{r+1}=\frac{1}{2r}(E^r\mathrm{Bal}^r-1). \end{equation}

is easily verified using differentiation and the species version of the fundamental theorem of calculus. Next,

\begin{align*} \mathrm{Cay}_{R} &= R + \sum_{r\ge 1} (R_r)^{\bullet}\odot\left(\int E^r\mathrm{Bal}^{r+1}\right) && \text{(by Theorem~8.2)}\\ &= \sum_{r\ge 0} R_r+(R_r)^{\bullet}\odot\left(\int E^r\mathrm{Bal}^{r+1}\right) && \text{(since}\ R=\sum_{r\ge 0}R_r \& R^{\bullet}_0=\emptyset\text{)}\\ &= \sum_{r\ge 0} R_r+rR_r\odot\frac{1}{2r}(E^r\mathrm{Bal}^r-1) && \text{(by equation~(20))}\\ &= \frac{1}{2}\sum_{r\ge 0} R_r\odot\left(1+E^r\mathrm{Bal}^r\right), \end{align*}

where the last identity follows by $R_r=R_r\odot 1$ and linearity of $\odot$.

Finding a combinatorial proof of this corollary remains an open problem.

9. Statistics and asymptotics

Theorem 5.3 provides a closed formula for the number of $\Psi_R$-structures with  $i$ internal nodes, among which  $r$ are recurrent, and  $j$ leaves. By suitably summing over  $r$, $i$ and  $j$, we obtain the distribution of each of these statistics over $R$-recurrent functional digraphs. For instance, the number of $R$-recurrent functional digraphs with  $n$ nodes and  $r$ recurrent points is

\begin{equation*} \sum_{i+j=n}|\Psi_{R_r}[i,j]| =\frac{|R[r]|}{r!}\sum_{i=0}^ni!\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}}. \end{equation*}

The distributions of internal nodes and leaves are obtained similarly. The total number of recurrent points, internal nodes, and leaves can be computed in the same fashion by multiplying the term inside the summation by  $r$, $i$ or  $j$. An example is the total number of recurrent points over $\Psi_R$-structures on $[i,j]$:

\begin{equation*} \sum_{r=0}^i|\Psi_{R_r}[i,j]|\cdot r =\sum_{r=0}^i\frac{|R[r]|}{r!}i!\genfrac{\{}{\}}{}{}{{i+j}}{{i}}_{{r}}\cdot r. \end{equation*}

Multiplying by  $r$ has the same effect as pointing to the $R$-structure. This gives us an elegant species expression for the total number of recurrent points:

(21)\begin{equation} \Psi_{R^{\bullet}}(X,Y),\; \text{where } |\Psi_{R^{\bullet}}[i,j]| =\sum_{r=0}^i|\Psi_{R_r}[i,j]|\cdot r. \end{equation}

If two species $F$ and $G$ are related by $F=E(G)$, with $G(0)=0$, then  $G$ is said to be the species of connected $F$-structures. In this sense, an $F$-structure is a set of $G$-structures each of which is called a connected component. We are by now familiar with the species of connected permutations, that is, cycles $\mathcal{C}$ where $\mathcal{S}=E(\mathcal{C})$. Not every species admits a notion of connected structure in the realm of $\mathbb{B}$-species, but it is always possible [Reference Bergeron, Labelle and Leroux2, Proposition 18], under the assumption $F(0)=1$, to construct a virtual species  $G$ such that $F=E(G)$. The species  $G$ is uniquely determined and is called the combinatorial logarithm of  $F$, denoted by $G=\log F$.

For any unisort species $R$ such that $R(0)=1$, we define the two-sort species of connected $R$-recurrent functional digraphs by letting the recurrent part be equal to the logarithm of  $R$:

\begin{equation*} \Psi_{\log R}(X,Y). \end{equation*}

Pointing to the $E$-structure in $E(\log R)=R$ has the effect of multiplying by the number of connected components. Therefore, the total number of connected components over $\Psi_R$-structures is obtained as $\Psi_{E^{\bullet}(\log R)}$. Note that $E^{\bullet}(X)=X\cdot E(X)$, from which

(22)\begin{equation} E^{\bullet}(\log R)=R\cdot\log R \quad\text{and}\quad \Psi_{E^{\bullet}(\log R)} = \Psi_{R\log R} \end{equation}

follows. Finally, Theorem 5.3 gives the total number of connected components over $\Psi_R$-structures on $[i,j]$:

(23)\begin{equation} \sum_{r=0}^i|\Psi_{R\log R}[i,j]| =\sum_{r=0}^i\frac{|(R\log R)[r]|}{r!}i!\genfrac{\{}{\}}{}{}{{i+j}}{{i}}_{{r}}. \end{equation}

To illustrate the techniques introduced in this section, we will show that permutations, Cayley permutations, and endofunctions share the following property:

The total number of recurrent points over connected structures of a given size equals the total number of structures of that size.

First, we consider permutations. There are $(n-1)!$ connected permutations (cycles) of size  $n\geq 1$. Since every point in a permutation is recurrent, the total number of recurrent points over connected structures is $(n-1)!\cdot n=n!=|\mathcal{S}[n]|$. To deal with Cayley permutations and endofunctions, we use the species of connected functional digraphs, $\Psi_{\mathcal{C}}$. Since $\mathcal{C}'=L$, we find that $\mathcal{C}^{\bullet} = X\cdot \mathcal{C}' = X\cdot L = L_+$. Thus, the total number of recurrent points over $\Psi_{\mathcal{C}}$ is given by

\begin{align*} |\Psi_{\mathcal{C}^{\bullet}}[i,j]| &=|\Psi_{L_+}[i,j]| =|\Psi_{\mathcal{S}_+}[i,j]|. \end{align*}

Finally, we translate the previous identity to functional digraphs of Cayley permutations and endofunctions to establish the desired property:

\begin{align*} |\mathrm{End}_{\mathcal{C}^{\bullet}}[n]| &=|\mathrm{End}_{\mathcal{S}}[n]|=|\mathrm{End}[n]|;\\ |\mathrm{Cay}_{\mathcal{C}^{\bullet}}[n]| &=|\mathrm{Cay}_{\mathcal{S}}[n]|=|\mathrm{Cay}[n]|. \end{align*}

The crucial property that makes the above derivation work is $\mathcal{C}^{\bullet} \equiv \mathcal{S}_+$. In other words, the species $F=\mathcal{S}_+$ satisfies $(\log F)^{\bullet}\equiv F_+$. The solutions to this differential equation are precisely the $k$-colored permutations. That is, $F \equiv \mathcal{S}(kX)$ for some positive integer $k$.

Next, we consider the total number of cycles/connected components over structures in $\Psi_{\mathcal{S}}[i,j]$. It is simply obtained by letting $R=\mathcal{S}$ in equation (22), where $E^{\bullet}(\log\mathcal{S})=E^{\bullet}(\mathcal{C})$ gives the total number of cycles over all permutations. It is well known that the average number of cycles over permutations of $[n]$ is the $n$th harmonic number $H_{n}=\sum_{k=1}^n 1/k$. To see this, note that $E^{\bullet}(\mathcal{C})=\mathcal{S}\cdot\log(\mathcal{S})=\mathcal{S}\cdot\mathcal{C}$ and

\begin{equation*} E^{\bullet}(\mathcal{C})(x) =\bigl(\mathcal{S}\cdot\mathcal{C}\bigr)(x) =\frac{1}{1-x}\cdot\log\left(\frac{1}{1-x}\right). \end{equation*}

Therefore,

\begin{equation*} \bigl|E^{\bullet}(\mathcal{C})[n]\bigr| =\bigl|(\mathcal{S}\cdot\mathcal{C})[n]\bigr| =\sum_{k=1}^n\binom{n}{k}(n-k)!(k-1)!=n!H_{n}. \end{equation*}

Now, by identity (23), the total number of cycles over $\Psi_{\mathcal{S}}$-structures on $[i,j]$ is

\begin{equation*} |\Psi_{\mathcal{S}\log\mathcal{S}}[i,j]| =i!\sum_{r=0}^i\frac{r!H_{r}}{r!}\genfrac{\{}{\}}{}{}{{i+j}}{{i}}_{{r}} =i!\sum_{r=0}^iH_{r}\genfrac{\{}{\}}{}{}{{i+j}}{{i}}_{{r}}. \end{equation*}

Corollary 5.5 yields the total number of cycles over endofunctions (see A190314 [Reference Sloane15]) and Cayley permutations of size  $n$:

\begin{align*} |\mathrm{End}_{E^{\bullet}(\mathcal{C})}[n]| &=\sum_{i=0}^n(n)_{i}\sum_{r=0}^iH_{r}\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}};\\ |\mathrm{Cay}_{E^{\bullet}(\mathcal{C})}[n]| &=\sum_{i=0}^n\,i!\,\sum_{r=0}^iH_{r}\genfrac{\{}{\}}{}{}{{n}}{{i}}_{{r}}. \end{align*}

The first few numbers of the latter sequence are

\begin{equation*} 0, 1, 4, 20, 126, 966, 8754, 91686, 1090578, 14528502, 214337874, 3469418646. \end{equation*}

At the time of writing, this sequence is not in the OEIS [Reference Sloane15].

The average number of cycles over $\mathrm{End}[n]$ is asymptotic to $\frac{1}{2}(\log (2n)+\gamma)$, where Euler’s constant $\gamma$ is defined as the limiting difference between the harmonic series and the natural logarithm. What is the corresponding limit for the average number of cycles over Cayley permutations? Is there a generalization of Euler’s constant for the average number of cycles over $R$-recurrent functional digraphs?

10. Generalizations

Equation (10) in Section 5 characterizes the two-sort species $\Psi_R$. There, linear orders determine the shape of the branches – $L(X)\cdot Y$ – that are recursively appended to the recurrent part to obtain $\Psi_R$-structures. Replacing  $L$ with any unisort species  $T$ allows us to manipulate the shape of these branches. Define the species $\Psi_{R,T}(X,Y)$ accordingly as the solution to the system of combinatorial equations

\begin{equation*} \displaystyle{\frac{ \partial }{\partial Y}}\Psi_{R,T}(X,Y) = T(X)\cdot\Psi_{R,T}^{\bullet_X}(X,Y),\qquad \Psi_{R,T}(X,0)=R(X). \end{equation*}

For instance, if we let $T=1$ be the species characteristic of the empty set, then we obtain structures where all the leaves have distance one from a recurrent point (since each branch $T(X)\cdot Y=Y$ consists of a single leaf). Letting $R=E$, we end up with a ‘brush-shaped’ endofunction, that is, a set of roots (of sort  $X$) to each of which is appended a set of leaves (of sort  $Y$):

Note that

\begin{equation*} \Psi_{E,1}(X,Y)=E\bigl(X\cdot E(Y)\bigr). \end{equation*}

The corresponding endofunctions of $\mathrm{End}_{E,1}$ and Cayley permutations of $\mathrm{Cay}_{E,1}$ are precisely those  $f$ such that $f^{(2)}=f$, where $f^{(2)}=f\circ f$ denotes the composition of  $f$ with itself (see also A000248 and A026898 [Reference Sloane15]). In other words, $\Psi_{E,1}$ is the species of idempotent functional digraphs of two-sorts.

Let us push this construction a bit further. Setting $R=\mathcal{S}$ has the effect of allowing cycles of any length, yielding maps  $f$ where $f^{(k)}=f$ for some $k \gt 1$; in this case,

\begin{equation*} \Psi_{\mathcal{S},1}(X,Y)=\mathcal{S}\bigl(X\cdot E(Y)\bigr). \end{equation*}

In the same spirit, we fix $k$ and let

\begin{equation*} R=E\circ\sum_{i|k}\mathcal{C}_i \end{equation*}

be the species of permutations whose cycle lengths divide  $k$. Then $\Psi_{R,1}$ yields maps $f$ such that $f^{(k+1)}=f$. What other choices of $R$ and $T$ lead to interesting examples?

In Section 4, we have defined the two-sort species $\Psi_R=R\circ\mathcal{A}$ whose structures are obtained by arranging a set of rooted trees in an $R$-structure. We can tweak this definition by replacing rooted trees with any other class of trees. For instance, let $\mathcal{B}=\mathcal{B}(X,Y)$ be the two-sort species of rooted trees where each node has at most two (unordered) children. They are obtained as

\begin{equation*} \mathcal{B}(X,Y) = X\cdot \Bigl(\bigl( 1 + X + E_2\bigr) \circ \bigl(\mathcal{B}(X,Y) - X + Y\bigr)\bigr). \end{equation*}

Then, $\mathcal{S}\circ\mathcal{B}(X,Y)$ yields functional digraphs where each recurrent point has indegree at most three, and each nonrecurrent point has indegree at most two. In the corresponding endofunctions and Cayley permutations, obtained as usual via (6) and (8), recurrent points have at most three preimages, and nonrecurrent points have at most two preimages (see also A201996 [Reference Sloane15]). More generally, rooted trees where each node has at most $k$ children

\begin{equation*} \mathcal{K}(X,Y) = X\cdot \Bigl(\bigl( 1 + X + E_2 + \cdots + E_k\bigr) \circ \bigl(\mathcal{K}(X,Y) - X + Y\bigr)\bigr) \end{equation*}

determine maps where recurrent points have at most $k+1$ preimages and nonrecurrent points have at most  $k$ preimages. What can we say about other classes of trees and choices of $R$?

10.1. Proof of Proposition 6.8

Recall that Proposition 6.8 refines Theorem 6.1 by giving the rate of convergence. We establish five preparatory lemmas before giving the proof. The key ingredients are a bound on pairwise intersections of the sets $S(a,b;n,i)$ introduced before Lemma 6.5, a uniform estimate on  $p_r(n)$ obtained via inclusion–exclusion, and an explicit series evaluation.

Truncating the inclusion–exclusion formula for a finite union $\bigcup_{j=1}^{M} A_j$ after the first or second term yields, respectively, an upper and a lower bound:

\begin{equation*} \sum_{j=1}^{M} |A_j| - \sum_{1 \leq j \lt k \leq M} |A_j \cap A_k| \leq \biggl|\,\bigcup_{j=1}^{M} A_j\,\biggr| \leq \sum_{j=1}^{M} |A_j|. \end{equation*}

These are known as the first two Bonferroni inequalities. To apply them in our setting, we need to control pairwise intersections, which is the purpose of the next lemma. Recall that $S(a,b;n,i)$ denotes the set of partitions of  $[n]$ into $i$ blocks in which $a$ and  $b$ lie in the same block (defined before Lemma 6.5).

Lemma 10.1. For $n \geq 3$ and distinct $2$-element subsets $\{a,b\}, \{c,d\} \subseteq [n]$, and for all $i\ge 0$,

\begin{equation*} |S(a,b;n,i) \cap S(c,d;n,i)| \leq \genfrac{\{}{\}}{0pt}{}{{n-2}}{{i}}. \end{equation*}

With the intersection bound in hand, we can obtain a uniform estimate on  $p_r(n)$. We first record the Fubini ratios that will be needed.

Lemma 10.2. With $r_1$ as in Lemma 6.7,

\begin{align*} \frac{\mathfrak{f}(n-1)}{\mathfrak{f}(n)} =\frac{\log 2}{n}\Bigl(1+O(r_1^{\,n})\Bigr) \quad & \text{and} \quad \frac{\mathfrak{f}(n-2)}{\mathfrak{f}(n)} =\frac{(\log 2)^2}{n(n-1)}\Bigl(1+O(r_1^{\,n})\Bigr). \end{align*}

Since $r_1^{\,n} = o(1/n^2)$, these give

\begin{align*} \frac{\mathfrak{f}(n-1)}{\mathfrak{f}(n)} = \frac{\log 2}{n} + O\!\left(\frac{1}{n^2}\right) \quad & \text{and} \quad \frac{\mathfrak{f}(n-2)}{\mathfrak{f}(n)} = O\!\left(\frac{1}{n^2}\right). \end{align*}

Proof. By Lemma 6.7, $\mathfrak{f}(n) = \frac{1}{2} n!(\log 2)^{-n-1} \bigl(1+O(r_1^{\,n})\bigr)$, so

\begin{equation*} \frac{\mathfrak{f}(n-1)}{\mathfrak{f}(n)} = \frac{(n-1)!\,(\log 2)^{n+1}} {n!\,(\log 2)^{n}} \cdot \frac{1+O(r_1^{\,n})}{1+O(r_1^{\,n})} = \frac{\log 2}{n}\Bigl(1+O(r_1^{\,n})\Bigr), \end{equation*}

and similarly for $\mathfrak{f}(n-2)/\mathfrak{f}(n)$.

Lemma 10.3. As $n\to\infty$, uniformly for $0 \leq r \leq n$,

\begin{equation*} p_r(n) = \frac{r\log 2}{n} + O\!\left(\frac{r^4}{n^2}\right). \end{equation*}

In other words, there exists a constant $C \gt 0$ such that for all sufficiently large  $n$, $|p_r(n) - r\log 2/n| \leq C\,r^4/n^2$ for every $0 \leq r \leq n$.

Proof. As in the proof of Lemma 6.6, $\genfrac{\{}{\}}{0pt}{}{{n}}{{i}} - \genfrac{\{}{\}}{0pt}{}{{n}}{{i}}_{{r}} = \bigl|\bigcup_{\{a,b\} \subseteq [r]} S(a,b;n,i)\bigr|$, a union of $M = \binom{r}{2}$ sets. By Lemma 6.5, each has size $\genfrac{\{}{\}}{0pt}{}{{n-1}}{{i}}$, and by Lemma 10.1, each pairwise intersection has size at most $\genfrac{\{}{\}}{0pt}{}{{n-2}}{{i}}$. The Bonferroni inequalities, therefore, give

\begin{equation*} M\,\genfrac{\{}{\}}{0pt}{}{{n-1}}{{i}} - \binom{M}{2}\genfrac{\{}{\}}{0pt}{}{{n-2}}{{i}} \leq \genfrac{\{}{\}}{0pt}{}{{n}}{{i}} - \genfrac{\{}{\}}{0pt}{}{{n}}{{i}}_{{r}} \leq M\,\genfrac{\{}{\}}{0pt}{}{{n-1}}{{i}}. \end{equation*}

In particular, $\genfrac{\{}{\}}{0pt}{}{{n}}{{i}} - \genfrac{\{}{\}}{0pt}{}{{n}}{{i}}_{{r}}$ differs from $M\,\genfrac{\{}{\}}{0pt}{}{{n-1}}{{i}}$ by at most $\binom{M}{2}\,\genfrac{\{}{\}}{0pt}{}{{n-2}}{{i}}$. Since $\sum_i i!\,\genfrac{\{}{\}}{0pt}{}{{m}}{{i}} = \mathfrak{f}(m)$, multiplying by  $i!$ and summing over  $i$ gives

\begin{align*} \mathfrak{f}(n) - \mathfrak{f}_{r}(n) &= M\,\mathfrak{f}(n-1) + O\bigl(\tbinom{M}{2}\,\mathfrak{f}(n-2)\bigr) \\ &= \binom{r}{2}\,\mathfrak{f}(n-1) + O\bigl(r^4\,\mathfrak{f}(n-2)\bigr), \end{align*}

where the second equality substitutes $M = \binom{r}{2}$ and $\binom{M}{2} \leq r^4/8$.

To pass from $\mathfrak{f}_{r}(n)$ to $\bar{\mathfrak{f}}_{r}(n)$, we compute

\begin{align*} \bar{\mathfrak{f}}_{r}(n) &= \mathfrak{f}_{r}(n) - \mathfrak{f}_{r+1}(n) \\ &= (\mathfrak{f}(n) - \mathfrak{f}_{r+1}(n)) - (\mathfrak{f}(n) - \mathfrak{f}_{r}(n)) \\ &= \binom{r+1}{2}\mathfrak{f}(n-1) - \binom{r}{2}\mathfrak{f}(n-1) + O(r^4\,\mathfrak{f}(n-2)) \\ &= r\,\mathfrak{f}(n-1) + O\bigl(r^4\,\mathfrak{f}(n-2)\bigr). \end{align*}

Dividing by $\mathfrak{f}(n)$ gives

\begin{equation*} p_r(n) = r\,\frac{\mathfrak{f}(n-1)}{\mathfrak{f}(n)} + O\!\left(r^4\,\frac{\mathfrak{f}(n-2)}{\mathfrak{f}(n)}\right). \end{equation*}

By Lemma 10.2, the second term is $O(r^4/n^2)$, while the first is $r\log 2/n + O(r/n^2)$. Since $r \leq r^4$ for $r \geq 1$ and both sides vanish for $r = 0$, the result follows.

It remains to evaluate the series $\sum r\,\epsilon_r$ that will arise when we substitute the estimate of Lemma 10.3.

Proof. By Lemma 6.4, $\epsilon_r = -\sum_{k \geq r+1} (-1)^k/k!$, so

\begin{equation*} \sum_{r \geq 0} r\,\epsilon_r = -\sum_{r \geq 0}\, \sum_{k \geq r+1} \frac{r\,(-1)^k}{k!}. \end{equation*}

Since $\sum_{r \geq 0} r\,|\epsilon_r| \lt \infty$, we may interchange the order of summation. The sum over  $r$ then runs from  $0$ to  $k-1$, contributing $\sum_{r=0}^{k-1} r = \binom{k}{2}$, which vanishes for $k \leq 1$. Thus

\begin{equation*} \sum_{r \geq 0} r\,\epsilon_r = -\sum_{k \geq 2} \frac{(-1)^k}{k!} \binom{k}{2} = -\frac{1}{2}\sum_{k \geq 2} \frac{(-1)^k}{(k-2)!} = -\frac{1}{2}\sum_{j \geq 0} \frac{(-1)^j}{j!} = -\frac{1}{2e}. \end{equation*}

Finally, we verify that the splitting point $K = \lfloor \log n \rfloor$ grows fast enough for the tail to be negligible.

Proof of Proposition 6.8.

By Lemma 6.4, it suffices to show that $\sum_{r=0}^{n} \epsilon_r\, p_r(n) \sim -\log 2/(2en)$. We split at $K = \lfloor\log n\rfloor$:

\begin{equation*} \sum_{r=0}^{n} \epsilon_r\, p_r(n) = \sum_{r=0}^{K-1} \epsilon_r\, p_r(n) + \sum_{r=K}^{n} \epsilon_r\, p_r(n). \end{equation*}

For the tail, $|\epsilon_r| \leq 1/(r+1)! \leq 1/(K+1)!$ for all $r \geq K$, and $\sum_{r=0}^{n} p_r(n) = 1$, so $\bigl|\sum_{r=K}^{n} \epsilon_r\, p_r(n)\bigr| \leq 1/(K+1)! = o(1/n)$ by Lemma 10.5.

For the main sum, Lemma 10.3 gives $p_r(n) = r\log 2/n + O(r^4/n^2)$ for each $0 \leq r \leq K$. Substituting,

(24)\begin{equation} \sum_{r=0}^{K-1} \epsilon_r\, p_r(n) = \frac{\log 2}{n}\sum_{r=0}^{K-1} r\,\epsilon_r + O\!\left(\frac{1}{n^2}\right), \end{equation}

where the error uses $\sum_{r \geq 0} r^4\,|\epsilon_r| \leq \sum_{r \geq 0} r^4/(r+1)! \lt \infty$. Since also $\sum_{r \geq 0} r\,|\epsilon_r| \lt \infty$, the partial sum $\sum_{r=0}^{K-1} r\,\epsilon_r$ can be completed to the full series $\sum_{r \geq 0} r\,\epsilon_r$ at the cost of an error $\sum_{r \geq K} r\,|\epsilon_r| = O(1/K!) = o(1)$. Applying Lemma 10.4 and collecting errors,

\begin{equation*} \sum_{r=0}^{n} \epsilon_r\, p_r(n) = -\frac{\log 2}{2en} + o\!\left(\frac{1}{n}\right). \end{equation*}

Indeed, the three error terms are all $o(1/n)$: the tail is $o(1/n)$ by Lemma 10.5, the error in (24) is $O(1/n^2) = o(1/n)$, and completing the series costs $O(1/(nK!)) = o(1/n)$ since $1/K! = o(1)$. This establishes Proposition 6.8.