|
Search: id:A063090
|
|
|
| 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. |
|
+0
2
|
|
| 1, 6, 34, 212, 1488, 11736, 103248, 1004832, 10733760, 124966080, 1575797760, 21403457280, 311623441920, 4842481190400, 80007869491200, 1400671686758400, 25902542427955200, 504597366114508800, 10328835149402112000
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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 this_sequence A108432 A125759 A062819
Adjacent sequences: A063087 A063088 A063089 this_sequence 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
|
|
|
Search completed in 0.002 seconds
|
