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.

1, 6, 34, 212, 1488, 11736, 103248, 1004832, 10733760, 124966080, 1575797760, 21403457280, 311623441920, 4842481190400, 80007869491200, 1400671686758400, 25902542427955200, 504597366114508800, 10328835149402112000

Offset: 1

Author

Rob Arthan, Aug 06 2001

Keywords

• nonn
• easy
• nice

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.

Crossrefs

Cf. A000108, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971.

Programs

Magma

[Factorial(n)*((2*n+2)*HarmonicNumber(n) - 3*n): n in [1..30]]; // G. C. Greubel, Sep 01 2018

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 *)

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

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

Extensions

More terms from Vladeta Jovovic, Aug 08 2001

Missing brackets in the formula in the name inserted by Rob Arthan, Sep 21 2014