|
| |
|
|
A076615
|
|
Number of permutations of {1,2,...,n} that result in a binary search tree with the minimum possible height.
|
|
2
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| Empty external nodes are counted in determining the height of a search tree.
|
|
|
LINKS
| Alois P. Heinz and Michal Forisek, Table of n, a(n) for n = 1..185 (first 50 terms by Michal Forisek)
|
|
|
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=1..30); # Alois P. Heinz, Sep 20 2011
|
|
|
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. - Alois P. Heinz, Sep 21 2011
Sequence in context: A152556 A113123 A177832 * A098777 A127226 A001119
Adjacent sequences: A076612 A076613 A076614 * A076616 A076617 A076618
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Jeffrey Shallit (shallit(AT)graceland.uwaterloo.ca), Oct 22 2002
|
|
|
EXTENSIONS
| Extended beyond a(8) and efficient formula by Michal Forisek (misof(AT)oeis.ksp.sk), Sep 19 2011
|
| |
|
|
