|
|
A227822
|
|
Number of permutations of [n], [n+1], ... that result in a binary search tree of height n.
|
|
4
|
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Empty external nodes are counted in determining the height of a search tree.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=n..2^n-1} A195581(k,n).
|
|
EXAMPLE
|
a(2) = 4, because 4 permutations of {1,2}, {1,2,3}, ... result in a binary search tree of height 2:
(1,2): 1 (2,1): 2 (2,1,3), (2,3,1): 2
/ \ / \ / \
o 2 1 o 1 3
/ \ / \ / \ / \
o o o o o o o o
|
|
MAPLE
|
b:= proc(n, k) option remember; `if`(n<2, `if`(k<n, 0, 1),
add(binomial(n-1, r)*b(r, k-1)*b(n-1-r, k-1), r=0..n-1))
end:
a:= n-> add(b(k, n)-b(k, n-1), k=n..2^n-1):
seq(a(n), n=0..6);
|
|
MATHEMATICA
|
b[n_, k_] := b[n, k] = If[n < 2, If[k < n, 0, 1],
Sum[Binomial[n - 1, r]*b[r, k - 1]*b[n - 1 - r, k - 1], {r, 0, n - 1}]];
a[n_] := Sum[b[k, n] - b[k, n - 1], {k, n, 2^n - 1}];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|