## 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.

: Primary 20M20; Secondary 05A10.

This paper is available as a pdf (160kB) file.

 Thursday, January 14, 2010