theoremequation theorem dodecaequation dodeca propequation prop lemmaequation
lemma corollaryequation corollary claimequation claim conjectureequation
conjecture questionequation question defnequation defn exampleequation example
computationequation computation constructionequation construction
remarkequation remark conventionequation convention

# The combinatorics of $N_{\infty}$ operads for $C_{qp^{n}}$ and $D_{p^{n}}$

Scott Balchin  Max Planck Institute for Mathematics<EMAIL_ADDRESS>,  Ethan MacBrough  Reed College<EMAIL_ADDRESS>and  Kyle Ormsby  Reed
College / University of Washington<EMAIL_ADDRESS>/<EMAIL_ADDRESS>
###### Abstract.

We provide a general recursive method for constructing transfer systems on
finite lattices. Using this we calculate the number of homotopically distinct
$N_{\infty}$ operads for dihedral groups $D_{p^{n}}$, $p>2$ prime, and cyclic
groups $C_{qp^{n}}$, $p\neq q$ prime. We then further display some of the
beautiful combinatorics obtained by restricting to certain homotopically
meaningful $N_{\infty}$ operads for these groups.

###### Contents

  1. 1 Introduction
  2. 2 Transfer systems and a generalized $\odot$ construction
  3. 3 Enumerating transfer systems for $D_{p^{n}}$
  4. 4 Enumerating transfer systems for $C_{qp^{n}}$
  5. 5 Restricted Tamari intervals
  6. 6 Maximally extendable $D_{p^{n}}$ transfer systems and Schröder numbers

##  1\. Introduction

Throughout, $D_{p^{n}}$ denotes the dihedral group of order $2p^{n}$, $p>2$
prime, and $C_{qp^{n}}$ the cyclic group of order $qp^{n}$, for $q,p$ distinct
primes. (We allow $p=2$ in the cyclic case.)

This paper — at its heart — is concerned with the combinatorical data arising
when studying commutative $G$-equivariant spectra for $G$ either $D_{p^{n}}$
or $C_{qp^{n}}$. In particular, we wish to study the set of $N_{\infty}$
operads for these groups, as introduced by Blumberg–Hill [BH15], which govern
the ways in which the commutativity respects the group action.

Such an exploration of $N_{\infty}$ operads for $G=C_{p^{n}}$ was undertaken
in [BBR21], where it was proved that the collection of these operads (up to
homotopy) was in bijection with the Tamari lattice, and in particular, there
are $\mathrm{Cat}(n+1)$ many of them, where $\mathrm{Cat}(k)$ is the $k$-th
Catalan number. This was achieved using an explicit representation of
$N_{\infty}$ operads as combinatorial structures called _transfer systems_ on
the subgroup lattice of $C_{p^{n}}$. As such, one is led to study transfer
systems on arbitrary finite lattices. We refer the reader to [FOO+22, §4] and
Section 2 for definitions in this context.

Note that the subgroup lattice for $C_{p^{n}}$ is isomorphic to
$[n]=\\{0<1<\cdots<n\\}$. A key method employed in [BBR21] was a recursive
method for building all transfer systems on $[n]$ from ones on $[i]$ where
$i<n$. It is this powerful point of view that we will generalize in this
paper. In particular, in Section 2 we shall exhibit an extremely general
method of iteratively building all transfer systems on a finite lattice $L$.

We will then implement the algorithm of Section 2 in the case of
$L=[1]\times[n]$. From a homotopical viewpoint, we observe that
$[1]\times[n]\cong\operatorname{Sub}(C_{qp^{n}})$, and as such, transfer
systems on $[1]\times[n]$ correspond to $N_{\infty}$ operads for $C_{qp^{n}}$.
To do so, we will first begin by considering a restricted collection of
transfer systems, namely the _liftable_ transfer systems (Section 3). From the
work of the authors in [BMO22], liftable transfer systems on $[1]\times[n]$
are in bijection with $N_{\infty}$ operads for $D_{p^{n}}$ (provided $p\neq
2$). A recursive formula for computing the number of liftable transfer systems
appears as the main result in Section 3.

We are then able to exploit the self duality of transfer systems on
$[1]\times[n]$ as observed in [FOO+22] to complete the computation for
$C_{qp^{n}}$ almost immediately from the case of $D_{p^{n}}$. This leads to
Section 4 where we provide a recursive formula for computing the number of
transfer systems on $[1]\times[n]$.111Python code for computing the number of
$N_{\infty}$ operads for $C_{qp^{n}}$ and $D_{p^{n}}$ using the results of
this paper can be found at https://github.com/bifibrant/recursion/.

Following these enumerative results, we begin to explore some of the
combinatorial structures appearing in the recursions that we have provided. In
Section 5 we study the notion of _restricted Tamari intervals_ , which form an
important part of the recursions for $C_{qp^{n}}$ and $D_{p^{n}}$, and see
that this is related to certain triangulations of polygons.

Finally, in Section 6 we will restrict ourselves to what we call _maximally
extendable_ transfer systems. In terms of the lattice $[1]\times[n]$, these
are those transfer systems whose restriction to the bottom row is the maximal
transfer system on $[n]$. We shall see that in the liftable case these have
specific combinatorial interpretation (in terms of large Schröder numbers),
and we make a conjecture relating the general case to rooted subtrees of a
rooted planar tree. Returning to the world of homotopy theory, these maximally
extendable transfer systems have a meaninful interpretation. Indeed, they are
precisely those transfer systems cooresponding to $N_{\infty}$ operads which
restrict to the genuine $G$-$E_{\infty}$ operad on $C_{p^{n}}$.

### Acknowledgements

The authors thank Mike Hill for suggesting the construction presented in
Section 2.

The first author would like to thank the Max Planck Institute for Mathematics
for its hospitality, and was partially supported by the European Research
Council (ERC) under Horizon Europe (grant No. 101042990). The second author
thanks Coil Technologies for their generous donation to fund his tuition,
which enabled him to conduct this research. The third author’s work was
supported by the National Science Foundation under Grant No. DMS-2204365.

##  2\. Transfer systems and a generalized $\odot$ construction

We begin by recalling the definition of a transfer system on a poset from
[FOO+22].

######  Definition .

Let $\mathcal{P}=(\mathcal{P},\leqslant)$ be a poset. A (categorical)
_transfer system_ on $\mathcal{P}$ consists of a partial order $\mathcal{R}$
on $\mathcal{P}$ that refines $\leqslant$ and such that for all
$x,y,z\in\mathcal{P}$, if $x\,\mathcal{R}\,y$, $z\leqslant y$, and $x\wedge y$
exists, then $(x{\wedge}z)\,\mathcal{R}\,z$. We denote by
$\mathsf{Tr}(\mathcal{P})$ the collection of all transfer systems on
$\mathcal{P}$.

In [BBR21] it was proved that $|\mathsf{Tr}([n])|$ coincides with the
$(n+1)$-th Catalan number. The proof for this proceeded in a recursive fashion
which was governed by an operation denoted $\odot$ in loc. cit.

Let $\mathcal{R}$ be a transfer system on $[n]$. Denote by $x$ the minimal
element such that $x\,\mathcal{R}\,n$, and consider the partition of $[n]$ as
$[0,x-1]\amalg[x,n]$. The key observation is that the restriction of
$\mathcal{R}$ to $[0,x-1]$ and $[x,n]$ yields two transfer systems, and
moreover, $\mathcal{R}$ can be recovered from the disjoint union of these two
transfer systems. To retrieve the aforementioned $\odot$ operation from this,
we note that the _pivot element_ in [BBR21] is simply $x$.

In this section we will follow a suggestion of Mike Hill to extend this
observation to transfer systems on an arbitrary finite lattice $L$, which
provides a method for producing recursive formulas for counting transfer
systems. To this end, let $L$ be a finite lattice equipped with a transfer
system $\mathcal{R}$. Let $m$ be the maximal element of $L$, we will say that
$x\in L$ is _fibrant_ if $x\,\mathcal{R}\,m$. (This terminology is inspired by
the corresponding statement under the equivalence of transfer systems to weak
factorization systems.)

######  Lemma .

Let $L$ and $\mathcal{R}$ be as above. Then $\mathcal{R}$ has a unique minimal
fibrant element.

###### Proof.

Let $\\{x_{i}\\}_{i}$ be the collection of fibrant elements of $\mathcal{R}$.
Then by pullback closure of transfer systems, it follows that
$(\bigwedge_{i}x_{i})\,\mathcal{R}\,m$. In particular, $\bigwedge_{i}x_{i}$ is
a fibrant element and $(\bigwedge_{i}x_{i})\leqslant x_{j}$ for all $j$ as
required. ∎

######  Definition .

Let $L$ be a lattice, and $x\in L$. We denote by $x_{\uparrow}$ the set of all
$y\geqslant x$. The set theoretic complement of $x_{\uparrow}$ in $L$ will be
denoted $x_{\uparrow}^{\mathsf{c}}$.

The following is a standard result in the theory of finite lattices.

######  Lemma .

Let $L$ be a finite lattice and $x\in L$. Then the collection $x_{\uparrow}$
is a sublattice of $L$, and $x_{\uparrow}^{\mathsf{c}}$ is a sub-meet-
semilattice of $L$.

Via Section 2, one sees that there is a well-defined notion of transfer system
for $x_{\uparrow}$ and $x_{\uparrow}^{\mathsf{c}}$. Indeed, the axioms for a
categorical transfer system only depend on the meet operation, so we can use
the same definition for meet-semilattices like $x_{\uparrow}^{\mathsf{c}}$. In
particular, for $L$ a finite lattice and $\mathcal{R}$ a transfer system on
$L$, if $x$ is the unique fibrant element, then $\mathcal{R}$ restricts to
transfer systems $\mathcal{R}_{2}$ and $\mathcal{R}_{1}$ on $x_{\uparrow}$ and
$x_{\uparrow}^{\mathsf{c}}$, respectively.

Given $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ as above, we can construct a
candidate transfer system $\mathcal{R}_{1}\amalg\mathcal{R}_{2}$ by simply
taking their disjoint union over $L$. The following lemma proves that this
retrieves the starting transfer system $\mathcal{R}$.

######  Lemma .

Let $\mathcal{R}$, $\mathcal{R}_{1}$, and $\mathcal{R}_{2}$ be as above. Then
$\mathcal{R}=\mathcal{R}_{1}\amalg\mathcal{R}_{2}$.

###### Proof.

Assume that there is some $y\in x_{\uparrow}^{\mathsf{c}}$ and $z\in
x_{\uparrow}$ such that $y\,\mathcal{R}\,z$. By pullback closure we have
$(x\wedge y)\,\mathcal{R}\,x$, and by transitivity we have $(x\wedge
y)\,\mathcal{R}\,x\mathcal{R}\,m$, that is, $x\wedge y$ is fibrant. However,
as $y\in x_{\uparrow}^{\mathsf{c}}$, $(x\wedge y)<x$, violating the assumed
minimality of $x$. ∎

######  Example .

Let $L=[1]\times[3]$, and consider the following transfer system.222B Warning:
For typographical reasons, we plot the first coordinate vertically and the
second coordinate horizontally; this same convention is held in all our
diagrams and nomenclature (especially _bottom row_ , _top row_ , _verticals_ ,
and _diagonals_.

The minimal fibrant element $(0,1)$ is highlighted in red. One clearly sees
pictorially that $\mathcal{R}$ splits as a transfer system $\mathcal{R}_{1}$
on $(0,1)_{\uparrow}\cong[1]\times[2]$ and a transfer system $\mathcal{R}_{2}$
on $(0,1)_{\uparrow}^{\mathsf{c}}\cong[1]\times[0]\cong[1]$.

As such, every transfer system $\mathcal{R}$ on $L$ can be split into a pair
of transfer systems on sub-(semi-)lattices of $L$. In the converse direction,
given two transfer systems $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ on
$x_{\uparrow}^{\mathsf{c}}$ and $x_{\uparrow}$ respectively, we can ask when
$\mathcal{R}_{1}\amalg\mathcal{R}_{2}$ is a transfer system for $L$. This
happens if and only if the restrictions of relations in $\mathcal{R}_{2}$ that
lie in $x_{\uparrow}^{\mathsf{c}}$ are relations in $\mathcal{R}_{1}$. We will
say that such an $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ is a _restriction
closed pair_ over $L$.

######  Example .

If we modify Section 2 so that $\mathcal{R}_{2}$ is the empty transfer system
on $[1]$, then this pair is not restriction closed and
$\mathcal{R}_{1}\amalg\mathcal{R}_{2}$ does not form a transfer system for
$[1]\times[3]$.

From this discussion, we can form the basis of a recursive formula for
computing $\mathsf{Tr}(L)$ based on the geometry of $L$. We summarise this in
the following theorem.

######  Theorem .

Let $L$ be a finite lattice. Then there is a bijection between transfer
systems on $L$ and restriction closed pairs of transfer systems over $L$.

######  Construction .

To rephrase this strategy in the form of an $\odot$ operation, we use the
observation from the beginning of this section that the _pivot element_ of the
$\odot$ operation for $[n]$ was given by the minimal fibrant element of
$\mathcal{R}$. If $L$ is now an arbitrary finite lattice with $\mathcal{R}$,
$\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ as above, we let
$\mathcal{R}_{2}\smallsetminus\\{x\\}$ be the collection of transfers where we
have removed the initial element (i.e., we remove the fibrant element $x$).
Then we could sensibly define
$\mathcal{R}=\mathcal{R}_{1}\odot(\mathcal{R}_{2}\smallsetminus\\{x\\}$),
where the operation $\odot$ inserts a new element $x$ and adds in the transfer
$x\,\mathcal{R}\,m$ and all transfers induced by this.

In this notation, one would decompose the $\mathcal{R}$ of Section 2 as

$\odot$.

##  3\. Enumerating transfer systems for $D_{p^{n}}$

The eventual goal of this paper is to provide a recursive formula for transfer
systems on $[1]\times[n]$ which we realize as the subgroup lattice of
$G=C_{qp^{n}}$ for $p,q$ distinct primes. We will begin with a slightly more
tame count, that of _liftable transfer systems_ of $[1]\times[n]$ as we now
define.

######  Definition .

A transfer system $\mathcal{R}$ on $[1]\times[n]$ is _liftable_ if
$\mathcal{R}$ additionally satisfies:

(_L_) If $(1,i)\,\mathcal{R}\,(1,j)$ for $i<j$ then
$(0,i)\,\mathcal{R}\,(1,i)$.

We write $L(n)$ to denote the collection of liftable transfer systems on
$[1]\times[n]$.

The relevance of liftable transfer systems in the general machinery of
$N_{\infty}$ operads is provided by the following key result of [BMO22].

######  Proposition  ([BMO22, §4]).

Let $n\geqslant 0$. Then there is a bijection between liftable transfer
systems on $[1]\times[n]$ and transfer systems for the group $G=D_{p^{n}}$.

The link between liftable transfer systems and dihedral transfer systems
arises via the lattice isomorphism
$\operatorname{Sub}(D_{p^{n}})/D_{p^{n}}\cong[1]\times[n]$. (Here the quotient
is with respect to the conjugation action of $D_{p^{n}}$ on its subgroups.)
Once we have given a recursive formula for $L(n)$, we will, in the following
section, exploit the involution on transfer systems as uncovered in [FOO+22]
to prove a recursion for $\mathsf{Tr}([1]\times[n])$.

As a warmup, let us see how the liftable condition $(L)$ allows us to
enumerate the number of saturated transfer systems in $L(n)$. Recall that a
transfer system is said to be _saturated_ if it satisfies 2-out-of-3.

######  Proposition .

There are $(n+2)2^{n}$ saturated transfer systems for $D_{p^{n}}$.

###### Proof.

In [HMOO22] it was proved that there are $2^{n}$ saturated transfer systems on
$[n]$. Consider the bottom row of $[1]\times[n]$ given by the coordinates
$(0,i)$, then we can freely pick any saturated transfer system to fill this
in. Let $j$ be the maximal number such that $(0,j)\,\mathcal{R}\,(1,j)$.
Clearly there are $n+2$ such choices (including the possibility of no such $j$
existing). We then claim that this data uniquely determines a saturated
transfer system on $[1]\times[n]$ which moreover satisfies $(L)$.

We begin by observing that if $j^{\prime},j^{\prime\prime}>j$, we cannot have
$(1,j^{\prime})\,\mathcal{R}\,(1,j^{\prime\prime})$. If this were the case
then by $(L)$ we would be forced to have
$(0,j^{\prime})\,\mathcal{R}\,(1,j^{\prime})$ which contradicts the maximality
of $j$. Instead consider the existence of $(1,j)\,\mathcal{R}\,(1,j+1)$. By
restriction we must have $(0,j)\,\mathcal{R}\,(1,j+1)$ as well as
$(0,j)\,\mathcal{R}\,(0,j+1)$. As saturated transfer systems satisfy two-out-
of-three, it would imply that we moreover have
$(0,j+1)\,\mathcal{R}\,(1,j+1)$, once again contradicting the maximality of
$j$. As such, everything to the right of $j$ on the top row of $[1]\times[n]$
must be empty.

As we have $(0,j)\,\mathcal{R}\,(1,j)$, by restriction we also have
$(0,\ell)\,\mathcal{R}\,(1,\ell)$ for all $0\leqslant\ell\leqslant j$. By the
saturation condition, this forces the top row to the left of $j$ to be
identical to the bottom row.

Assembling everything, it follows that there are $(n+2)2^{n}$ possibilities as
claimed. ∎

We will use the strategy outlined in Section 2 to give a recursion for $L(n)$.
In particular, we begin by considering the partition of $L(n)$ as

$L(n)=\coprod_{(a,b)\in[1]\times[n]}L(n,(a,b))$

where $L(n,(a,b))$ is the set of liftable transfer systems such that $(a,b)$
is the minimal fibrant element (i.e., $(a,b)$ is minimal such that
$(a,b)\,\mathcal{R}\,(1,n)$).

We will find it advantageous to further split up the elements $L(n,(a,b))$
based on further partitioning properties of transfer systems.

######  Definition .

Let $\mathcal{R}$ be a transfer system on $[1]\times[n]$. We say that
$(a,b)\in[1]\times[n]$ is:

  * •

_Stationary_ if $a=1$ and there exists no $d>b\geqslant c$ with
$(1,c)\,\mathcal{R}\,(1,d)$.

  * •

_Extendable_ if $a=0$ and $(a,b)\,\mathcal{R}\,(0,n)$.

It is clear that any transfer system possesses at least one stationary and at
least one extendable element, namely $(1,n)$ and $(0,n)$ respectively. We now
have a different partition of $L(n)$ as

$L(n)=\coprod_{1\leqslant k\leqslant n+1}L(n,k)$

where $L(n,k)$ is the collection of transfer systems such that exactly $k$
elements are stationary. We then further refine each $L(n,k)$ as

$L(n,k)=\coprod_{1\leqslant\ell\leqslant n+1}L(n,k,\ell)$

where $L(n,k,\ell)\subseteq L(n,k)$ is the subset of those transfer system
where exactly $\ell$ elements are extendable.

Finally, we can define $L(n,k,\ell,(a,b))$ to be $L(n,k,\ell)\cap L(n,(a,b))$.
We provide a full description of these transfer systems in the following
definition.

######  Definition .

Let $n\geqslant 0$, $1\leqslant k,\ell\leqslant n+1,(a,b)\in[1]\times[n]$. We
define $L(n,k,\ell,(a,b))$ to be the collection of liftable transfer systems
$\mathcal{R}$ on $[1]\times[n]$ such that:

  * •

$\mathcal{R}$ has $k$ stationary elements.

  * •

$\mathcal{R}$ has $\ell$ extendable elements.

  * •

$(a,b)$ is the minimal fibrant element of $\mathcal{R}$.

In the next collection of propositions we will provide recursions for
$L(n,k,\ell,(a,b))$ for varying families of $(a,b)\in[1]\times[n]$. We require
one more definition before continuing to the first case.

######  Definition .

We denote by $\mathrm{Tam}(n)$ the set of all transfer systems $\mathcal{R}$
with $(0,n)\,\mathcal{R}\,(1,n)$ and $\mathrm{Tam}(n,k)=\mathrm{Tam}(n)\cap
L(n,k)$.

We will provide an in-depth exploration of $\mathrm{Tam}(n,k)$ in Section 5.
In particular, we will explain their namesake (_Tamari intervals_) and provide
explicit formulæ for $|\mathrm{Tam}(n)|$ and $|\mathrm{Tam}(n,k)|$; see
Section 5.

######  Proposition .

Let $b>0$. Then

$L(n,k,\ell,(0,b))=\coprod_{0\leqslant i\leqslant k}\mathrm{Tam}(b-1,i)\times
L(n-b,k-i,\ell,(0,0)).$

###### Proof.

Let $\mathcal{R}\in L(n,(0,b))$. Then by restriction to
$(0,b)_{\uparrow}^{\mathrm{c}}\cong[1]\times[b-1]$, we obtain a transfer
system $\mathcal{R}_{1}\in L(b-1)$, and by restricting to
$(0,b)_{\uparrow}\cong[1]\times[n-b]$, we obtain a transfer system
$\mathcal{R}_{2}\in L(n-b)$.

Since $(0,b)$ is fibrant in $\mathcal{R}$ and the minimal element of
$(0,b)_{\uparrow}$, we see that $\mathcal{R}_{2}\in L(n-b,(0,0))$. Similarly,
since $(0,b)\,\mathcal{R}\,(1,b)$ by assumption, we also have
$(0,b-1)\,\mathcal{R}\,(1,b-1)$. As such, $(1,b-1)$ is fibrant in
$\mathcal{R}_{1}$. In particular, we conclude that

$\mathcal{R}_{1}\in\mathrm{Tam}(b-1)$

and

$\mathcal{R}_{2}\in L(n-b,(0,0)).$

Conversely, given an arbitrary $\mathcal{R}_{1}\in\mathrm{Tam}(b-1)$ and
$\mathcal{R}_{2}\in L(n-b,(0,0))$, we can construct a relation $\mathcal{R}$
on $[1]\times[n]$ by placing $\mathcal{R}_{2}$ to the right of
$\mathcal{R}_{1}$ (i.e., we reindex $\mathcal{R}_{2}$ via a horizontal shift
of $b$).

Clearly such an $\mathcal{R}$ is transitive and satisfies the lifting
condition. Suppose that $(c,d)\,\mathcal{R}\,(e,f)$ and $(g,h)\leqslant(e,f)$.
If $(e,f)\leqslant(1,b-1)$, then we know that
$(c,d)\wedge(g,h)\,\mathcal{R}\,(g,h)$ by the virtue of $\mathcal{R}_{1}$
being a transfer system.

Else, if $(e,f)\not\leqslant(1,b-1)$, then we must have $(e,f)\geqslant(0,b)$,
and since $(c,d)\,\mathcal{R}\,(e,f)$ and we have no transfers from
$(0,b)_{\uparrow}^{\mathsf{c}}$ to $(0,b)_{\uparrow}$, we must also have
$(c,d)\geqslant(0,b)$. If $(g,h)\geqslant(0,b)$ as well, then
$(c,d)\wedge(g,h)\,\mathcal{R}\,(g,h)$ from that fact that $\mathcal{R}_{2}$
is a transfer system.

The last remaining case is $(0,b)\leqslant(c,d)$ and $(g,h)\leqslant(1,b-1)$,
then $(c,d)\wedge(g,h)=(c\wedge g,h)$. If $c\wedge g=g$, then we have
$(c\wedge g,h)\mathcal{R}(g,h)$. Otherwise, $c=0$ and $g=1$, so that we just
need to ensure that $(0,h)\,\mathcal{R}\,(1,h)$ fo all $h\leqslant b$, but
this follows from that fact that $(0,b-1)$ is fibrant in $\mathcal{R}_{1}$.

As such, we have shown that

$L(n,(0,b))=\mathrm{Tam}(b-1)\times L(n-b,(0,0)).$

Now we note that $(1,d)$ is stationary in $\mathcal{R}$ if and only if
$d\leqslant b-1$, and $(1,d)$ is stationary in $\mathcal{R}_{1}$, or
$d\geqslant b$ and $(1,d-b)$ is stationary in $\mathcal{R}_{2}$. Furthermore,
$(0,d)$ is extendable in $\mathcal{R}$ if and only if $d\geqslant b$ and
$(0,d-b)$ is extendable in $\mathcal{R}_{2}$. As such, we can refine the above
formula to the desired result. ∎

Section 3 is valid whenever $b>0$. However, we see that the formula is trivial
if $b=0$, even though there are liftable transfer systems on $[1]\times[n]$
where the minimal fibrant element is $(0,0)$ (in particular the maximal
transfer system is such). The next proposition resolves that case of $b=0$.

######  Proposition .

$L(n,k,\ell,(0,0))=\coprod_{k-1\leqslant k^{\prime}\leqslant
n}L(n-1,k^{\prime},\ell-1).$

###### Proof.

Let $\mathcal{R}\in L(n,k,(0,0))$, and $\mathcal{R}^{\prime}\in L(n-1)$ be the
restriction to $(0,1)_{\uparrow}\cong[1]\times[n-1]$. Let $b\leqslant n$ be
the maximal such that $(1,0)\,\mathcal{R}\,(1,b)$. Then $\mathcal{R}$ is
determined by $\mathcal{R}^{\prime}$ and $b$. Further, the only constraint
that we have on $\mathcal{R}^{\prime}$ and $b$ is that if $b\neq 0$ then
$(1,b-1)$ must be stationary in $\mathcal{R}^{\prime}$.

We then note that an element $(1,d)$ is stationary in $\mathcal{R}$ if and
only if $d\geqslant b$, and either $d=b=0$ or $(1,d-1)$ is stationary in
$\mathcal{R}^{\prime}$. Conversely, an element $(0,d)$ is extendable if and
only if $d=0$ or $(0,d-1)$ is extendable in $\mathcal{R}^{\prime}$. The result
follows. ∎

Via Section 3 and Section 3, we have now computed $|L(n,k,\ell,(0,b))|$ for
all possible values of $b$. As such we now turn our attention to computing
$|L(n,k,\ell,(1,b))|$. The case where $b<n$ is trivial as we now prove.

######  Proposition .

Let $b<n$, then

$L(n,k,\ell,(1,b))=\varnothing.$

###### Proof.

Recall that $L(n)$ consists of the liftable transfer systems. Assume that
$\mathcal{R}\in L(n,k,\ell,(1,b))$ then by assumption we have
$(1,b)\,\mathcal{R}\,(1,n)$. However, by the lifting condition, this implies
that $(0,b)\,\mathcal{R}\,(1,b)\,\mathcal{R}\,(1,n)$, violating the minimality
of $(1,b)$. Therefore no such $\mathcal{R}$ exists. ∎

The simplicity of the case of $(1,b)$ where $b<n$ is one of the reasons why
working with liftable transfer systems is simpler than the general case. Given
Section 3, it now suffices to compute $L(n,k,\ell,(1,n))$:

######  Proposition .

We have

$L(n,k,\ell,(1,n))=\coprod_{\ell-1\leqslant\ell^{\prime}\leqslant
n}L(n-1,k-1,\ell^{\prime}).$

###### Proof.

Let $\mathcal{R}\in L(n,k,(1,n))$, and $\mathcal{R}^{\prime}\in L(n,-1)$ be
the restriction to $[1]\times[n-1]$. Clearly there are no constraints on
$\mathcal{R}^{\prime}$ except from that it must have $k-1$ stationary
elements.

We begin by assuming that there are no transfers $(0,d)\,\mathcal{R}\,(0,n)$
for $d<n$, that is, $\mathcal{R}$ has a single extendable element. Thus all
transfers in $\mathcal{R}$ are contained in $(0,n)^{\mathsf{c}}_{\uparrow}$
and hence $\mathcal{R}$ is determined solely by $\mathcal{R}^{\prime}$. In
particular we have

$L(n,k,1,(1,n))=L(n-1,k-1)=\coprod_{0\leqslant\ell^{\prime}\leqslant
n}L(n-1,k-1,\ell^{\prime}).$

We now move to the case where $\mathcal{R}$ has more than a single extendable
element. That is, we assume that there exists some $d<n$ with
$(0,d)\,\mathcal{R}\,(0,n)$ for $d<n$. The set of all $d<n$ admitting arrows
$(0,d)\,\mathcal{R}\,(0,n)$ is determined by the maximal such $d$, which we
denote $b$. Indeed, if $(0,d)\,\mathcal{R}\,(0,n)$ then by restriction we also
have $(0,d)\,\mathcal{R}\,(0,b)$, and hence by definition
$(0,d)\mathcal{R}^{\prime}(0,b)$. Conversely if
$(0,d)\mathcal{R}^{\prime}(0,b)$, then by transitivity we have
$(0,d)\,\mathcal{R}\,(0,b)\,\mathcal{R}\,(0,n)$. The only constraint that we
have on $b$ is that $(0,b)$ must be extendable in $\mathcal{R}^{\prime}$. Note
that if $b$ is the $i$-th smallest extendable element in
$\mathcal{R}^{\prime}$, then $\mathcal{R}$ has $i+1$ extendable elements. If
$\mathcal{R}^{\prime}$ has $k$ stationary elements, then $\mathcal{R}$ has
$k+1$ stationary elements. Thus we have shown that

$L(n,k,\ell,(1,n))=\coprod_{\ell-1\leqslant\ell^{\prime}\leqslant
n}L(n-1,k-1,\ell^{\prime}).$

as required. We note that this retrieves the above formula when $\ell=1$. ∎

We are now in a position to combine the above results into the main theorem of
this section which provides an explicit recursive algorithm for computing
$|L(n)|$.

######  Theorem .

Let $n\geqslant 0$. Then for $1\leqslant\ell,k\leqslant n+1$ and
$(a,b)\in[1]\times[n]$ we have:

$\displaystyle|L(n,k,\ell,(0,0))|=$ $\displaystyle\sum_{k-1\leqslant
k^{\prime}\leqslant n}|L(n-1,k^{\prime},\ell-1)|$
$\displaystyle|L(n,k,\ell,(1,n))|=$
$\displaystyle\sum_{\ell-1\leqslant\ell^{\prime}\leqslant
n}|L(n-1,k-1,\ell^{\prime})|$ $\displaystyle|L(n,k,\ell,(0,b))|=$
$\displaystyle\sum_{0\leqslant i\leqslant
k}|\mathrm{Tam}(b-1,i)|\cdot|L(n-b,k-i,\ell,(0,0))|$ $\displaystyle(b>0)$
$\displaystyle|L(n,k,\ell,(1,b))|=$ $\displaystyle{\hskip 4.30554pt}0$
$\displaystyle(b<n).$

By convention, set $|L(n,k,\ell,(a,b))|=0$ when $k,\ell$ are out of range.
Then

$|L(n)|=\sum_{\begin{subarray}{c}1\leqslant k,\ell\leqslant n+1\\\\[4.0pt]
(a,b)\in[1]\times[n]\end{subarray}}|L(n,k,\ell,(a,b))|.$

######  Corollary .

Let $n\geqslant 0$. Then the number of homotopically distinct $N_{\infty}$
operads for $D_{p^{n}}$ is given by the recursion in Section 3.

######  Remark .

Note that in Section 3, it is only the computation $|L(n,k,\ell,(1,b))|=0$ for
$b<n$ where we use the fact that we are working with liftable transfer
systems. This will be relevant in the next section we consider transfer
systems for $C_{qp^{n}}$.

######  Computation .

By starting at $m=0$, we inductively store the values of $|L(m,k,\ell,(a,b))|$
for all $m\leqslant n$, $1\leqslant k,\ell\leqslant m+1$ and
$(a,b)\in[1]\times[m]$. The entries for all $m<m^{\prime}$ allow us to compute
the values for $m=m^{\prime}$ via Section 3 and Section 5; some small values
are recorded in Table 1, and large scale structure appears at the end of the
paper in Figure 1.

$n$ | $|L(n)|$
---|---
0 | 2
1 | 9
2 | 56
3 | 416
4 | 3457
5 | 31063
6 | 295834
7 | 2948082
8 | 30471080
9 | 324580196
10 | 3546142551
Table 1. Values of $|L(n)|$, the number of transfer systems for $D_{p^{n}}$,
$p\neq 2$.

######  Remark .

We leave open the challenge of finding a closed formula for $|L(n)|$. One
might begin with a five-variable generating function and the functional
equation implied by Section 3. Of course, a bijective enumeration would be
even more desirable.

######  Remark .

In Section 6 we deduce a nontrivial lower bound on the asymptotics of
$|L(n)|$.

##  4\. Enumerating transfer systems for $C_{qp^{n}}$

In the previous section we enumerated the liftable transfer systems on
$[1]\times[n]$. We will now move to the general case. For clarity we will
write $T(n)$ for the collection of all transfer systems $[1]\times[n]$ (i.e.,
$L(n)\subseteq T(n)$). We will employ the same strategy as before, and
$T(n,k,\ell,(a,b))$ will be as before (but without the lifting condition).

From Section 3 we see that we need only consider how to resolve the case of
$T(n,k,\ell,(1,b))$ for $b<n$, and in the other cases the recursion for
$T(n,k,\ell,(a,b))$ is the same as the recursion for $L(n,k,\ell,(a,b))$. To
resolve this remaining case, we will use a powerful observation regarding the
duality of transfer systems as described in [FOO+22] which we now recall. For
a transfer system $\mathcal{R}$ on a finite lattice $L$, we write

$\mathcal{E}(\mathcal{R})=\\{(z,y)\mid\text{ there exists }x\in L\text{ such
that }z\leqslant x<y\text{ and }x\,\mathcal{R}\,y\\}$

for the _downward closure of $\mathcal{R}$_.

######  Definition .

Let $L$ be a finite lattice admitting a self duality $\nabla$ and let
$\mathcal{R}$ be a transfer system on $L$. The _dual_ of $\mathcal{R}$ is the
transfer system $\mathcal{R}^{\ast}$ defined as

$\mathcal{R}^{\ast}=((\mathcal{E}(\mathcal{R})^{op})^{\nabla})^{\mathsf{c}}.$

From [FOO+22] we have that $(\mathcal{R}^{\ast})^{\ast}=\mathcal{R}$ so this
provides an involution on the set $\mathsf{Tr}(L)$. In the case that
$L=[1]\times[n]$, we use the canonical duality given by
$(a,b)\xmapsto{\nabla}(1-a,n-b)$.

######  Proposition .

The duality on $\mathsf{Tr}([1]\times[n])$ restricts to a duality

$T(n,k,\ell,(a,b))\longleftrightarrow T(n,\ell,k,(1-a,n-b)).$

This duality does not preserve the property of being liftable.

###### Proof.

Let $\mathcal{R}\in T(n,k,\ell,(a,b))$. We first observe that $(1-a,n-b)$ is
the minimal fibrant element in $\mathcal{R}^{\ast}$. Indeed, we have $(a,b)$
is the minimal element such that $(a,b)\,\mathcal{R}\,(1,n)$. From the
definition, we see that $(1-a,b-n)\,\mathcal{R}^{\ast}\,(1,n)$ if and only if
$(0,0)\,\cancel{\mathcal{E}(\mathcal{R})}\,(a,b)$. Assume that we have
$(0,0)\,\mathcal{E}(\mathcal{R})\,(a,b)$, then this implies the existence of
some $(i,j)<(a,b)$ such that $(i,j)\,\mathcal{R}\,(a,b)$, but by transitivity
we would get $(i,j)\,\mathcal{R}\,(a,b)\,\mathcal{R}\,(1,n)$, contradicting
the minimality of $(a,b)$. The minimality of $(1-a,n-b)$ as a fibrant element
of $\mathcal{R}^{\ast}$ is afforded by the minimality of $(a,b)$ in
$\mathcal{R}$.

We will now explore the duality between the extendable and stationary
elements. Let $y\geqslant 1$, we will show that $(1,y-1)$ is stationary in
$\mathcal{R}$ if and only if $(0,n-y)$ is extendable in $\mathcal{R}^{\ast}$.
Again by definition, this happens if and only if
$(1,0)\,\cancel{\mathcal{E}(\mathcal{R})}\,(1,y)$. Assume that
$(1,0)\,\mathcal{E}(\mathcal{R})\,(1,y)$, then this implies the existence of
some $0\leqslant z<y$ with $(1,z)\,\mathcal{R}\,(1,y)$. However, we have
assumed that $y-1$ is stationary, so no such $z$ can exist.

The remaining case of $y=0$ is covered by the fact that $(1,n)$ is always
stationary and $(0,n)$ is always extendable. ∎

Combining Section 4, Section 3 and Section 3 we arrive at our desired result.

######  Theorem .

Let $n\geqslant 0$. Then for $1\leqslant\ell,k\leqslant n+1$ and
$(a,b)\in[1]\times[n]$ we have:

$\displaystyle|T(n,k,\ell,(0,0))|=$ $\displaystyle\sum_{k-1\leqslant
k^{\prime}\leqslant n}|T(n-1,k^{\prime},\ell-1)|$
$\displaystyle|T(n,k,\ell,(0,b))|=$ $\displaystyle\sum_{0\leqslant i\leqslant
k}|\mathrm{Tam}(b-1,i)|\cdot|T(n-b,k-i,\ell,(0,0))|$ $\displaystyle(b>0)$
$\displaystyle|T(n,k,\ell,(1,b))|=$ $\displaystyle{\hskip
4.30554pt}|T(n,\ell,k,0,n-b)|.$

By convention, set $|T(n,k,\ell,(a,b))|=0$ when $k,\ell$ are out of range.
Then

$|T(n)|=\sum_{\begin{subarray}{c}1\leqslant k,\ell\leqslant n+1\\\\[4.0pt]
(a,b)\in[1]\times[n]\end{subarray}}|T(n,k,\ell,(a,b))|.$

######  Corollary .

Let $n\geqslant 0$. Then the number of homotopically distinct $N_{\infty}$
operads for $C_{qp^{n}}$ is given by the recursion in Section 4.

######  Computation .

Following the methods of Section 3 we are once again able to efficiently
compute values of $|T(n)|$; for small values of $n$, these are presented in
Table 2, and larger scale behavior appears at the end of the paper in Figure
1.

$n$ | $|T(n)|$
---|---
0 | 2
1 | 10
2 | 68
3 | 544
4 | 4828
5 | 46124
6 | 465932
7 | 4919062
8 | 53832832
9 | 607000122
10 | 7019272236
Table 2. Values of $|T(n)|$ computed via Section 4.

######  Remark .

The strategy outlined Section 2 is extremely general, and one could envisage
running the machine for other fundamental lattices such as $[m]\times[n]$ and
$[1]^{n}$. What is evident from the discussions in Section 3 and Section 4 is
that the power of the computation can be improved by understanding the
inherent structures of transfer systems and how they arise (e.g., the
existence of suitable liftable families and dualities).

######  Remark .

As with $|L(n)|$, it would be desirable to derive a closed formula for
$|T(n)|$ via generating function or bijective techniques.

##  5\. Restricted Tamari intervals

In this section we will study the term $\mathrm{Tam}(n,k)$ which appears in
Section 3, Section 3, and Section 4.

We begin by recalling from Section 3 that we denote by $\mathrm{Tam}(n)$ the
set of all transfer systems $\mathcal{R}$ with $(0,n)\,\mathcal{R}\,(1,n)$ and
$\mathrm{Tam}(n,k)=\mathrm{Tam}(n)\cap L(n,k)$.

Recall from [BOOR22] that $\mathsf{Tr}([n])$ admits a lattice bijection to the
Tamari lattice. As such for $\mathcal{R}$ and $\mathcal{R}^{\prime}$ transfer
systems on $[n]$, we say that $\mathcal{R}\leqslant\mathcal{R}^{\prime}$ is a
_Tamari interval_. The next lemma justifies our choice of notation for
$\mathrm{Tam}(n)$. We note that if $\mathcal{R}$ is a transfer system on
$[n]$, then we — analogously to the $[1]\times[n]$ case — say that $b\in[n]$
is _stationary_ for $\mathcal{R}$ if there exists no $d>b\geqslant c$ with
$(1,c)\,\mathcal{R}\,(1,d)$.

######  Lemma .

Let $n\geq 0$. Then $\mathrm{Tam}(n)$ is in bijection with Tamari intervals in
$\mathsf{Tr}[n]$. In particular $\mathrm{Tam}(n,k)$ is in bijection with the
Tamari intervals $\mathcal{R}\leqslant\mathcal{R}^{\prime}$ in
$\mathsf{Tr}[n]$ such that $\mathcal{R}$ has $k$ stationary elements.

###### Proof.

By restriction, a transfer system in $\mathrm{Tam}(n)$ has all vertical
transfers $(0,a)\,\mathcal{R}$ $(1,a)$ for $0\leqslant a\leqslant n$. We have
the diagonal $(0,b)\,\mathcal{R}\,(1,c)$ if and only if
$(0,b)\,\mathcal{R}\,(0,c)$. Indeed, the forward implication follows by
pullback closure, and the reverse implication is given by composition with
$(0,c)\,\mathcal{R}\,(1,c)$. Therefore, such an $\mathcal{R}$ restricted to
the bottom row determines all diagonals. In particular $\mathcal{R}$ is
determined uniquely by its restriction to the top and bottom, and is therefore
the data of a Tamari interval. ∎

From work of Chapoton [Cha07], we know that the cardinality of the set of
Tamari intervals for $[n]$ has closed form given by

$|\mathrm{Tam}(n)|=\dfrac{2}{(n+1)(n+2)}\binom{4n+5}{n}.$

The following proposition provides a closed formula for $|\mathrm{Tam}(n,k)|$.

######  Proposition .

Let $n\geqslant 0$ and $1\leqslant k\leqslant n+1$. Then

$|\mathrm{Tam}(n,k)|=\dfrac{2(2k+1)!(4n-2k+3)!}{(k-1)!(k+1)!(n-k+1)!(3n-k+4)!}$

###### Proof.

An explicit bijection between transfer systems on $[n]$ and rooted binary
trees with $(n+1)$ internal nodes was constructed in [BOOR22]. One can check
that under this bijection that the number of stationary elements of a transfer
system $\mathcal{R}$ on $[n]$ is equal to the number of elements on the
corresponding binary tree whose path from the root is a straight line to the
left.

Using the classical bijection between binary trees with $n+1$ nodes and Dyck
paths of length $2n+2$, we see that the number of stationary elements is also
given by one less than the number of times the corresponding Dyck path touches
the horizontal axis.

The result then follows from [BMFPR11, Corollary 11] and the first remark
following it. ∎

$n$ $k$ | 1 | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---|---
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0
1 | 1 | 2 | 0 | 0 | 0 | 0 | 0
2 | 3 | 5 | 5 | 0 | 0 | 0 | 0
3 | 13 | 20 | 21 | 14 | 0 | 0 | 0
4 | 68 | 100 | 105 | 84 | 42 | 0 | 0
5 | 399 | 570 | 595 | 504 | 330 | 132 | 0
6 | 2530 | 3542 | 3675 | 3192 | 2310 | 1287 | 429
Table 3. Values of $|\mathrm{Tam}(n,k)|$ for small values of $n$ and $k$ using
Section 5.

######  Remark .

The values appearing in Table 3 make up some very well known number sequences
as we now outline. The triangular array $|\mathrm{Tam}(n,k)|$ appears in a
reindexed form in [Bro64] where one enumerates triangulations of $k+3$-gons
with $n+1$-internal vertices. In particular we have:

  * •

The major diagonal where $k=n+1$ retrieves the Catalan numbers.

  * •

The sum of the row $|\mathrm{Tam}(n,-)|$ computes the number of Tamari
intervals for $[n]$.

  * •

The column $|\mathrm{Tam}(-,1)|$ is the number of Tamari intervals for
$[n-1]$.

  * •

The column $|\mathrm{Tam}(-,k)|$ is the number of triangulations of a
$(k+2)$-gon with $n$ internal nodes.

##  6\. Maximally extendable $D_{p^{n}}$ transfer systems and Schröder numbers

In the remainder of this paper, we will explore a certain type of transfer
system on $[1]\times[n]$ in the liftable and nonliftable cases, the
enumeration of which retrieve interesting number sequences. We begin by
introducing the class that we are interested in.

######  Definition .

A (liftable) transfer system $\mathcal{R}$ for $[1]\times[n]$ is _maximally
extendable_ if it has $n+1$ extendable elements.

######  Remark .

In a more intuitive description, a transfer system is maximally extendable if
and only if its restriction to the bottom row is the maximal transfer system
on $[n]$. As such, for $G=D_{p^{n}}$ or $C_{qp^{n}}$ (in the liftable and
general scenarios, respectively) these are the transfer systems associated
with $G$-$N_{\infty}$ operads restricting to genuine $G$-$E_{\infty}$ operads
on $C_{p^{n}}\leqslant G$.

We will once again begin with the case of liftable transfer systems.

######  Definition .

Let $n\geqslant 0$. Then $\mathfrak{S}_{n}$, the $n^{\mathrm{th}}$ _(large)
Schröder number_ , is the number of lattice paths from the southwest corner
$(0,0)$ of an $n\times n$ grid to the northeast corner $(n,n)$ using single
steps north $(0,1)$, northeast $(1,1)$, or east $(1,0)$, that do not rise
above the $SW$-$NE$ diagonal. (Such paths are called _royal ( $n$-)paths_.)

######  Proposition  ([QG17]).

If $n=0$ then $\mathfrak{S}_{n}=1$. For $n\geq 1$, the large Schröder numbers
satisfy the recurrence

$\mathfrak{S}_{n}=3\mathfrak{S}_{n-1}+\sum_{k=1}^{n-2}\mathfrak{S}_{k}\mathfrak{S}_{n-k-1}.$

Additionally, for $n\geqslant 1$ we have

$\mathfrak{S}_{n}=\sum_{1\leqslant k\leqslant n}\mathrm{Nar}(n,k)\cdot
2^{k}=\sum_{1\leqslant k\leqslant
n}\dfrac{1}{n}\binom{n}{k}\binom{n}{k-1}\cdot 2^{k}$

where $\mathrm{Nar}(n,k)$ is the $(n,k)$-th Narayana number.

######  Computation .

Table 4 provides a calculation of $\mathfrak{S}_{n}$ for small values of $n$.

$n$ | $\mathfrak{S}_{n}$
---|---
0 | 1
1 | 2
2 | 6
3 | 22
4 | 90
5 | 394
6 | 1806
7 | 8558
8 | 41586
9 | 206098
10 | 1037718
Table 4. Values of $\mathfrak{S}_{n}$ computed via Section 6.

We can produce refined statistics on royal paths by tracking the number of
diagonal returns each path has, using the convention that a northeast step on
the diagonal counts as a return. Let $\mathfrak{S}_{n}(k)$ denote the number
of royal $n$-paths with $k$ returns to the diagonal; call these the _refined
Schröder numbers_.

######  Proposition  ([OEIS]).

The refined Schröder numbers take the values

$\mathfrak{S}_{n}(k)=\begin{cases}0&\text{if }n<k,\\\ 2^{n}&\text{if }n=k,\\\
2^{k}\frac{k}{n-k}\sum_{p=1}^{n-k}\binom{n-k}{p}\binom{n-1+p}{p-1}&\text{if
}n>k.\end{cases}$

Furthermore,

$\sum_{k=1}^{n}\mathfrak{S}_{n}(k)=\mathfrak{S}_{n}.$

######  Computation .

Table 5 provides a calculation of $\mathfrak{S}_{n}(k)$ for small values of
$n$ and $k$.

$n$ $k$ | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---
1 | 2 | 0 | 0 | 0 | 0 | 0
2 | 2 | 4 | 0 | 0 | 0 | 0
3 | 6 | 8 | 8 | 0 | 0 | 0
4 | 22 | 28 | 24 | 16 | 0 | 0
5 | 90 | 112 | 96 | 64 | 32 | 0
6 | 394 | 484 | 416 | 288 | 160 | 64
Table 5. Values of $\mathfrak{S}_{n}(k)$ computed via Section 6.

While the above result is standard, we were unable to find a proof of the
following recurrence in the literature. It will be extremely useful in linking
large Schröder numbers with transfer systems.

######  Lemma .

The refined Schröder numbers satisfy the recurrence relation

$\mathfrak{S}_{n}(k)=2\mathfrak{S}_{n}(k-1)+\sum_{p=k}^{n}\mathfrak{S}_{n-1}(p)$

for $1\leq k\leq n$.

###### Proof.

Write $E$ for east steps, $N$ for north steps, and $D$ for diagonal steps.
Given a royal $n$-path, consider the location of its first diagonal return. If
this return is in position $(1,1)$, then the path begins $EN$ or $D$ and the
rest of the path may be filled in by any royal $(n-1)$-path with $k-1$
returns. This accounts for the $2\mathfrak{S}_{n}(k-1)$ term. If the first
return is in position $(r,r)$ with $r>1$, then we may write our path as $EPNQ$
where $P$ is a royal $(r-1)$-path and $Q$ is a royal $(n-r)$-path. The path
$PQ$ is then a royal $(n-1)$-path with at least $k$ diagonal returns. This
decomposition is unique and each such royal $(n-1)$-path arises in this
fashion, so this accounts for the term $\sum_{p=k}^{n}\mathfrak{S}_{n-1}(p)$.
∎

We are now prepared to demonstrate the connection between (refined) large
Schröder numbers and maximally extendable transfer systems on $D_{p^{n}}$.

######  Theorem .

Let $n\geqslant 0$. Then the number of maximally extendable transfer systems
in $L(n)$ is given by $\mathfrak{S}_{n+1}$, and the number of maximally
extendable transfer systems in $L(n)$ with exactly $k$ stationary nodes is
$\mathfrak{S}_{n+1}(k)$.

###### Proof.

It suffices to prove the second statement since the refined Schröder numbers
$\mathfrak{S}_{n+1}(k)$ add up to $\mathfrak{S}_{n+1}$. Write
$\mathfrak{m}(n,k):=|L(n,k,n+1)|$ for the number of maximally exetndable
transfer systems on $D_{p^{n}}$ with exactly $k$ stationary nodes. Clearly
$\mathfrak{m}(0,1)=2=\mathfrak{S}_{1}(1)$, so it suffices to prove that
$\mathfrak{m}(n,k)$ satisfies the recurrence of Section 6, _i.e._ ,

$\mathfrak{m}(n,k)=2\mathfrak{m}(n,k-1)+\sum_{p=k}^{n}\mathfrak{m}(n-1,p).$

This is a direct consequence of Section 3 specialized to the case $\ell=n+1$.
∎

######  Remark .

In [Sta99, Exercise 6.39], Stanley provides a list of nineteen classical
structures counted by Schröder numbers. The challenge of finding an explicit
bijection between maximally extendable transfer systems on $D_{p^{n}}$ and one
of these structures remains open.

######  Proposition .

Let $L^{\mathrm{max}}(n)$ denote the collection of maximally extendable
liftable transfer systems on $[1]\times[n]$. The asymptotics of
$|L^{\mathrm{max}}(n)|$ satisfy

$|L^{\mathrm{max}}(n)|\sim C\frac{(3+\sqrt{8})^{n}}{n^{3/2}}$

where

$C=\frac{\sqrt{2}(3+2\sqrt{2})}{2\sqrt{\pi(-4+3\sqrt{2})}}\approx
4.720408926.$

This provides a lower bound on the asymptotic behavior of $|L(n)|$.

###### Proof.

This follows directly from Section 6 and the asymptotics of the large Schröder
numbers (see for instance Exercise 12 on p.539 of [Knu97]). ∎

We now shift our attention back to all transfer systems on $[1]\times[n]$, and
consider the maximally extendable transfer systems here. Recall from Section 4
that there is a duality

$T(n,k,\ell,(a,b))\longleftrightarrow T(n,\ell,k,(1-a,n-b)).$

In particular, by summing up over all elements $(a,b)\in[1]\times[n]$ we
obtain a duality

$T(n,k,\ell)\longleftrightarrow T(n,\ell,k).$

######  Definition .

A transfer system $\mathcal{R}$ for $[1]\times[n]$ is _maximally stationary_
if it has $n+1$ stationary elements.

######  Remark .

In a more intuitive description, a transfer system is maximally stationary if
and only if its restriction to the top row is the minimal transfer system on
$[n]$.

######  Corollary .

Let $n\geqslant 0$. Then the number of maximally extendable transfer systems
in $T(n)$ is the same as the number of maximally stationary transfer systems
in $T(n)$ (and indeed the same as the number of maximally stationary transfer
systems in $L(n)$).

######  Definition .

Let $n\geqslant 1$. Then $\mathfrak{A}_{n}$ is the number of rooted subtrees
in rooted planar tree with $n$ nodes.

######  Remark .

Rooted subtrees of a fixed planar tree are in bijection with nonempty
antichains in the same tree (with the canonical partial order in which the
root is minimal and edges are covering relations). Rooted subtrees are
analyzed in [Rus81] while [Kla97] studies the same problem in the language of
antichains.

######  Proposition  ([Rus81, Kla97]).

Let $n\geqslant 1$. Then

$\mathfrak{A}_{n}=\dfrac{\displaystyle{\sum_{0\leqslant
i<n}}\binom{2i+1}{i}\binom{2n-1}{n-i-1}}{2n-1}.$

Moreover $\mathfrak{A}_{n}$ satisfies the recurrence $\mathfrak{A}_{1}=1$ and

$\mathfrak{A}_{n}=\sum_{j=1}^{n-1}\mathfrak{A}_{n-j}\mathfrak{A_{j}}+\mathfrak{A}_{n-j}\mathrm{Cat}(j-1)$

where $\mathrm{Cat}(j)$ is the $j$-th Catalan number.

######  Computation .

Table 6 provides a calculation of $\mathfrak{A}_{n}$ for small values of $n$.

$n$ | $\mathfrak{A}_{n}$
---|---
1 | 1
2 | 2
3 | 7
4 | 29
5 | 131
6 | 625
7 | 3099
8 | 15818
9 | 82595
10 | 439259
Table 6. Values of $\mathfrak{A}_{n}$ computed via Section 6.

Numerical experiments lead us to conjecture that maximally extendable transfer
systems in $T(n)$ are counted by $\mathfrak{A}_{n+2}$. By Section 6, we
conjecture the same count for maximally stationary transfer systems in $T(n)$
and maximally stationary transfer systems in $L(n)$.

######  Conjecture .

For $n\geqslant 0$, the number of maximally extendable transfer systems in
$T(n)$ is given by $\mathfrak{A}_{n+2}$.

The authors’ attempts to prove this conjecture by standard enumerative methods
(both bijective and inductive) have been spoiled by the subtle effects of
restriction on transfers joining the bottom and top rows. Following the
argument of [Kla97], we note that it would suffice to decompose the top row
$r$ of each maximally extendable transfer system in $T(n)$ into “primary
components” $r_{1},\ldots,r_{k}$ for which

$w(r)=\prod_{i=1}^{k}(1+w(r_{i}))$

where $w(s)$ measures the number of maximally extendable transfer systems with
top row $s$.

###  6.1. Figures

We conclude by plotting of the behavior of our enumerations related to
transfer systems for $D_{p^{n}}$ and $C_{qp^{n}}$. All of the data for these
figures was produced using code available at
https://github.com/bifibrant/recursion/.

$0$$10$$20$$30$$40$$50$$60$$70$$80$$10^{1}$$10^{23}$$10^{45}$$10^{67}$$10^{89}$
Figure 1. A semilog plot of the values of $|L(n)|$ (blue dots), $|T(n)|$ (red
dots), $|L^{\mathrm{max}}(n)|$ (blue squares), and $|T^{\mathrm{max}}(n)|$
(red squares) for $0\leqslant n\leqslant 80$. Here the superscript
$\mathrm{max}$ indicates maximally extendable transfer systems.

The graph in Figure 1 suggests that $|L(n)|$ and $|T(n)|$ might have
subexponential growth rates of a shape similar to the asymptotics of
$|L^{\mathrm{max}}(n)|$ from Section 6.

Finally, in Figure 2 we plot $|L(n)|/|T(n)|$ and observe that the fraction of
liftable transfer systems appears to approach $0$.

$0$$10$$20$$30$$40$$50$$60$$70$$80$$0.2$$0.4$$0.6$$0.8$$1$ Figure 2. A
(nonlogarithmic) plot of $L(n)/T(n)$ for $0\leqslant n\leqslant 80$. The
semilogarithmic plot appears approximately linear.

## References

  * [BBR21] S. Balchin, D. Barnes, and C. Roitzheim.  $N_{\infty}$-operads and associahedra.  Pacific J. Math., 315(2):285–304, 2021.
  * [BH15] A. J. Blumberg and M. A. Hill.  Operadic multiplications in equivariant spectra, norms, and transfers.  Adv. Math., 285:658–708, 2015.
  * [BMFPR11] M. Bousquet-Mélou, É. Fusy, and L.-F. Préville-Ratelle.  The number of intervals in the $m$-Tamari lattices.  Electron. J. Combin., 18(2):Paper 31, 26, 2011.
  * [BMO22] S. Balchin, E. MacBrough, and K. Ormsby.  Lifting $N_{\infty}$ operads from conjugacy data.  arXiv:2209.06798, 2022.
  * [BOOR22] S. Balchin, K. Ormsby, A.M. Osorno, and C. Roitzheim.  Model structures on finite total orders.  arXiv:2109.07803, 2022.
  * [Bro64] W. G. Brown.  Enumeration of triangulations of the disk.  Proc. London Math. Soc. (3), 14:746–768, 1964.
  * [Cha07] F. Chapoton.  Sur le nombre d’intervalles dans les treillis de Tamari.  Sém. Lothar. Combin., 55:Art. B55f, 18, 2005/07.
  * [FOO+22] E. E. Franchere, K. Ormsby, A. M. Osorno, W. Qin, and R. Waugh.  Self-duality of the lattice of transfer systems via weak factorization systems.  Homology, Homotopy and Applications, 24(2):115–134, 2022.
  * [HMOO22] U. Hafeez, P. Marcus, K. Ormsby, and A.M. Osorno.  Saturated and linear isometric transfer systems for cyclic groups of order $p^{m}q^{n}$.  Topology Appl., 317:Paper No. 108162, 2022.
  * [Kla97] M. Klazar.  Twelve countings with rooted plane trees.  European J. Combin., 18(2):195–210, 1997.
  * [Knu97] D. E. Knuth.  The art of computer programming. Vol. 1.  Addison-Wesley, Reading, MA, 1997.  Fundamental algorithms, Third edition.
  * [OEIS] OEIS Foundation Inc.  Entry A108891 in The On-Line Encyclopedia of Integer Sequences, 2022.  https://oeis.org/A108891.
  * [QG17] F. Qi and B.-N. Guo.  Some explicit and recursive formulas of the large and little Schröder numbers.  Arab J. Math. Sci., 23(2):141–147, 2017.
  * [Rus81] F. Ruskey.  Listing and counting subtrees of a tree.  SIAM J. Comput., 10(1):141–150, 1981.
  * [Sta99] R. P. Stanley.  Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1999.  With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.