In this post we show how to count the number of monogenic subsemigroups of the full transformation monoid up to isomorphism.

Throughout this post, we denote the natural numbers $$\{0, 1, \ldots\}$$ by $${\mathbb{N}}$$. The symmetric group and full transformation semigroup on $$\{1, \ldots, n\}$$, $$n\in {\mathbb{N}}$$, are denoted $$S_n$$ and $$T_n$$, respectively. A subsemigroup of a semigroup $$S$$ is monogenic if it can be generated by a single element; monogenic subsemigroups of finite groups are just cyclic subgroups. Let $$\mathbf{s},\mathbf{t}: {\mathbb{N}}{\longrightarrow}{\mathbb{N}}$$ be defined by

Since cyclic groups are determined up to isomorphism by their size, it follows that $$\mathbf{s}(n)$$ is the number of distinct orders of elements in $$S_n$$. The purpose of this post is to prove the following result.

Theorem 1. Let $$n\in {\mathbb{N}}$$. Then $$\mathbf{t}(n)=\mathbf{s}(1)+\cdots+\mathbf{s}(n)$$.

A partition of $$n\in {\mathbb{N}}$$ is a $$k$$-tuple $$(a_1, \ldots, a_k)$$, where $$k \geq 0$$, $$a_1\geq\cdots\geq a_k\geq1$$, and $$a_1 + \cdots + a_k = n$$. For instance, the partitions of $$5$$ are:

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, $${\operatorname{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 $${\mathbf{s}}(n)$$ is the size of the set $$\{\operatorname{lcm}(a_1, a_2, \ldots, a_k):a_1 + \cdots + a_k = n\}.$$

If $$M$$ is a finite monoid and $$x\in M$$, then the index and period of $$x$$ are the least values $$m \in {\mathbb{N}}$$ and $$r \in {\mathbb{N}}\setminus\{0\}$$ such that $$x ^ {m + r} = x ^{m}$$, respectively. We define $$x ^ 0$$ to be the identity element of $$M$$ for all $$x\in M$$. Consequently, the only elements in $$M$$ with index $$0$$ are in the group of units.

Lemma 2. Let $$S$$ be a semigroup and let $$s, t\in S$$. Then $${\langle s\rangle}$$ and $${\langle t\rangle}$$ are isomorphic if and only if the index and period of $$s$$ equal those of $$t$$.

A special case of Lemma 2 is when $$S = S_n$$, where the lemma asserts that $${\langle s\rangle}$$ and $${\langle t\rangle}$$ are isomorphic if and only if $$|{\langle s\rangle}|= |{\langle t\rangle}|$$, 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,\ldots,n\}$$. It is straightforward to verify that the function mapping $$f$$ to the functional digraph $$\Gamma_f$$ with vertices $$V = \{1, \ldots, n\}$$ and edges $${\{(v, f(v)):v\in V\}}$$ is a bijection.

The period of a transformation $$f\in T_n$$ is equal to the least common multiple of the lengths of the cycles in the digraph $$\Gamma_f$$, and the index of $$f$$ is equal to the maximal number of edges in a path $$(x_1, x_2, \ldots, x_k)$$ where $$x_k$$ belongs to a cycle of $$\Gamma_f$$ but $$x_1, x_2, \ldots, x_{k - 1}$$ do not. In particular, the index of $$f\in T_n$$ is between $$0$$ and $$n - 1$$, inclusive.

If $$p \in S_m$$ is any permutation, then there exists a transformation $$f\in T_n$$ such that the period of $$f$$ equals the order of $$p$$ and the index of $$f$$ is any value in $$k \in \{0, \ldots, n - m\}$$; one such transformation is

Proof of Theorem 1. Let $$A$$ be the set of pairs $$(m, r)$$ such that $$m$$ and $$r$$ are the index and period of some transformation of degree $$n$$ and let $A_m = {\{r\in{\mathbb{N}}\setminus\{0\}:(m,r)\in A\}}.$ Then, by Lemma 2, $$|A| = {\mathbf{t}}(n)$$ and $$|A| = |A_0| + |A_1| + \cdots + |A_{n - 1}| = {\mathbf{t}}(n)$$. It therefore suffices to show that $$|A_m|={\mathbf{s}}(n-m)$$ for all $$m \in \{0, \ldots, n - 1\}$$.

If $$m \in \{0, \ldots, n - 1\}$$ and $$B_m$$ is the set of orders of elements in $$S_{n-m}$$, then clearly $$|B_m| = {\mathbf{s}}(n - m)$$ and it suffices to show that $$A_m = B_m$$.

If $$r \in B_m$$, then we showed above that there exists a transformation $$f\in T_n$$ with index $$m$$ and period $$r$$ and so $$r \in A_m$$.

Conversely, if $$r\in A_m$$, then, by the definition of $$A_m$$, there exists $$f\in T_n$$ with index $$m$$ and period $$r$$. Since the index of $$f$$ is $$m$$, there are at most $$n - m$$ points in any cycle of $$f$$, and so $$r$$ is the order of a permutation in $$S_{n -m}$$. In other words, $$r\in B_m$$. $$\blacksquare$$