A227822 Number of permutations of [n], [n+1], ... that result in a binary search tree of height n.

1, 1, 4, 220, 60092152, 203720181459953921762400, 7088043372247785801830314829178419617696182324188730917543544992

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..9

Wikipedia, Binary search tree

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

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

Adjacent sequences: A227819 A227820 A227821 * A227823 A227824 A227825

Keyword

nonn

Author

Alois P. Heinz, Jul 31 2013

Extensions

Terms corrected by Alois P. Heinz, Dec 08 2015

Status

approved