What is wrong with my Catalan Number logic?

Question

I wanted to write a code for Catalan Numbers.Catalan Numbers are defined as follows:

C(n) = 2n C n/(n+1). But instead of computing (2n C n) I wanted to calculate the catalan numbers bottom up using the following facts:

Catalan(n) =    
2n! /n! * n! * (n+1)  

Catalan(n+1) =  
2*(n+1)  
--------------------------- =    
(n+1)! * (n+1)! * ((n+1)+1)  

(2n+2) * (2n+1) * 2n!    
------------------------------- =  
(n+1) * n! * (n+1) * n! * (n+2)    

(2n+2) * (2n+1) * 2n!    
----------------------------------- =    
(n+1) * (n+2) * n! * n! * (n+1)    

(2n+2) * (2n+1)    
--------------- * Catalan(n)      
(n+1) * (n+2)

Now utilizing the above fact this is my following code:

int catalan(int n)
{
    if (n == 1)
       return 1 //since c(1)=1 is my base case
    else
       return (((2*n+2) * (2*n+1))/((n+1)*(n+2))) * catalan(n-1)
}

Now,my question is why does the above function return 12 when my input is 4 .It should return 14 because c(4)=14.

Can anyone help me, please?

Answer 1

There is an error in your formula. Your formula is for calculating c(n+1) yet your input is n. This can be fixed by decreasing the value of n by one before using it in the calculation:

int catalan(int n)
{
    if (n == 1)
       return 1 //since c(1)=1 is my base case
    else
       n=n-1
       return (((2*n+2) * (2*n+1))/((n+1)*(n+2))) * catalan(n)
}

Edit: As pointed out by abeln, the code above will fail due to integer division dropping the remainder. Use the code below instead:

int catalan(int n)
{
    if (n == 1)
       return 1 //since c(1)=1 is my base case
    else
       n=n-1
       return ((catalan(n) * (2*n+2) * (2*n+1))/((n+1)*(n+2)))
}