|
| |
|
|
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
|
|
|
|
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))).
|
|
|
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 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.
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):
|
|
|
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];
|
|
|
PROG
|
(C++)
#include<bits/stdc++.h>
using namespace std;
map<pair<int, int>, 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<int>(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
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
