A265846 Number of permutations of {1,2,...,2n} that result in a binary search tree of height n.

1, 0, 0, 80, 11360, 1508032, 197163648, 27624399104, 4256968553472, 724948555548672, 136034167652859904, 27976811931437752320, 6269253131872946298880, 1522110257603797873737728, 398311795891656532955725824, 111813044381693547723191418880

Offset

0,4

Links

Alois P. Heinz, Table of n, a(n) for n = 0..250

Wikipedia, Binary search tree

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

Formula

a(n) = A195581(2n,n) = A244108(2n,n).

a(n) ~ c * d^n * (n-1)!, where d = -16*LambertW(-1, -exp(-1/2)/2)^2 / (1 + 2*LambertW(-1, -exp(-1/2)/2)) = 19.643259858273023595006139220961408..., c = 0.0646979349409396546649864277836... . - Vaclav Kotesovec, Jan 02 2016, updated Mar 17 2024

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-> b(2*n, n)-b(2*n, n-1):
seq(a(n), n=0..20);

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_] := b[2*n, n] - b[2*n, n-1]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Feb 25 2017, translated from Maple *)

Crossrefs

Cf. A195581, A244108.

Sequence in context: A159734 A091754 A118493 * A269145 A187052 A159377

Adjacent sequences: A265843 A265844 A265845 * A265847 A265848 A265849

Keyword

nonn

Author

Alois P. Heinz, Dec 21 2015

Status

approved