|
| |
|
|
A064038
|
|
Numerator of average number of swaps needed to bubble sort a string of n distinct letters.
|
|
16
| |
|
|
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; 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
| Index to sequences with 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 4 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 4 2011].
a(n+1) = A026741(A000217(n)). - Paul Curtz, Apr 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]
|
|
|
CROSSREFS
| Sequence in context: A183483 A095355 A069834 * A051684 A195583 A139431
Adjacent sequences: A064035 A064036 A064037 * A064039 A064040 A064041
|
|
|
KEYWORD
| nonn,frac
|
|
|
AUTHOR
| Antti Karttunen Aug 23 2001
|
| |
|
|
