login
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

%I #51 Feb 17 2022 00:02:47

%S 1,6,34,212,1488,11736,103248,1004832,10733760,124966080,1575797760,

%T 21403457280,311623441920,4842481190400,80007869491200,

%U 1400671686758400,25902542427955200,504597366114508800,10328835149402112000

%N 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.

%C 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.

%C a(n) mod n is n-2 or 0 depending on whether n is prime or not. - _Gary Detlefs_, May 28 2012

%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 427, C(n).

%H T. D. Noe, <a href="/A063090/b063090.txt">Table of n, a(n) for n = 1..100</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Quicksort.html">Quicksort</a>.

%F a(1) = 1, a(n) = n*n! + 2 * Sum_{k=1}^{n-1} (n-1)!/k! * a(k).

%F a(n) = (2*n - 1)*(n - 1)! + (n + 1)*a(n-1).

%F E.g.f.: -(x+2*log(1-x))/(1-x)^2. - _Vladeta Jovovic_, Sep 15 2003

%F a(n) = Sum_{k=0..n} |Stirling1(n, k)|*A000337(k). - _Vladeta Jovovic_, Jul 06 2004

%F a(n) = 2*(n+1)*abs(Stirling1(n+1, 2))-3*n*n!. - _Vladeta Jovovic_, Jul 06 2004

%F a(n) = n!*((2*n+2)*h(n) - 3*n), where h(n) is the n-th harmonic number. - _Gary Detlefs_, May 28 2012

%F 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

%p A[1]:= 1:

%p for n from 2 to 30 do A[n]:= (2*n-1)*(n-1)!+(n+1)*A[n-1] od:

%p seq(A[n],n=1..30); # _Robert Israel_, Sep 21 2014

%t 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_ *)

%o (PARI) {h(n) = sum(k=1,n, 1/k)};

%o for(n=1,30, print1(n!*(2*(n+1)*h(n) - 3*n), ", ")) \\ _G. C. Greubel_, Sep 01 2018

%o (Magma) [Factorial(n)*((2*n+2)*HarmonicNumber(n) - 3*n): n in [1..30]]; // _G. C. Greubel_, Sep 01 2018

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

%K nonn,easy,nice

%O 1,2

%A _Rob Arthan_, Aug 06 2001

%E More terms from _Vladeta Jovovic_, Aug 08 2001

%E Missing brackets in the formula in the name inserted by _Rob Arthan_, Sep 21 2014