4
$\begingroup$

How many different binary search trees are possible that store the values 1,2,...,n ?

So far I found a recursive formula for the number (by case distinction what's at the root):

$ T(n) = 2T(n-1) + \sum_{i=2}^{n-1}T(i-1)T(n-i), n > 1 $ and $ T(1) = 1 $

But I have no idea how to solve this recursion. Our task was only to find the recursion and I believe this to be a correct solution. But I am very interested in a closed formula of it. Can anyone link me to some resources/books or give a general hint on how it can be solved?

$\endgroup$
4
$\begingroup$

The solution to your recurrence is $$ T(n) = \frac{(2n)!}{n!(n+1)!}, $$ also known as the Catalan numbers. The quickest way to find this is by computing a few elements of the sequence and using the OEIS to identify the sequence.

$\endgroup$
3
$\begingroup$

Any time you see something resembling a convolution, that suggests generating functions as a method. Convolutions are things that look like $\sum_x f(x)f(\overline{x})$, where $\overline{x}$ denotes some kind of "complement" or "opposite" of $x$. Generating functions often turn convolutions into products.

Possible references are:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.