|
| |
|
|
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.
|
|
2
| |
|
|
1, 6, 34, 212, 1488, 11736, 103248, 1004832, 10733760, 124966080, 1575797760, 21403457280, 311623441920, 4842481190400, 80007869491200, 1400671686758400, 25902542427955200, 504597366114508800, 10328835149402112000
(list; graph; refs; listen; history; 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.
|
|
|
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) = (2n-1)*(n-1)! + (n+1)*a(n-1).
E.g.f.: -(x+2*ln(1-x))/(1-x)^2. - Vladeta Jovovic (vladeta(AT)eunet.rs), Sep 15 2003
a(n) = Sum_{k=0..n} |Stirling1(n, k)|*A000337(k). - Vladeta Jovovic (vladeta(AT)eunet.rs), Jul 06 2004
a(n) = 2*(n+1)*abs(Stirling1(n+1, 2))-3*n*n!. - Vladeta Jovovic (vladeta(AT)eunet.rs), Jul 06 2004
|
|
|
CROSSREFS
| Cf. A000108.
Cf. A093418, A096620.
Sequence in context: A087413 A059228 A079568 * A184185 A197436 A108432
Adjacent sequences: A063087 A063088 A063089 * A063091 A063092 A063093
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| Rob Arthan (rda(AT)lemma-one.com), Aug 06 2001
|
|
|
EXTENSIONS
| More terms from Vladeta Jovovic (vladeta(AT)eunet.rs), Aug 08 2001
|
| |
|
|
