|
|
A064038
|
|
Numerator of average number of swaps needed to bubble sort a string of n distinct letters.
|
|
27
|
|
|
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
|
|
|
FORMULA
|
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
|
|
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
|
|
|
KEYWORD
|
easy,nonn,frac
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|