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