|
%I M3379 #32 Nov 16 2017 06:19:38
%S 1,4,10,19,31,47,68,92,120,153,190,232,279,332,392,454,521,593,670,
%T 753,841,936,1036,1141,1252,1370,1494,1625,1763,1909,2063,2216,2376,
%U 2542,2713,2890,3074,3264,3460,3663,3872,4088,4310,4540,4776,5021
%N Optimal cost of search tree for searching an ordered array of n elements with cost k of probing element k.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H M. V. Connolly and W. J. Knight, <a href="/A007077/a007077_1.pdf">Search in an array in which probe costs grow exponentially or factorially</a>, Preprint. (Annotated scanned copy)
%H William J. Knight, <a href="https://doi.org/10.1137/0217076">Search in an ordered array having variable probe cost</a>, SIAM J. Comput. 17 (1988), no. 6, 1203-1214.
%H W. J. Knight, <a href="/A007077/a007077.pdf">Letter to N. J. A. Sloane, Jul. 1991</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F 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
%Y Cf. A007078.
%K nonn
%O 1,2
%A _N. J. A. Sloane_, _Mira Bernstein_
%E More terms from _Sean A. Irvine_, Oct 07 2017
|
