What is wrong with my Catalan Number logic?

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!    
---------------开发者_Go百科---------------- =  
(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?

---

Even though the original expression for C(n) might be wrong, the actual recurrence

is correct.

You can further simplify that to

But that gives you C(n+1) in terms of C(n). What you want is C(n) in terms of C(n-1). Plug in n-1 to get

Also note that in order to prevent the integer division from truncating your result, you need to multiply first and then divide.

int catalan(int n) {
  if (n == 1)
    return 1; 
  else
    return 2 * (2*n - 1) * catalan(n-1) / (n+1);
}

EDIT: if the values of the

need to be used frequently and not just calculated once, it's probably a good idea to use memoization, to avoid calculating them more than once.

Additionally, notice that due to the large growth rate, the Catalan numbers quickly overflow any of the predefined integer data types C has.

---

According to http://en.wikipedia.org/wiki/Catalan_number the recurrence formula is:

C(n+1)=2(2n+1)/(n+1) * C(n) or C(n)=2(2(n-1)+1)/n * C(n-1)

I think you have forgotten this transformation from C(n+1) to C(n).

---

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)))
}

---

When you go from the mathematical expression to code, you are implicitly replacing n with n-1 in the Catalan() parts, but not in the expression itself. So you are computing the multiplier for value N and multiplying it by C(N-1). Try substituting N-1 for N in your equation, which leads to:

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

---

In your formula, you have

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

when in fact the Catalan Numbers are defined as

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

i.e. you have one factorial on the denominator too much