On the work performed by a transformation semigroup

James East and Peter McNamara

Abstract

A (partial) transformation \(\alpha\) on the finite set \(\{1,\ldots,n\}\) moves an element \(i\) of its domain a distance of \(|i-i\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 order-preserving functions on an \(n\)-element chain is equal to \((n-1)2^{2n-3}\).

Keywords: Transformation semigroup, work.

AMS Subject Classification: Primary 20M20; Secondary 05A10.