login
Numerator of expression W_n occurring in analysis of bubble sort.
7

%I #18 Dec 31 2017 01:41:00

%S 1,2,10,29,97,739,6331,8617,633127,1037497,90414391,1214394319,

%T 17506484887,38519714137,4419404086711,10972377997177,

%U 1410921315134167,27316952872520239,555986170009834231,154130283599461067,265123004099257677847,883735015159907270617,150492959376114678237751,293138621437723505079883,100289605416287509517021527

%N Numerator of expression W_n occurring in analysis of bubble sort.

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

%H G. C. Greubel, <a href="/A190186/b190186.txt">Table of n, a(n) for n = 1..445</a>

%F W_n = Sum_{r=0..(n-1)}( Sum_{s=(r+1)..n} s!*r^(n-s) )/n!.

%F W_n = numerator(A190194(n)/n!).

%e 1, 2, 10/3, 29/6, 97/15, 739/90, 6331/630, 8617/720, 633127/45360, 1037497/64800, ...

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

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

%p t1/n!;

%p end;

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

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

%Y Cf. A190187.

%K nonn,frac

%O 1,2

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