The Work Performed by a Transformation Semigroup

James East


A partial transformation \al on the finite set {1,\ldots,n} moves an element i of its domain a distance of |i-i\al| units. The \emph{work} w(\al) performed by \al is defined to be the sum of all of these distances. In this article we derive a formula for the total work w(S)=∑\al∈ Sw(\al) performed by a subset S of the partial transformation semigroup \PTn. We then obtain explicit formulae for w(S) when S is one of seven important subsemigroups of \PTn: the partial transformation semigroup, the (full) transformation semigroup, the symmetric group, and the symmetric inverse semigroup, as well as their order-preserving submonoids. Each of these formulae gives rise to a formula for the average work \wb(S)=\frac{1}{|S|}w(S) performed by an element of S.

Keywords: Transformation semigroup, work.

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

This paper is available as a gzipped postscript (176kB) file and a PDF (216kB) file.
Tuesday, November 15, 2005