Counting monogenic monoids and inverse monoids

ABSTRACT

In this short note, we show that the number of monogenic submonoids of the full transformation monoid of degree n for $n>0$, equals the sum of the number of cyclic subgroups of the symmetric groups on 1 to n points. We also prove an analogous statement for monogenic subsemigroups of the finite full transformation monoids, as well as monogenic inverse submonoids and subsemigroups of the finite symmetric inverse monoids.

Keywords:

• Inverse semigroup
• monogenic semigroup
• transformation semigroup

2020 Mathematics Subject Classification:

• 20M20

1. Introduction

In this short note we count, up to isomorphism, the number of monogenic subsemigroups and submonoids of the finite full transformation monoids and the number of monogenic inverse subsemigroups and submonoids of the finite symmetric inverse monoids.

The question of counting the monogenic subsemigroups of the finite full transformation monoids was posed to the third author by A. Egri-Nagy in the course of their work on [5]. The general case of counting all of the subsemigroups of the finite full transformation monoids up to isomorphism seems extremely complex, but the highly restricted case of the monogenic subsemigroups is tractable. The numbers of subsemigroups of the full transformation monoids and the number of inverse subsemigroups of the symmetric inverse monoids are very large (see for example Corollary 3.3 of [9] or Theorem 9.1 in [1]). So, unsurprisingly, the monogenic semigroups account for a tiny proportion of the subsemigroups of these monoids.

The question of counting the monogenic inverse subsemigroups of the finite symmetric inverse monoids arose naturally in the context of another project of the authors of the present note. Every finite semigroup can be embedded in a full transformation monoid, and every finite inverse semigroup can be embedded in some symmetric inverse monoid. As such counting, or characterizing, the transformation monoids, or inverse monoids, that can be found as subsemigroups of any given full transformation monoid, or symmetric inverse monoid, seems natural enough. The structure of monogenic semigroups is rather straightforward, and while the structure of monogenic inverse semigroups is more involved, they are sufficiently straightforward that it is possible to enumerate them. Similar questions have been studied for finite symmetric groups, see, for example, [6] and the references therein, and for other classes of semigroups and monoids; see, for example, [3] and [10].

There are a number of results in the literature relating to monogenic inverse semigroups. Preston [8] presented a description of all monogenic inverse monoids up to isomorphism. This description was independently obtained by Conway, Duncan and Paterson [2] in the context of $C^{\ast }$-algebras. Dyadchenko [4] gave a number of results on monogenic inverse semigroups by studying free monogenic inverse semigroups. Some of the results in [4] and [8] overlap with the results in the present paper, and the authors have endeavored to point this out.

Throughout this short note, we denote the natural numbers $\{0,1,\dots \}$ by $\mathbb{N}$. If $n\in \mathbb{N}$ and $n\ge 0$, then the symmetric group, denoted $S_n$, is the group of all permutations of the set $\{1,\dots ,n\}$. The full transformation monoid is the monoid of all functions from the set $\{1,\dots ,n\}$ to itself (called transformations) and the semigroup operation is the usual composition of functions. The symmetric inverse monoid $I_n$ is the set of all bijections between subsets of $\{1,\dots ,n\}$, with the operation of composition of binary relations. Throughout the remainder of this note we will write functions to the right of their arguments and compose from left to right.

We distinguish two notions of being “generated” by a single element, for monoids, and inverse monoids as follows. A monoid M is monogenic if there is $m\in M$ such that $M=\{m^n:n\in \mathbb{N}\}$. An inverse monoid M is a monogenic inverse monoid if there exists $m\in M$ such that M is the monoid generated by m and $m^{-1}$. Note that in a monogenic monoid M, or inverse monoid, the identity is $m^0$ for every $m\in M$. For finite groups, these two definitions coincide, and so a monogenic finite group is just a cyclic group. We elaborate why we have chosen to consider monoids rather semigroups after stating the main theorem below.

Let $\mathbf{s},\mathbf{t},\mathbf{i}:\mathbb{N}\to \mathbb{N}$ be defined by $$\begin{array}{cc}(n)\mathbf{s}\hfill & =\text{ the number of non- isomorphic cyclic subgroups of }{S}_n\hfill \\ (n)\mathbf{t}\hfill & =\text{ the number of non-isomorphic monogenic submonoids of }{T}_n\hfill \\ (n)\mathbf{i}\hfill & =\text{ the number of non-isomorphic monogenic inverse submonoids of }{I}_n.\hfill \end{array}$$

Since cyclic groups are determined up to isomorphism by their size, it follows that $(n)\mathbf{s}$ is the number of distinct orders of elements in $S_n$; see [11] and Table 1 for some values for $(n)\mathbf{s}$. Note that we will follow the convention that $(1)\mathbf{s}=1$ (and $(0)\mathbf{s}=1$ by virtue of the trivial group being cyclic). A partition of $n\in \mathbb{N}$ is a k-tuple $(a_1,\dots ,a_k)$, where $k\ge 0$, $a_1\ge \cdots \ge a_k\ge 1$ and $a_1+\cdots +a_k=n$. For instance, the partitions of 5 are: $$1+1+1+1+1,\hspace{1em}2+1+1+1,\hspace{1em}2+2+1,\hspace{1em}3+1+1,\hspace{1em}3+2,\hspace{1em}4+1,\hspace{1em}5.$$

Table 1. The values of the functions $(n)\mathbf{s}$, $(n)\mathbf{t}$, and $(n)\mathbf{i}$ for some small values of n.

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
$(n)\mathbf{s}$	1	1	2	3	4	6	6	9	11	14	16	20	23	27	31	35	43	47	55	61
$(n)\mathbf{t}$	1	1	3	6	10	16	22	31	42	56	72	92	115	142	173	208	251	298	353	414
$(n)\mathbf{i}$	1	2	4	7	11	17	23	32	43	57	73	93	116	143	174	209	252	299	354	415

There is a unique partition of 0, namely, the empty partition $\varnothing$. We use the standard conventions that an empty sum equals 0 and an empty product equals 1; in particular, $\text{lcm}(\varnothing )=1$.

The order of a permutation $f\in S_n$ is just the least common multiple of the lengths of its cycles, and so $(n)\mathbf{s}$ is the size of the set $\{\text{lcm}(a_1,a_2,\dots ,a_k):a_1+\cdots +a_k=n\}$.

The purpose of this short note is to prove the following result.

Theorem 1.

Let $n\in \mathbb{N}$ such that $n>1$. Then $$(n)\mathbf{t}=\sum _{k=1}^n(k)\mathbf{s}\hspace{1em}\text{ and }\hspace{1em}(n)\mathbf{i}=\sum _{k=0}^n(k)\mathbf{s}=(n)\mathbf{t}+1.$$

See Table 1 for the values of $(n)\mathbf{s}$, $(n)\mathbf{t}$, and $(n)\mathbf{i}$ for some small values of n.

A semigroup S is monogenic if there is $s\in S$ such that $S=\{s^n:n>0,n\in \mathbb{N}\}$. As such a monogenic subsemigroup S of $T_n$ contains the identity transformation $1_n\in T_n$; if and only if S is a monogenic submonoid of $T_n$ (in this case S is a cyclic group).

It follows that every monogenic submonoid M of $T_n$ is either a cyclic group; or $M\cap T_n\setminus S_n$ is a monogenic subsemigroup and $M\cap S_n=\left\{1_n\right\}$. Conversely, every monogenic subsemigroup of $T_n$ is either a monogenic submonoid of $T_n$ (and hence a group) or can be obtained from a monogenic submonoid by removing the identity element. Thus the number of monogenic subsemigroups of $T_n$ up to isomorphism is the number of cyclic subgroups of $S_n$ plus the number of monogenic subsemigroups of $T_n\setminus S_n$ that are not groups. As we will see later, the number of monogenic subsemigroups of $T_n\setminus S_n$, that are groups is $(n-1)\mathbf{s}$. Analogous comments hold for monogenic inverse subsemigroups and inverse submonoids of $I_n$. From this discussion we obtain the following corollary to Theorem 1.

Corollary 2.

The number of monogenic subsemigroups of $T_n$ equals $(n)\mathbf{t}-(n-1)\mathbf{s}$ up to isomorphism. The number of monogenic inverse subsemigroups of $I_n$, up to isomorphism, is $(n)\mathbf{i}-(n-1)\mathbf{s}$.

There is a natural injection from isomorphism types of submonoids of $T_n$ to inverse submonoids of $I_n$ defined by mapping a generating transformation to a generating partial permutation with the same period and threshold. This is almost a bijection, however, it does not map onto any element of threshold n as $T_n$ contains no such element. This element is unique up to the isomorphism type of a submonoid it generates.

2. Monogenic transformation monoids

In this section, we collect a small number of facts about monogenic transformation monoids that we require to prove Theorem 1.

If M is a finite monoid and $x\in M$, then the threshold $t\in \mathbb{N}$ and period $p\in \mathbb{N}$ of x are the least values such that $p>0$ and $x^{t+p}=x^t$.

Lemma 3

.

Let M be a monoid and let $a,b\in M$. Then the monogenic submonoids of M generated by a and b, respectively, are isomorphic if and only if the threshold and period of a equal those of b.

To prove Lemma 3, it is not difficult to show the unique homomorphism extending the map $a\mapsto b$ is an isomorphism whenever the thresholds and periods of a and b coincide. A special case of Lemma 3 is when $M=S_n$, where the lemma asserts that $〈a〉$ and $〈b〉$ are isomorphic if and only if $|〈a〉|=|〈b〉|$, as mentioned above.

Recall that a digraph $\Gamma$ is a pair $(V,E)$ consisting of a vertex set V and an edge set $E\subseteq V\times V$. A digraph is functional if for every $u\in V$ there exists a unique $v\in V$ such that $(u,v)\in E$. Suppose that $D_n$ denotes the set of functional digraphs with vertex set $\{1,\dots ,n\}$. It is straightforward to verify that the function mapping f to the functional digraph ${\Gamma }_f$ with vertices $V=\{1,\dots ,n\}$ and edges $E=\{(v,(v)f):v\in V\}$ is a bijection. We give an example of a functional digraph of a transformation in Figure 1.

Figure 1. Functional digraph of a transformation on 11 points with threshold 2 and period 3.

Lemma 4

.

Let $n,p,t\in \mathbb{N}$ be such that $n>0$ and $p>0$. Then t and p are the threshold and period of an element of $T_n$ if and only if there exists $m\in \mathbb{N}\setminus \left\{0\right\}$ with $m\le n$, such that p is the order of an element of $S_m$, and $t\in \{0,\dots ,n-m\}$.

Proof.

The period of a transformation $f\in T_n$ is equal to the least common multiple p of the lengths of the cycles in the digraph ${\Gamma }_f$, and the threshold of f is equal to the maximal number t of edges in a path $(x_0,x_1,\dots ,x_t)$ where the vertex $x_t$ belongs to a cycle but the vertices $\{x_0,\dots ,x_{t-1}\}$ do not. In particular, the threshold of $f\in T_n$ is between 0 and $n-1$, inclusive. If $g\in S_m$ is any permutation, then there exists a transformation $f\in T_n$ such that the period of f equals the order p of g and the threshold of f is any value in $t\in \{0,\dots ,n-m\}$; one such transformation is $$(i)f=\{\begin{array}{cc}(i)g\hfill & \text{if }1\le i\le m\hfill \\ i-1\hfill & \text{if }m+1\le i\le m+t\hfill \\ i\hfill & \text{if }i>m+t.\hfill \end{array}$$

This transformation has threshold t and period p, since $$(i)f^{t+p}=\{\begin{array}{cc}(i)g^{t+p}=(i)g^t=(i)f^k\hfill & \text{ if }1\le i\le m\hfill \\ ((i)f^{i-m})f^{p+t-(i-m)}=(m)f^{p+t-(i-m)}=(m)f^{t-(i-m)}=(i)f^t\hfill & \text{ if }m+1\le i\le m+t\hfill \\ (i)f^{t+p}=i=(i)f^t\hfill & \text{ if }i>m+t\hfill \end{array}$$shows that the threshold and period are at most t and p, respectively. As f restricts to a permutation of order p, the period of f can be no less than p, and so the period of f equals p.

If $x<t$ and $t>0$, then $(m+t)f^x\notin \{1,2,\dots ,m\}$, $(m+t)f^{x+pt}\in \{1,2,\dots ,m\}$. In particular, $(m+t)f^x\ne (m+t)f^{x+p}$, and so the threshold of f does not equal x, and therefore it must equal t. □

3. Monogenic inverse monoids of partial permutations

We now consider monogenic inverse submonoids of $I_n$. Many of the results in this section have analogous or equivalent results in [8]. We include proofs for completeness.

Throughout this section we consider the monogenic inverse monoid $S_{n,k}$ defined by the following inverse monoid presentation (i.e., $S_{n,k}$ is isomorphic to the quotient of the monogenic free inverse monoid by the least congruence containing the relations): (5) $${\mathcal{P}}_{n,k}=\text{Inv}〈x|x^n{x}^{-n}=x^{n+1}{x}^{-(n+1)},x^n{x}^{-n}=x^n{x}^{-n}{x}^k〉$$(5) for an arbitrary but fixed $k,n\in \mathbb{N}$ with $k>0$.

By [7], elements of the free inverse monoid are uniquely determined by the corresponding Munn tree. The Munn tree of an element of the monogenic free inverse monoid can be defined for any $a,b,c\in \mathbb{N}$ such that $a,c\le b$ to be the chain of length b where the initial state is the node at distance a from the start of the chain, and the terminal node is distance c from the start. Hence every element of a monogenic free inverse monoid is represented by a word of the form: $$x^{-a}{x}^b{x}^{-b}{x}^c\in {\{x,x^{-1}\}}^{*}$$where $a,b,c\in \mathbb{N}$ and $a,c\le b$ and ${\{x,x^{-1}\}}^{*}$ is the free monoid over the alphabet $\{x,x^{-1}\}$. We give an example of a Munn tree in Figure 2.

Figure 2. Munn tree for the free inverse monoid element $\mathit{aba}{a}^{-1}baa{a}^{-1}{a}^{-1}b$ with start $\alpha$ and end $\omega$.

We start by defining a set of representative words for each element, which we use to classify all finite monogenic inverse monoids.

Lemma 6

(see also Proposition 4 of [4]).

The set $$W:=\{x^{-a}{x}^b{x}^{-b}{x}^c\in {\{x,x^{-1}\}}^{*}:0\le a,c\le b<n\}\cup \{x^{-a}{x}^n{x}^{-n}{x}^c\in {\{x,x^{-1}\}}^{*}:0\le a,c<k\}$$contains representatives for all elements of $S_{n,k}$. That is to say, if $\mathit{FIM}(\{x\})$ is the free inverse monoid on $\left\{x\right\}$, and $\Psi :{\{x,x^{-1}\}}^{*}\to \mathit{FIM}(\{x\})$, $\Phi :\mathit{FIM}(\{x\})\to S_{n,k}$ are the natural homomorphisms, then $(\Psi \Phi ){\upharpoonright }_W$ is surjective.

Proof.

As mentioned above, every element of $S_{n,k}$, can be given as $x^{-a}{x}^b{x}^{-b}{x}^c$ where $a,c\le b$. If $b<n$, then $x^{-a}{x}^b{x}^{-b}{x}^c$ belongs to the first set in the union in the statement of the lemma.

By the relations in (5), we know that $x^n{x}^{-n}=x^n{x}^{-n}{x}^k$ and by inverting this it follows that $x^n{x}^{-n}=x^{-k}{x}^n{x}^{-n}$. Hence, again using the given relations, if $b\ge n$, then $$x^{-a}{x}^b{x}^{-b}{x}^c=x^{-a\text{ mod }k}{x}^n{x}^{-n}{x}^{c\text{ mod }k}.$$

In particular, if $b\ge n$ and $a,c\le b$, then $x^{-a}{x}^b{x}^{-b}{x}^c$ is equivalent to a word in the second set in the union in the statement of the lemma. □

If M is an inverse monoid, then we denote the monogenic inverse submonoid of M generated an element $f\in M$ by $〈f〉$. An element $f\in I_n$ is called a chain if the there exists $x\in \{1,\dots ,n\}\setminus \text{im}(f)$ such that $\text{dom}(f)=\{(x)f^i:i\in \{0,\dots ,|\text{dom}(f)|-1\left\}\right\}$ (and so $\text{im}(f)=\{(x)f^i:i\in \{1,\dots ,n\left\}\right\}$). The length of a chain f is denoted $\left|f\right|$ (the cardinality of f as a subset of $\{1,\dots ,n\}\times \{1,\dots ,n\}$). We denote a chain f by $[x,(x)f,\dots ,(x)f^{\left|f\right|-1}]$. Note that we will sometimes implicitly refer to a chain on 1 point of (length 0), this should be interpreted as the empty function, for example in Lemma 9, if $a=1$ then $x=(2,3,\dots ,b+1)$.

To classify all monogenic inverse monoids, we must first classify those generated by chains.

Lemma 7.

Let $f,g\in I_n$ be chains such that $\left|f\right|\ge \left|g\right|$. Then there exists a surjective homomorphism $\varphi :〈f〉\to 〈g〉$.

Proof.

Clearly if $\left|f\right|=\left|g\right|$, then the homomorphism from $〈f〉$ to $〈g〉$ mapping f to g is an isomorphism. Suppose that $\left|f\right|>\left|g\right|$. We may assume without loss of generality that $f=[1,\dots ,n]$ and that $g=[1,\dots ,n-1]$. It suffices to show that there exists a set X such that $〈g〉$ acts faithfully by partial perms on X and that $〈f〉$ has the same action by partial perms on X as $〈g〉$. We set $X=\{(1,2),\dots ,(n-1,n)\}$ and define the actions of f and g by $$(a,a+1)f=((a)f,(a+1)f)\hspace{1em}(b,b+1)g=((b)g,(b)g+1).$$

It is routine to verify that these two actions are equal. □

We require the following lemma, which is a special case of [8, Theorem 7], we have included a proof here for the sake of completeness.

Lemma 8

.

If M is a finite monogenic inverse submonoid of $I_n$, then there exist $a,b\in \mathbb{N}$ such that $a+b=n$ and M is isomorphic to the inverse submonoid of $I_n$ generated by $$x=[1,\dots ,a]\cup p.$$where p is some permutation on the set $\{a+1,\dots ,b+1\}$. Moreover, the monoid is isomorphic to the submonoid of $I_{a+\left|p\right|}$ generated by $[1,\dots ,a]\cup (a+1,\dots ,a+|p|)$.

Proof.

If $M=〈m〉$ is a monogenic inverse monoid, then M is isomorphic to an inverse submonoid of $I_n$ for some n, and so we may suppose that M is an inverse submonoid of $I_n$. Thus m is a union of disjoint cycles $y_1,\dots ,y_k$ and chains $h_1,\dots ,h_l$, and M is an inverse submonoid of the direct product $$M=\prod _{i=1}^k〈y_i〉\times \prod _{j=1}^l〈h_j〉.$$

If $k=1$ and $l=1$, then there is nothing to prove, and so we suppose that $k\ge 2$ or $l\ge 2$.

If $l\ge 2$, then we define x to be a chain of length equal to the maximum of the lengths of $h_{m-1}$ and $h_m$ and we define $$U=\prod _{i=1}^k〈y_i〉\times 〈x〉\times \prod _{j=1}^{l-2}〈h_j〉.$$

We define $\varphi :U\to M$ to be the homomorphism induced by the isomorphisms $y_i\mapsto y_i$ for all i, $h_j\mapsto h_j$ for all $j<l-1$, and such that $x\mapsto (h_{l-1},h_l)$, which is also an isomorphism by Lemma 7. Hence $\varphi$ is an isomorphism when restricted to $〈(y_1,\dots ,y_k,x,h_1,\dots ,h_{l-2})〉$, and this monoid has a generator with one fewer chains than the generator of M.

Suppose that $k\ge 2$. Then we define x to be any cycle of length $\text{lcm}(|y_{k-1}|,|y_k|)$ and we define $$U=\prod _{i=1}^{k-2}〈y_i〉\times 〈x〉\times \prod _{j=1}^l〈h_j〉.$$

We define $\varphi :U\to M$ to be the homomorphism induced by the isomorphisms $y_i\mapsto y_i$ for $i<k-1$, $h_j\mapsto h_j$ for all j, and the isomorphism $〈x〉\to 〈(y_{k-1},y_k)〉$ induced by $x\mapsto (y_{k-1},y_k)$. Then the restriction of $\varphi$ to $〈(y_1,\dots ,y_{k-2},x,h_1,\dots ,h_l)〉$ is an isomorphism of $〈(y_1,\dots ,y_{k-2},x,h_1,\dots ,h_l)〉$ and M. In particular, these monoids are isomorphic, and the former has a generator with one fewer cycles than the generator of M. □

When one is not concerned with embedding an inverse monoid into a partial permutation monoid on a specific number of points, the following formulation of the above lemma is more natural.

Lemma 9.

If M is a finite monogenic inverse monoid, then there exist $a,b,n\in \mathbb{N}$ such that M is isomorphic to the inverse submonoid of $I_n$ generated by $$x=[1,\dots ,a]\cup (a+1,\dots ,a+b).$$

Proof.

This is immediate from Lemma 8. □

We are now ready to give the theorem which allows us to classify the isomorphism types of finite monogenic inverse monoids. This theorem is essentially a reformulation of Theorem 7 from [8].

Theorem 10.

The inverse submonoid of $I_{n+k}$ generated by a partial permutation $$[1,2,\dots ,n]\cup (n+1,n+2,\dots ,n+k)$$is isomorphic to $S_{n,k}$ defined in (5) for all $n\ge 0$ and $k\ge 1$. Moreover, if $m\ge 0$ and $l\ge 1$, then $S_{n,k}\cong S_{m,l}$ if and only if $(n,k)=(m,l)$.

Proof.

Since the set containing normal forms for $S_{n,k}$ from Lemma 6 is finite, the monoid $S_{n,k}$ is finite. It follows by Lemma 9 that there are $a,b\in \mathbb{N}$ such that $S_{n,k}$ is isomorphic to the inverse submonoid of $I_{a+b}$ generated by the partial permutation $$x=[1,\dots ,a]\cup (a+1,\dots ,a+b).$$

We will show that $a=n$ and $b=k$ (unless $k=1$ in which case b may be 0). The relation $x^n{x}^{-n}=x^{n+1}{x}^{-(n+1)}$ implies that $${[1,\dots ,a]}^n{[1,\dots ,a]}^{-n}={[1,\dots ,a]}^{n+1}{[1,\dots ,a]}^{-(n+1)}.$$

This can only hold if $a\le n$. Thus, the relation $x^n{x}^{-n}=x^n{x}^{-n}{x}^k$ implies that $${\text{id}}_{\{a+1,\dots ,a+b\}}=x^n{x}^{-n}=x^n{x}^{-n}{x}^k={(a+1,\dots ,a+b)}^k$$where ${\text{id}}_{\{a+1,\dots ,a+b\}}$ is the identity function on the set $\{a+1,\dots ,a+b\}$. Thus $b|k$ and, in particular $b\le k$ since $k\ge 1$.

It suffices to show that $a\ge n$ and $b\ge k$ (unless $k=1$, in which case b is also allowed to be 0). Seeking a contradiction suppose that $a<n$. Since the relations in (5) hold for $y=[1,\dots ,n]$, the inverse monoid generated by y is a homomorphic image of $S_{n,k}$. In particular, $x^a{x}^{-a}\ne x^n{x}^{-n}$ since $y^a{y}^{-a}\ne y^n{y}^{-n}$ (the latter is the empty function and the former is not). However, we proved above that $x^a{x}^{-a}={\text{id}}_{\{a+1,\dots ,a+b\}}=x^n{x}^{-n}$, which is a contradiction.

If $1<k$ and $b<k$, then a similar argument implies (the contradiction) that the relation $x^n{x}^{-n}=x^n{x}^{-n}{x}^b$ does not hold in $S_{n,k}$ since it does not hold in the image of the homomorphism extending $x\mapsto (1,\dots ,k)$. □

4. Proof of the main theorem

Proof of Theorem 1.

We start by proving the formula for $(n)\mathbf{t}$. Let A be the set of pairs $(t,p)$ such that t and p are the threshold and period of some transformation of degree n and let $$A_t=\{p\in \mathbb{N}\setminus \{0\}:(t,p)\in A\}.$$

Then, by Lemma 3, $\left|A\right|=(n)\mathbf{t}$ and $\left|A\right|=\left|A_0\right|+\cdots +\left|A_{n-1}\right|=(n)\mathbf{t}$. It therefore suffices to show that $\left|A_t\right|=\mathbf{s}(n-t)$ for all $t\in \{0,\dots ,n-1\}$.

If $t\in \{0,\dots ,n-1\}$ and $B_t$ is the set of orders of elements in $S_{n-t}$, then clearly $\left|B_t\right|=(n-t)\mathbf{s}$ and it suffices to show that $A_t=B_t$. If $p\in B_t$, then we showed above that there exists a transformation $f\in T_n$ with threshold t and period p and so $p\in A_t$. Conversely, if $p\in A_t$, then, by the definition of $A_t$, there exists $f\in T_n$ with threshold t and period p. Since the threshold of f is t, there are at most $n-t$ points in any cycle of f, and so p is the order of a permutation in $S_{n-t}$. In other words, $p\in B_t$. Thus $$(n)\mathbf{t}=\sum _{i=0}^{n-1}\left|A_i\right|=\sum _{i=0}^{n-1}(n-i)\mathbf{s}=\sum _{i=1}^n(i)\mathbf{s},$$as required.

Next, we prove that the formula for $(n)\mathbf{i}$ in the statement of the theorem is correct. By Lemma 8, every monogenic inverse submonoid of $I_n$ is isomorphic to one generated by the disjoint union of a chain and permutation. Moreover, by Theorem 10, two such elements generate isomorphic inverse submonoids of $I_n$ if and only if the chains have the same length and the permutations have the same order. Hence for every length of chain i, the number of distinct monogenic inverse submonoids up to isomorphism is $(n-i)\mathbf{s}$. It follows that $$(n)\mathbf{i}=\sum _{i=0}^n(n-i)\mathbf{s}=\sum _{i=0}^n(i)\mathbf{s}.$$□

Acknowledgments

The authors would also like to thank A. Egri-Nagy for originally asking the question that gave rise to this paper, and J. East for discussing the case of the full transformation monoid with the third author.

Additional information

Funding

The second and third authors would like to thank the London Mathematical Society, the Heilbronn Institute for Mathematical Research, and the University of St Andrews, for their support of this work.