|
| |
|
|
A007077
|
|
Optimal cost of search tree for searching an ordered array of n elements with cost k of probing element k.
(Formerly M3379)
|
|
2
|
|
|
|
1, 4, 10, 19, 31, 47, 68, 92, 120, 153, 190, 232, 279, 332, 392, 454, 521, 593, 670, 753, 841, 936, 1036, 1141, 1252, 1370, 1494, 1625, 1763, 1909, 2063, 2216, 2376, 2542, 2713, 2890, 3074, 3264, 3460, 3663, 3872, 4088, 4310, 4540, 4776, 5021
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
Table of n, a(n) for n=1..46.
M. V. Connolly and W. J. Knight, Search in an array in which probe costs grow exponentially or factorially, Preprint. (Annotated scanned copy)
William J. Knight, Search in an ordered array having variable probe cost, SIAM J. Comput. 17 (1988), no. 6, 1203-1214.
W. J. Knight, Letter to N. J. A. Sloane, Jul. 1991
Index entries for sequences related to rooted trees
Index entries for sequences related to trees
|
|
|
FORMULA
|
a(n) = m(n, 0) where m(0, d) = 0 and for n > 0, m(n, d) = min_{1 <= r <= n} {(r+d) * n + m(r-1, d) + m(n-r, r+d)} [from Knight]. - Sean A. Irvine, Oct 07 2017
|
|
|
CROSSREFS
|
Cf. A007078.
Sequence in context: A005448 A301247 A037040 * A301202 A301021 A009895
Adjacent sequences: A007074 A007075 A007076 * A007078 A007079 A007080
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
N. J. A. Sloane, Mira Bernstein
|
|
|
EXTENSIONS
|
More terms from Sean A. Irvine, Oct 07 2017
|
|
|
STATUS
|
approved
|
| |
|
|
