|
Search: id:A093418
|
|
|
| A093418 |
|
Numerator of -3n + 2(1+n)*HarmonicNumber[n]. |
|
+0
9
|
|
| 0, 1, 3, 17, 53, 62, 163, 717, 3489, 3727, 43391, 45596, 619313, 644063, 667229, 2756003, 24124223, 24784883, 160941559, 164719333, 33664415, 11451017, 268428987, 819836496, 20845424563, 21181779967, 193553388003
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
Average time to quicksort n items in random order.
|
|
REFERENCES
|
Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 143 and 258-259, 1996.
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Quicksort
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
|
|
FORMULA
|
G.f.: -(x+2*ln(1-x))/(1-x)^2. - Vladeta Jovovic (vladeta(AT)eunet.rs), Jul 05 2004
1+(1/n!)*Sum_{k=0..n} (-1)^(n-k)*Stirling1(n, k)*(k-1)*2^k. - Vladeta Jovovic (vladeta(AT)eunet.rs), Jul 05 2004
a(n) = Numerator[ - n + 2 * H(n, (2)) ], where H(n, (2)) = Sum[HarmonicNumber[k], {k, 1, n}] is second-order harmonic number. - Alexander Adamchuk (alex(AT)kolmogorov.com), Nov 01 2004
|
|
EXAMPLE
|
0, 1, 3, 17/3, 53/6, 62/5, 163/10, 717/35, 3489/140, ... = A093418/A096620
|
|
MATHEMATICA
|
Numerator[Table[2*Sum[Sum[1/i, {i, 1, k}], {k, 1, n}]-n, {n, 0, 20}]] or Numerator[Table[2*Sum[HarmonicNumber[k], {k, 1, n}]-n, {n, 0, 20}]]
|
|
CROSSREFS
|
Cf. A093412, A093413, A093414, A093415, A093417, A093419, A096620.
Cf. A063090.
Cf. A001008, A002805.
Sequence in context: A011917 A018691 A163943 this_sequence A033562 A152457 A130857
Adjacent sequences: A093415 A093416 A093417 this_sequence A093419 A093420 A093421
|
|
KEYWORD
|
nonn,frac
|
|
AUTHOR
|
Amarnath Murthy (amarnath_murthy(AT)yahoo.com), Mar 30 2004
|
|
EXTENSIONS
|
Edited by Eric Weisstein (eric(AT)weisstein.com), Jul 01, 2004
|
|
|
Search completed in 0.002 seconds
|
