A064038 Numerator of average number of swaps needed to bubble sort a string of n distinct letters.
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
Offset: 1
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
- Eric Weisstein's World of Mathematics, Simple Graph.
- Index entries for linear recurrences with constant coefficients, signature (3,-6,10,-12,12,-10,6,-3,1).
Crossrefs
Programs
-
Magma
[Numerator(n*(n-1)/4): n in [1..100]]; // G. C. Greubel, Sep 21 2018
-
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] LinearRecurrence[{3,-6,10,-12,12,-10,6,-3,1},{0,1,3,3,5,15,21,14,18},80] (* Harvey P. Dale, Jan 23 2023 *) -
PARI
vector(100, n, numerator(n*(n-1)/4)) \\ G. C. Greubel, Sep 21 2018
Formula
a(n) = numerator(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) = 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) = numerator(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, corrected by Vaclav Kotesovec, Aug 09 2022
Sum_{n>=2} 1/a(n) = 4 - Pi/2. - Amiram Eldar, Aug 09 2022
E.g.f.: x^2*(3*exp(x) + cos(x) + sin(x))/8. - Stefano Spezia, Aug 23 2025
Comments