Enumerating $k$th Roots in the Symmetric Inverse Monoid

Abstract

The symmetric inverse monoid, $\text{SIM}(n)$, is the set of all partial one-to-one mappings from the set $\{1,2,\dots ,n\}$ to itself under the operation of composition. Earlier research on the symmetric inverse monoid delineated the process for determining whether an element of $\text{SIM}(n)$ has a $k$th root. The problem of enumerating $k$th roots of a given element of $\text{SIM}(n)$ has since been posed, which is solved in this work. In order to find the number of $k$th roots of an element, all that is needed is to know the cycle and path structure of the element. Conveniently, the cycle and cycle-free components may be considered separately in calculating the number of $k$th roots. Since the enumeration problem has been completed for the symmetric group, this paper only focuses on the cycle-free elements of $\text{SIM}(n)$. The formulae derived for cycle-free elements of $\text{SIM}(n)$ here utilize integer partitions, similar to their use in the expressions given for the number of $k$th roots of permutations.