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