The On-Line Encyclopedia of Integer Sequences (OEIS)

Revision History for A335919 (Bold, blue-underlined text is an addition; faded, red-underlined text is a ~~deletion~~.)
Showing entries 1-10 | older changes

A335919

Number T(n,k) of binary search trees of height k having n internal nodes; triangle T(n,k), n>=0, max(0,floor(log_2(n))+1)<=k<=n, read by rows.
(history; published version)

#26 by Susanna Cuyler at Mon Feb 08 17:41:08 EST 2021

STATUS

proposed

approved

#25 by Jean-François Alcover at Mon Feb 08 08:28:43 EST 2021

STATUS

editing

proposed

#24 by Jean-François Alcover at Mon Feb 08 08:28:38 EST 2021

MATHEMATICA

g[n_] := If[n == 0, 0, Floor@Log[2, n]+1];

b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,

Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];

T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];

Table[Table[T[n, k], {k, g[n], n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 08 2021, after Alois P. Heinz *)

STATUS

approved

editing

#23 by Alois P. Heinz at Mon Jun 29 18:03:45 EDT 2020

STATUS

editing

approved

#22 by Alois P. Heinz at Mon Jun 29 18:03:41 EDT 2020

LINKS

Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree</a>

<a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

<a href="/index/Tra#trees">Index entries for sequences related to trees</a>

STATUS

approved

editing

#21 by Alois P. Heinz at Mon Jun 29 17:57:57 EDT 2020

STATUS

editing

approved

#20 by Alois P. Heinz at Mon Jun 29 17:57:54 EDT 2020

COMMENTS

T(n,k) is defined for n,k >= 0. The triangle contains only the positive terms. Terms not shown are zero.

STATUS

approved

editing

#19 by Alois P. Heinz at Mon Jun 29 17:52:45 EDT 2020

STATUS

editing

approved

#18 by Alois P. Heinz at Mon Jun 29 17:41:16 EDT 2020

CROSSREFS

T(n+3,n+2) gives A014480.

#17 by Alois P. Heinz at Mon Jun 29 17:33:01 EDT 2020

FORMULA

Sum_{n=k..2^k-1} n * T(n,k) = A335922(nk).