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 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\)