A related interesting problem is counting binary set hierarchies: the
number of perfect binary trees you can build over the same set of
n=2^k leaves, where there is no distinction between left and right
children.
In other words, starting with n=2^k elements, put them into disjoint
sets of 2
For a binary search tree the solution is called the Catalan Numbers.
The formula is (2n)!/(n!(n+1)!)
The first few terms are:
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,
742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190,
6564120420, 24466267020, 91482563640,
