This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A064038 Numerator of average number of swaps needed to bubble sort a string of n distinct letters. 25
 0, 1, 3, 3, 5, 15, 21, 14, 18, 45, 55, 33, 39, 91, 105, 60, 68, 153, 171, 95, 105, 231, 253, 138, 150, 325, 351, 189, 203, 435, 465, 248, 264, 561, 595, 315, 333, 703, 741, 390, 410, 861, 903, 473, 495, 1035, 1081, 564, 588, 1225, 1275, 663, 689, 1431, 1485, 770 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS Denominators are given by the simple periodic sequence [1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, ...] (= A014695) thus we get an average of 1/2, 3/2, 3, 5, 15/2, 21/2, 14, 18, etc. swappings required to bubble sort a string of 2, 3, 4, 5, 6, ... letters. REFERENCES E. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.1, p. 287. LINKS G. C. Greubel, Table of n, a(n) for n = 1..5000 Index entries for linear recurrences with constant coefficients, signature (3,-6,10,-12,12,-10,6,-3,1). Eric Weisstein's World of Mathematics, Simple Graph FORMULA Numerator of A001809[n]/(n!). a(4n) = A033991(n). a(4n+1) = A007742(n). a(4n+2) = A014634(n). a(4n+3) = A033567(n+1). a(n+1) = A061041(8*n-4). - Paul Curtz, Jan 03 2011 G.f.: -x^2*(1+4*x^3+x^6) / ( (x-1)^3*(1+x^2)^3 ). - R. J. Mathar, Jan 03 2011 a(n+1) = A060819(n)*A060819(n+1). a(n+1) = A000217(n)/(period 4:repeat 2,1,1,2=A014695(n+2)=A130658(n+3)). a(n) = 3*a(n-4) -3*a(n-8) +a(n-12). - Paul Curtz, Mar 04 2011 a(n) = +3*a(n-1) -6*a(n-2) +10*a(n-3) -12*a(n-4) +12*a(n-5) -10*a(n-6) +6*a(n-7) -3*a(n-8) +1*a(n-9). - Joerg Arndt, Mar 04 2011 a(n+1) = A026741(A000217(n)). - Paul Curtz, Apr 04 2011 a(n) = numerator of sum(k=0..n-1, k/2). - Arkadiusz Wesolowski, Aug 09 2012 a(n) = n*(n+1)*(3-i^(n*(n+1)))/8, where i=sqrt(-1). - Bruno Berselli, Oct 01 2012 MAPLE [seq(numer((n*(n-1))/4), n=1..120)]; MATHEMATICA f[n_] := Numerator[n (n - 1)/4]; Array[f, 56] f[n_] := n/GCD[n, 4]; Array[f[#] f[# - 1] &, 56] PROG (PARI) vector(100, n, numerator(n*(n-1)/4)) \\ G. C. Greubel, Sep 21 2018 (MAGMA) [Numerator(n*(n-1)/4): n in [1..100]]; // G. C. Greubel, Sep 21 2018 CROSSREFS Sequence in context: A218663 A095355 A069834 * A051684 A209388 A195583 Adjacent sequences:  A064035 A064036 A064037 * A064039 A064040 A064041 KEYWORD easy,nonn,frac AUTHOR Antti Karttunen, Aug 23 2001 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 23 05:56 EDT 2019. Contains 328335 sequences. (Running on oeis4.)