I had task from school which I do not know how to solve. Can you help me with it? Here is correct task:
Determine the number of different binary search trees with just 6 vertices, which contains these values: 27, 1, 3452, 815, 29 and 100.
Correct result it should be 132. Can you tell ako find out that result in steps? Thanks.
Values themselves are not important, we just use that they are pairwise distinct. Let compute number $f(n)$ of binary search trees (BSTs) on $n$ vertices for some values of $n$.
Obviously $f(1) = 1$ since there is the only BST on $1$ vertex.
For $n > 1$ we can take any vertex as root. If we take vertex with the smallest value as root then all other $n - 1$ vertices go to the right subtree and there are $f(n - 1)$ such BSTs. If we take vertex wtih the second smallest value as root then $1$ certain vertex goes to the left subtree in $f(1)$ possible ways and other $n - 2$ vertices go to the right subtree in $f(n - 2)$ possible ways. And so on. Assuming $f(0) = 1$ we have $$f(n) = f(0) \cdot f(n - 1) + f(1) \cdot f(n - 2) + \cdots + f(n - 1) \cdot f(0) = \sum_{i = 0}^{n - 1}f(i)\cdot f(n - 1 - i).$$ Then $$f(1) = 1,\\ f(2) = 1 + 1 = 2,\\ f(3) = 2 + 1 + 2 = 5,\\ f(4) = 5 + 2 + 2 + 5 = 14,\\ f(5) = 14 + 5 + 4 + 5 + 14 = 42,\\ f(6) = 42 + 14 + 10 + 10 + 14 + 42 = 132. $$ In general $f(n) = C_n = \frac{(2n)!}{(n + 1)!n!}$ where $C_n$ is the Cathalan number.