The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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. 8
 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 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. Cf. A076616, A328349. Sequence in context: A303567 A177832 A230800 * A098777 A127226 A001119 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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 12 17:48 EDT 2021. Contains 342929 sequences. (Running on oeis4.)