|
| |
|
|
A093418
|
|
Numerator of -3n + 2(1+n)*HarmonicNumber[n].
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| 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: A018691 A163943 A174285 * A173733 A033562 A152457
Adjacent sequences: A093415 A093416 A093417 * 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
|
| |
|
|
