The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A328349 Number of binary search trees (BST) on n nodes which have the same height as the optimal BST. 4
 1, 1, 2, 1, 6, 6, 4, 1, 94, 114, 116, 94, 60, 28, 8, 1, 32398, 41658, 49700, 54746, 55308, 50788, 41944, 30782, 19788, 10948, 5096, 1932, 568, 120, 16, 1, 5193067630, 6939692682, 8948546308, 11120136162, 13299362332, 15286065700, 16859410792, 17813777994, 17999433372 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS For any BST node p, p.left.value < p.value and p.right.value > p.value provided that the left (right) node exists. LINKS Alois P. Heinz, Table of n, a(n) for n = 0..1023 Wikipedia, Binary search tree FORMULA a(n) = 1 when n = 2^m - 1, m > 0 because the optimal BST represents a full binary tree thus precisely 1 tree is possible. a(n) = 2^(m-1) when n = 2^m - 2, m > 1. Here the BST is full BST minus 1 node, which must be at the last level. The last level of a full BST has 2^(m-1) nodes. Once the "missing" node is chosen at the last level, there is only 1 BST. a(n) = f(n, 1+floor(log_2(n))) where f(k, level) is 0 when there are too many nodes (k >= 2^ level), otherwise f(k, level) = Sum_{root=1..n}(root=1 ? 1 : f(root-1, level-1)) * (root=k ? 1 : f(k-root, level-1))). a(n) = A335919(n,max(0,A000523(n)+1)) = A335920(n,max(0,A000523(n)+1)). - Alois P. Heinz, Jun 29 2020 EXAMPLE a(1) = 1 - the trivial tree having 1 node. a(2) = 2 - two trees: one {1,2} rooted at node 1, and {2,1} - at 2. a(3) = 1 - one BST tree of height 1 with edges {1,2}, {2,3} rooted at the node 2.       2     1   3 a(4) = 6. Optimal BST height is 2. When the root is 1, the remaining nodes {2,3,4} can form 1 subtree having height 1. Taking 2 as the root, 1 must go to the left, and {3,4} - right; there can be 2 trees on {3,4}. The cases for root 4,3 are symmetric. Thus, a(4) = 2*(1+1*2) = 6. The 6 BSTs of the optimal height 2 are: ({1,3},{3,2},{3,4}), ({2,1},{2,3},{3,4}), ({2,1},{2,4},{4,3}), ({3,4},{3,2},{2,1}), ({3,4},{3,1},{1,2}), ({4,2},{2,1},{2,3}). a(5) = 1+1+2*2 = 6. Height=2. Nodes 1,5 cannot be the root, because the remaining 4 nodes cannot be compressed into a BST of height 1. Node 2 as the root implies {3,4,5} must follow to the right (left) producing 1 tree. Node 4 similarly adds 1 more BST. Finally, 3 as the root allows to form 2 trees consisting of {1,2} to the left of the root, and 2 trees of {4,5} to the right giving 2*2 = 4 trees. a(6) = 4. Here height = 2. The nodes 1,2,5,6 can't be the root. When rooting at the third node, {1,2} will form 2 trees, and {4,5,6} to the right will make 1 possible tree of height 1. The node 4 is similar to 3. In total, a(6) = 2*1*2 = 4. MAPLE b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,       add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))     end: a:= n-> b(n, ilog2(n)+1): seq(a(n), n=0..42);  # Alois P. Heinz, Jun 28 2020 MATHEMATICA 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]]; a[n_] := b[n, Floor@Log[2, n]+1]; a /@ Range[0, 42] (* Jean-François Alcover, Nov 15 2020, after Alois P. Heinz *) PROG (C++) #include using namespace std; map, int64_t> _cache; int64_t f(const int k, int level) {     if (k >= 1ll << level) return 0;     level = min(k, level);     const auto p = make_pair(k, level);     const auto d = _cache.find(p);     if (d != _cache.end()) return d->second;     int64_t r = 0;     for (auto root = 1; root <= k; ++root) {         const auto left = root == 1 ? 1 : f(root - 1, level - 1),             right = root == k ? 1 : f(k - root, level - 1);         r += left * right;     }     assert(r);     return _cache[p] = r; } int main() {     for (auto n = 1; n <= 70; ++n) {         const auto level = 1 + static_cast(log2(n));         const auto c = f(n, level);         cout << n << '\t' << c << '\n';     }     return 0; } (Julia) # after C++ program const _cache = Dict{Tuple{Int, Int}, Int}() function f(k::Int, level::Int)     (k >= 1 << level) && return 0     level = min(k, level)     haskey(_cache, (k, level)) && return _cache[(k, level)]     r = 0     for root in 1:k         left  = root == 1 ? 1 : f(root - 1, level - 1)         right = root == k ? 1 : f(k - root, level - 1)         r += left * right     end     return _cache[k, level] = r end BinaryIntegerLength(n) = n == 0 ? 1 : floor(Int, log2(n)) + 1 [f(n, BinaryIntegerLength(n)) for n in 1:40] |> println # Peter Luschny, Oct 14 2019 CROSSREFS Cf. A000225, A000523, A076615, A195581, A244108, A335919, A335920. Sequence in context: A052121 A193895 A193561 * A117965 A111646 A342965 Adjacent sequences:  A328346 A328347 A328348 * A328350 A328351 A328352 KEYWORD nonn,look AUTHOR Viktar Karatchenia, Oct 13 2019 EXTENSIONS a(0)=1 prepended by Alois P. Heinz, Jun 28 2020 STATUS approved

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

Last modified October 26 05:46 EDT 2021. Contains 348256 sequences. (Running on oeis4.)