The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A076615 Number of permutations of {1,2,...,n} that result in a binary search tree with the minimum possible height. 9
 1, 1, 2, 2, 16, 40, 80, 80, 11360, 55040, 253440, 1056000, 3801600, 10982400, 21964800, 21964800, 857213660160, 7907423180800, 72155129446400, 645950912921600, 5622693241651200, 47110389109555200, 375570435981312000, 2811021970538496000, 19445103757787136000 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS Empty external nodes are counted in determining the height of a search tree. LINKS Alois P. Heinz, Table of n, a(n) for n = 0..511 (first 50 terms from Michal Forisek) Wikipedia, Binary search tree Index entries for sequences related to rooted trees Index entries for sequences related to trees FORMULA Let b(n,k) be the number of permutations of {1,2,...,n} that produce a binary search tree of depth at most k. We have: b(0,k) = 1 for k>=0, b(1,0) = 0, b(1,k) = 1 for k>0, b(n,k) = Sum_{r=1..n} C(n-1,r-1) * b(r-1,k-1) * b(n-r,k-1) for n>=2, k>=0. Then a(n) = b(n,floor(log_2(n))+1). EXAMPLE a(3) = 2 because only the permutations (2,1,3) and (2,3,1) result in a binary search tree of minimal height. In both cases you will get the following binary search tree: 2 / \ 1 3 / \ / \ o o o o MAPLE b:= proc(n, k) option remember; if n=0 then 1 elif n=1 then `if`(k>0, 1, 0) else add(binomial(n-1, r-1) *b(r-1, k-1) *b(n-r, k-1), r=1..n) fi end: a:= n-> b(n, ilog2(n)+1): seq(a(n), n=0..30); # Alois P. Heinz, Sep 20 2011 MATHEMATICA b[n_, k_] := b[n, k] = Which[n==0, 1, n==1, If[k>0, 1, 0], True, Sum[ Binomial[n-1, r-1]*b[r-1, k-1]*b[n-r, k-1], {r, 1, n}]]; a[n_] := b[n, Floor @ Log[2, n]+1]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Feb 19 2017, after Alois P. Heinz *) PROG (Python) from math import factorial as f, log, floor B= {} def b(n, x): if (n, x) in B: return B[(n, x)] if n<=1: B[(n, x)] = int(x>=0) else: B[(n, x)]=sum([b(i, x-1)*b(n-1-i, x-1)*f(n-1)//f(i)//f(n-1-i) for i in range(n)]) return B[(n, x)] for n in range(1, 51): print(b(n, floor(log(n, 2)))) # Michal Forisek, Sep 19 2011 CROSSREFS Leftmost nonzero elements in rows of A195581, A244108. Cf. A076616, A328349. Sequence in context: A177832 A230800 A363236 * A098777 A127226 A371548 Adjacent sequences: A076612 A076613 A076614 * A076616 A076617 A076618 KEYWORD nonn AUTHOR Jeffrey Shallit, Oct 22 2002 EXTENSIONS Extended beyond a(8) and efficient formula by Michal Forisek, Sep 19 2011 a(0)=1 prepended by Alois P. Heinz, Jul 18 2018 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 11 07:51 EDT 2024. Contains 375059 sequences. (Running on oeis4.)