The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 (list; graph; refs; listen; history; text; internal format)
 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 24 10:07 EDT 2024. Contains 373674 sequences. (Running on oeis4.)