A111874 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}.

0, 4, 56, 680, 8360, 108220, 1492624, 21994896, 346014960, 5798797620, 103251381640, 1947864594104, 38827482815576, 815655120856940, 18013584786712480, 417284952377904160, 10117859730525070944

Offset

1,2

Links

Table of n, a(n) for n=1..17.

James East The Work Performed by a Transformation Semigroup, preprint 2005.

Formula

((n^3-n)/3)*sum(i=0...n-1, (n-1 choose i)^2*i!)

Example

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.

Mathematica

f[n_] := (n^3 - n)Sum[Binomial[n - 1, k]^2*k!, {k, 0, n - 1}]/3; Array[f, 17] (* Robert G. Wilson v *)

Crossrefs

Cf. A111867, A111873, A111903.

Sequence in context: A333294 A130219 A222687 * A297944 A298555 A240298

Adjacent sequences: A111871 A111872 A111873 * A111875 A111876 A111877

Keyword

easy,nonn

Author

James East, Nov 23 2005

Extensions

More terms from Robert G. Wilson v, Nov 26 2005

Status

approved