login
a(n) = Sum_{r=0..n-1} Sum_{s=r+1..n} s! * r^(n-s).
4

%I #13 Dec 29 2017 17:44:28

%S 0,1,4,20,116,776,5912,50648,482552,5065016,58099832,723315128,

%T 9715154552,140051879096,2157103991672,35355232693688,614453167841912,

%U 11287370521073336,218535622980161912,4447889360078673848,94944254697268017272,2120984032794061422776,49489160848954807154552,1203943675008917425902008,30486416629523244528307832

%N a(n) = Sum_{r=0..n-1} Sum_{s=r+1..n} s! * r^(n-s).

%C The expression a(n)/n! = A190186/A190187 arises in the analysis of bubble sort [Knuth].

%D D. E. Knuth, The Art of Computer Programming, Vol. 3, Section 5.2.2, p. 129.

%H G. C. Greubel, <a href="/A190194/b190194.txt">Table of n, a(n) for n = 0..445</a>

%p f:=proc(n) local t1,r,s;

%p t1:=add( add(s!*r^(n-s), s=r+1..n), r=0..n-1);

%p end;

%t Join[{0}, Table[Sum[n! + Sum[s!*k^(n - s), {s, k + 1, n - 1}], {k, 0, n - 1}], {n, 1, 50}]] (* _G. C. Greubel_, Dec 28 2017 *)

%o (PARI) for(n=0,30, print1(if(n==0,0, sum(k=0,n-1, n! + sum(s=k+1,n-1, s!*k^(n-s)))), ", ")) \\ _G. C. Greubel_, Dec 28 2017

%Y Cf. A190186, A190187.

%K nonn

%O 0,3

%A _N. J. A. Sloane_, May 05 2011