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