login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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

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.

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.

License Agreements, Terms of Use, Privacy Policy. .

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