A076615 Number of permutations of {1,2,...,n} that result in a binary search tree with the minimum possible height.

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

Offset: 0

Author

Jeffrey Shallit, Oct 22 2002

Keywords

• nonn

Comments

Empty external nodes are counted in determining the height of a search tree.

Examples

			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
		

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

Crossrefs

Leftmost nonzero elements in rows of A195581, A244108.

Cf. A076616, A328349.

Programs

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

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

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

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