login
A227822
Number of permutations of [n], [n+1], ... that result in a binary search tree of height n.
4
1, 1, 4, 220, 60092152, 203720181459953921762400, 7088043372247785801830314829178419617696182324188730917543544992
OFFSET
0,3
COMMENTS
Empty external nodes are counted in determining the height of a search tree.
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}];
a /@ Range[0, 6] (* Jean-François Alcover, Apr 02 2021, after Alois P. Heinz *)
CROSSREFS
Column sums of A195581 and of A244108.
Cf. A317012.
Sequence in context: A222421 A025420 A259460 * A052209 A211610 A364481
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 31 2013
EXTENSIONS
Terms corrected by Alois P. Heinz, Dec 08 2015
STATUS
approved