login
This site is supported by donations to The OEIS Foundation.

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy. .

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