The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A063090 a(n)/(n*n!) is the average number of comparisons needed to find a node in a binary search tree containing n nodes inserted in a random order. 15
 1, 6, 34, 212, 1488, 11736, 103248, 1004832, 10733760, 124966080, 1575797760, 21403457280, 311623441920, 4842481190400, 80007869491200, 1400671686758400, 25902542427955200, 504597366114508800, 10328835149402112000 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS a(n) is the sum over all permutations, p, of {1, ..., n} of the number of comparisons required to find all the entries in the tree formed when the order of insertion is p(1), p(2), ... p(n). To derive the formula given, first group the trees according to the value of k = p(1). For a given k, p determines a permutation of {1, ..., k-1} that gives the structure of the left subtree. By symmetry, the contribution of the right subtrees will be the same as the left subtrees. Now count and simplify. a(n) mod n is n-2 or 0 depending on whether n is prime or not. - Gary Detlefs, May 28 2012 REFERENCES D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 427, C(n). LINKS T. D. Noe, Table of n, a(n) for n = 1..100 Eric Weisstein's World of Mathematics, Quicksort. FORMULA a(1) = 1, a(n) = n*n! + 2 * Sum_{k=1}^{n-1} (n-1)!/k! * a(k). a(n) = (2*n - 1)*(n - 1)! + (n + 1)*a(n-1). E.g.f.: -(x+2*log(1-x))/(1-x)^2. - Vladeta Jovovic, Sep 15 2003 a(n) = Sum_{k=0..n} |Stirling1(n, k)|*A000337(k). - Vladeta Jovovic, Jul 06 2004 a(n) = 2*(n+1)*abs(Stirling1(n+1, 2))-3*n*n!. - Vladeta Jovovic, Jul 06 2004 a(n) = n!*((2*n+2)*h(n) - 3*n), where h(n) is the n-th harmonic number. - Gary Detlefs, May 28 2012 a(n) = A288964(n) + n!*n (because this sequence and A288964 have the same definition related to quicksort but under slightly different assumptions). - Petros Hadjicostas, May 03 2020 MAPLE A[1]:= 1: for n from 2 to 30 do A[n]:= (2*n-1)*(n-1)!+(n+1)*A[n-1] od: seq(A[n], n=1..30); # Robert Israel, Sep 21 2014 MATHEMATICA a[n_] := n!*((2*n+2)*HarmonicNumber[n] - 3*n); Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Sep 20 2012, after Gary Detlefs *) PROG (PARI) {h(n) = sum(k=1, n, 1/k)}; for(n=1, 30, print1(n!*(2*(n+1)*h(n) - 3*n), ", ")) \\ G. C. Greubel, Sep 01 2018 (Magma) [Factorial(n)*((2*n+2)*HarmonicNumber(n) - 3*n): n in [1..30]]; // G. C. Greubel, Sep 01 2018 CROSSREFS Cf. A000108, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971. Sequence in context: A317178 A218893 A266431 * A184185 A216317 A230331 Adjacent sequences: A063087 A063088 A063089 * A063091 A063092 A063093 KEYWORD nonn,easy,nice AUTHOR Rob Arthan, Aug 06 2001 EXTENSIONS More terms from Vladeta Jovovic, Aug 08 2001 Missing brackets in the formula in the name inserted by Rob Arthan, Sep 21 2014 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 7 08:27 EST 2023. Contains 367645 sequences. (Running on oeis4.)