CareerCup

C(n)=2n!/n!(n+1)!

C(n) = (2n)!/n!*(n+1)!, Catalan Number

It is catalan number where if n keys are given to us we can generate distinct number of trees from those n keys by the below formula:

No.of.trees= (2n)! / (n!*(n+1)!)
It comes from the fact that if n are the number of keys that for every node we can have 2 children for binary tree then those can be made or mathematically arranged in (2n)!. But for n keys we will have n+1 external nodes. So the internal nodes and external nodes can be arranged seperately in n! and (n+1) !. Note here external nodes cannot be arranged with internal nodes only with external nodes so (n+1)! similarly internal nodes among themselves in n! so for both these arrangements multiply them and divide it by the number of child arrangement to get the required distribution and thus number of different trees that can be generated.

int DistingusishedTree(int n) {
        if(n<1)
           return 1;
         int sum=0;
         for(int i=1;i<=n;i++){
             sum+=DistingusishedTree(i-1)*DistingusishedTree(n-i);             
         }         
     return sum;
            
    }

This is the program to find the different BSTs.
The reason is simple:
suppose n=3;
so we will make each number as root and calculate the different subtrees possible.
for i=1;
left subtree will not contain any node and right subtree will contain 2 nodes i.e 2 & 3
there are two combination possible.
if i=2
left subtree will contain 1 node(1) and right subtree will contain 1 node(3)
if i=3
left subtree will contain 2 nodes(1,2).there are two combinations possible for it.

so required number will be
num(i)= sumation(num(i-1)+num(n-i)) where i=1,2...n
The compact formula for this is num(n)=C(2n,n)-C(2n,2n+1) and known as catalan number
N.B.: This problem can be solved using DP instead of recusion.

Question continued, trying out some formatting as a comment.

For ex: n = 1 => one tree
n = 2 => two trees
   O        O
  /           \
 O            O
n = 3 =>  five trees
    O       O               O               O              O
    /         \               \             /             /  \
  O            O              O           O               O  O
  /             \           /               \
O                 O         O               O

This question is already asked in CareerCup. For more details refer to question with id= 183797

catalan number.. (2n)!/(n!)(n+1)!

Hi D,tox'mi, what 0OZz has said is right, the number trees has to be calculated with Catalan number and also it has to be solved by Dynamic programming so its a combination of Catalan number calculation and dynamic programming, please correct me if i am wrong, Me too also looking for this solution, i think it is not binary tree, rather, from a given set of numbers the BSTs need to be constructed.

n!