|
Search: id:A064038
|
|
|
| A064038 |
|
Numerator of average number of swaps needed to bubble sort a string of n distinct letters. |
|
+0
4
|
|
| 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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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
|
Eric Weisstein's World of Mathematics, Simple Graph
|
|
FORMULA
|
Numerator of A001809[n]/(n!).
|
|
MAPLE
|
[seq(numer((n*(n-1))/4), n=1..120)];
|
|
CROSSREFS
|
A064038[4n] = A033991[n], A064038[4n+1] = A007742[n]
Quadrisections are A007742, A014634, A033567, A033991.
Sequence in context: A052898 A095355 A069834 this_sequence A051684 A139431 A128636
Adjacent sequences: A064035 A064036 A064037 this_sequence A064039 A064040 A064041
|
|
KEYWORD
|
nonn,frac
|
|
AUTHOR
|
Antti Karttunen Aug 23 2001
|
|
|
Search completed in 0.002 seconds
|
