The number of monogenic subsemigroups of the full transformation monoid
Mathematics
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
$$\begin{aligned} \mathbf{s}(n) & = \text{ the number of non-isomorphic cyclic subgroups of } S_n\\ \mathbf{t}(n) & = \text{ the number of non-isomorphic monogenic subsemigroups of } T_n. \end{aligned}$$
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:
$$1 + 1 + 1 + 1 + 1,\ 2 + 1 + 1 + 1,\ 2 + 2 + 1,\ 3 + 1 + 1,\ 3 + 2,\ 4 + 1,
5.$$
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
\[f(i) = \begin{cases} p(i) & \text{if } 1 \leq i \leq m \\ i - 1 & \text{if } m + 1\leq i \leq k \\ m & \text{if } i > k. \end{cases} \]
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\)
Computing the values - first attempt
Theorem 1 gives an explicit formula for the number $\mathbf{t}(n)$ of monogenic subsemigroups of the full transformation monoid $T_n$ in terms of the numbers $\mathbf{s}(k)$ of cyclic subgroups of the symmetric group $S_k$. In this section we describe how to actually compute $\mathbf{s}(k)$, and hence how to compute $\mathbf{t}(k)$. As mentioned above,
\[ \mathbf{s}(k) = |\{\operatorname{lcm}(a_1, a_2, \ldots, a_l):a_1 + \cdots + a_l = k\}|. \]
One approach to computing $\mathbf{s}(k)$ is more or less clear:
- generate all of the distinct partitions of $k$;
- find the least common multiple (lcm) of the numbers in each partition;
- count the number of distinct such lcms.
Generating integer partitions is a classical problem; see . A succinct implementation from https://stackoverflow.com/questions/10035752/ in python is:
def partitions(n, I=1):
yield (n,)
for i in range(I, n//2 + 1):
for p in partitions(n-i, i):
yield (i,) + p
[x for x in partitions(5)]
# [(5,), (1, 4), (1, 1, 3), (1, 1, 1, 2), (1, 1, 1, 1, 1), (1, 2, 2), (2, 3)]If $a, b\in \mathbb{N}$, then:
$$ \operatorname{lcm}(a, b) = \frac{ab}{\gcd(a, b)} $$
and so we can compute $\operatorname{lcm}(a, b)$ by first finding $\gcd(a, b)$ using the Euclidean algorithm. One succinct implementation in python is:
def gcd(a,b):
while b > 0:
a, b = b, a % b
return a
gcd(2, 3) # 1Mostly, we want to compute the lcm of more than two numbers, which we can do by remembering that $\operatorname{lcm}$ is associative, meaning that
$$ \operatorname{lcm}(a, b, c) = \operatorname{lcm}(\operatorname{lcm}(a, b), c) = \operatorname{lcm}(a, \operatorname{lcm}(b, c)). $$
In python:
def lcm(x):
a = x[0]
for b in x[1:]:
a = a * b // gcd(a, b)
return a
lcm((2, 3, 3, 4, 5)) # 60Putting together the previous sections, the following python function can be used to compute some values of $\mathbf{s}(n)$:
def number_of_cyclic_subgroups(n):
return len(set(lcm(x) for x in partitions(n)))
[number_of_cyclic_subgroups(n) for n in range(1, 20)]
# [1, 2, 3, 4, 6, 6, 9, 11, 14, 16, 20, 23, 27, 31, 35, 43, 47, 55, 61]Popping these numbers into the oeis shows us sequence number A009490 (and might give us some more confidence that the code above is correct); see Table 1.
\begin{array}{l|lllllllllllll} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\\hline \mathbf{s}(n) & 1& 2& 3& 4& 6& 6& 9& 11& 14& 16& 20& 23& 27& 31& 35& 43& 47& 55& 61 \end{array}
By Theorem 1, the number $\mathbf{t}(n)$ of monogenic subsemigroups of the full transformation monoid is $\mathbf{t}(n)=\mathbf{s}(1)+\cdots+\mathbf{s}(n)$. In python:
def number_of_monogenic_subsemigroups(n):
return sum(number_of_cyclic_subgroups(m) for m in range(1, n + 1))
[number_of_monogenic_subsemigroups(n) for n in range(1, 20)]
# [1, 3, 6, 10, 16, 22, 31, 42, 56, 72, 92, 115, 142, 173, 208, 251, 298, 353, 414]Putting this sequence into the oeis yields:
Sorry, but the terms do not match anything in the table.
So, it seems like we computed something new. The first 19 terms in the sequence can be seen in Table 2.
\begin{array}{r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\\hline \mathbf{t}(n) & 1 & 3 & 6 & 10 & 16 & 22 & 31 & 42 & 56 & 72 & 92 & 115 & 142 & 173 & 208 & 251 & 298 & 353 & 414 \end{array}