On the work performed by a transformation semigroup
James East, Peter J. McNamara · 2011
A partial transformation on the nite set f1; : : : ; ng moves an element i of its domain a distance of ji ij units. The work w() performed by is dened to be the sum of all of these distances. In this article we derive a formula for the total work w(S) = P 2S w() 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) transforma-tion 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 w(S) = 1jSjw(S) performed by an element of S.