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
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