cp's OEIS Frontend

A328349 Number of binary search trees (BST) on n nodes which have the same height as the optimal BST.

%I A328349 #40 Jan 07 2022 19:35:39
%S A328349 1,1,2,1,6,6,4,1,94,114,116,94,60,28,8,1,32398,41658,49700,54746,
%T A328349 55308,50788,41944,30782,19788,10948,5096,1932,568,120,16,1,
%U A328349 5193067630,6939692682,8948546308,11120136162,13299362332,15286065700,16859410792,17813777994,17999433372
%N A328349 Number of binary search trees (BST) on n nodes which have the same height as the optimal BST.
%C A328349 For any BST node p, p.left.value < p.value and p.right.value > p.value provided that the left (right) node exists.
%H A328349 Alois P. Heinz, <a href="/A328349/b328349.txt">Table of n, a(n) for n = 0..1023</a>
%H A328349 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree</a>
%H A328349 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A328349 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A328349 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.
%F A328349 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.
%F A328349 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))).
%F A328349 a(n) = A335919(n,max(0,A000523(n)+1)) = A335920(n,max(0,A000523(n)+1)). - _Alois P. Heinz_, Jun 29 2020
%e A328349 a(1) = 1 - the trivial tree having 1 node.
%e A328349 a(2) = 2 - two trees: one {1,2} rooted at node 1, and {2,1} - at 2.
%e A328349 a(3) = 1 - one BST tree of height 1 with edges {1,2}, {2,3} rooted at the node 2.
%e A328349       2
%e A328349     1   3
%e A328349 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}).
%e A328349 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 the formation of 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.
%e A328349 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.
%p A328349 b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
%p A328349       add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
%p A328349     end:
%p A328349 a:= n-> b(n, ilog2(n)+1):
%p A328349 seq(a(n), n=0..42);  # _Alois P. Heinz_, Jun 28 2020
%t A328349 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 A328349 a[n_] := b[n, Floor@Log[2, n]+1];
%t A328349 a /@ Range[0, 42] (* _Jean-François Alcover_, Nov 15 2020, after _Alois P. Heinz_ *)
%o A328349 (C++)
%o A328349 #include<bits/stdc++.h>
%o A328349 using namespace std;
%o A328349 map<pair<int, int>, int64_t> _cache;
%o A328349 int64_t f(const int k, int level) {
%o A328349     if (k >= 1ll << level) return 0;
%o A328349     level = min(k, level);
%o A328349     const auto p = make_pair(k, level);
%o A328349     const auto d = _cache.find(p);
%o A328349     if (d != _cache.end()) return d->second;
%o A328349     int64_t r = 0;
%o A328349     for (auto root = 1; root <= k; ++root) {
%o A328349         const auto left = root == 1 ? 1 : f(root - 1, level - 1),
%o A328349             right = root == k ? 1 : f(k - root, level - 1);
%o A328349         r += left * right;
%o A328349     }
%o A328349     assert(r);
%o A328349     return _cache[p] = r;
%o A328349 }
%o A328349 int main() {
%o A328349     for (auto n = 1; n <= 70; ++n) {
%o A328349         const auto level = 1 + static_cast<int>(log2(n));
%o A328349         const auto c = f(n, level);
%o A328349         cout << n << '\t' << c << '\n';
%o A328349     }
%o A328349     return 0;
%o A328349 }
%o A328349 (Julia) # after C++ program
%o A328349 const _cache = Dict{Tuple{Int, Int}, Int}()
%o A328349 function f(k::Int, level::Int)
%o A328349     (k >= 1 << level) && return 0
%o A328349     level = min(k, level)
%o A328349     haskey(_cache, (k, level)) && return _cache[(k, level)]
%o A328349     r = 0
%o A328349     for root in 1:k
%o A328349         left  = root == 1 ? 1 : f(root - 1, level - 1)
%o A328349         right = root == k ? 1 : f(k - root, level - 1)
%o A328349         r += left * right
%o A328349     end
%o A328349     return _cache[k, level] = r
%o A328349 end
%o A328349 BinaryIntegerLength(n) = n == 0 ? 1 : floor(Int, log2(n)) + 1
%o A328349 [f(n, BinaryIntegerLength(n)) for n in 1:40] |> println # _Peter Luschny_, Oct 14 2019
%Y A328349 Cf. A000225, A000523, A076615, A195581, A244108, A335919, A335920.
%K A328349 nonn,look
%O A328349 0,3
%A A328349 _Viktar Karatchenia_, Oct 13 2019
%E A328349 a(0)=1 prepended by _Alois P. Heinz_, Jun 28 2020