%I #5 Oct 31 2013 12:17:33
%S 0,4,56,680,8360,108220,1492624,21994896,346014960,5798797620,
%T 103251381640,1947864594104,38827482815576,815655120856940,
%U 18013584786712480,417284952377904160,10117859730525070944
%N The work performed by a partial function f:{1,...,n}->{1,...,n} is defined to be work(f)=sum(|i-f(i)|,i in dom(f)); a(n) is equal to sum(work(f)) where the sum is over all injective partial functions f:{1,...,n}->{1,...,n}.
%H James East <a href="http://www.maths.usyd.edu.au/u/pubs/publist/preprints/2005/east-35.html">The Work Performed by a Transformation Semigroup</a>, preprint 2005.
%F ((n^3-n)/3)*sum(i=0...n-1, (n-1 choose i)^2*i!)
%e When n=2 there are 7 injective partial maps {1,2}->{1,2}. these are (1 2), (2 1), (1 -), (2 -), (- 1), (- 2) (- -). Adding up the work performed by these maps (from left to right as arranged above) gives a(2)=0+2+0+1+1+0+0=4.
%t f[n_] := (n^3 - n)Sum[Binomial[n - 1, k]^2*k!, {k, 0, n - 1}]/3; Array[f, 17] (* _Robert G. Wilson v_ *)
%Y Cf. A111867, A111873, A111903.
%K easy,nonn
%O 1,2
%A _James East_, Nov 23 2005
%E More terms from _Robert G. Wilson v_, Nov 26 2005
|