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,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

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).

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+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(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

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 *)

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

Cf. A014695 (denominators), A190186, A190187, A350660.

Cf. A000217, A001809, A007742, A014634, A026741, A033567, A033991, A060819, A061041.

Sequence in context: A095355 A336130 A069834 * A051684 A209388 A195583

Adjacent sequences: A064035 A064036 A064037 * A064039 A064040 A064041

Keyword

easy,nonn,frac,changed

Author

Antti Karttunen, Aug 23 2001

Status

approved