PreprintOn the work performed by a transformation semigroupJames East and Peter McNamaraAbstractA (partial) transformation \(\alpha\) on the finite set \(\{1,\ldots,n\}\) moves an element \(i\) of its domain a distance of \(ii\alpha\) units. The work \(w(\alpha)\) performed by \(\alpha\) is the sum of all of these distances. We derive formulae for the total work \(w(S)=\sum_{\alpha\in S}w(\alpha)\) performed by various semigroups \(S\) of (partial) transformations. One of our main results is the proof of a conjecture of Tim Lavers which states that the total work performed by the semigroup of all orderpreserving functions on an \(n\)element chain is equal to \((n1)2^{2n3}\). Keywords: Transformation semigroup, work.AMS Subject Classification: Primary 20M20; Secondary 05A10.
This paper is available as a pdf (160kB) file.
