|
%I #60 May 22 2023 20:38:11
%S 1,1,2,2,16,40,80,80,11360,55040,253440,1056000,3801600,10982400,
%T 21964800,21964800,857213660160,7907423180800,72155129446400,
%U 645950912921600,5622693241651200,47110389109555200,375570435981312000,2811021970538496000,19445103757787136000
%N Number of permutations of {1,2,...,n} that result in a binary search tree with the minimum possible height.
%C Empty external nodes are counted in determining the height of a search tree.
%H Alois P. Heinz, <a href="/A076615/b076615.txt">Table of n, a(n) for n = 0..511</a> (first 50 terms from Michal Forisek)
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree</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 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:
%F b(0,k) = 1 for k>=0,
%F b(1,0) = 0,
%F b(1,k) = 1 for k>0,
%F 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.
%F Then a(n) = b(n,floor(log_2(n))+1).
%e 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:
%e 2
%e / \
%e 1 3
%e / \ / \
%e o o o o
%p b:= proc(n,k) option remember;
%p if n=0 then 1
%p elif n=1 then `if`(k>0, 1, 0)
%p else add(binomial(n-1, r-1) *b(r-1, k-1) *b(n-r, k-1), r=1..n)
%p fi
%p end:
%p a:= n-> b(n, ilog2(n)+1):
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Sep 20 2011
%t 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_ *)
%o (Python)
%o from math import factorial as f, log, floor
%o B= {}
%o def b(n,x):
%o if (n,x) in B: return B[(n,x)]
%o if n<=1: B[(n,x)] = int(x>=0)
%o 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)])
%o return B[(n,x)]
%o for n in range(1,51): print(b(n,floor(log(n,2))))
%o # _Michal Forisek_, Sep 19 2011
%Y Leftmost nonzero elements in rows of A195581, A244108.
%Y Cf. A076616, A328349.
%K nonn
%O 0,3
%A _Jeffrey Shallit_, Oct 22 2002
%E Extended beyond a(8) and efficient formula by _Michal Forisek_, Sep 19 2011
%E a(0)=1 prepended by _Alois P. Heinz_, Jul 18 2018
|
