Calculating Catalan Number

Question

I am using this code to calculate the Catalan Number. It gives me right value until n=6 , then it gives me wrong values. I checked manually using a calculator. For Ex: when n=5 Catalan Number is 42 which is right but when n=7 , it gives me 6 which is completely wrong as the answer should be 429. I just cant figure out whats wrong. Can some one help me please?

static void Main(string[] args)
{
    int i, n, fact, fact1, fact2, CatalanN;
    Console.WriteLine("Enter a Number (n>=0)");

    n = Convert.ToInt32(Console.ReadLine());
    fact = n;

    for (i = n - 1; i > 0; i--)
    {
        fact = fact * i;
    }
    Console.WriteLine("" + fact);
    Console.ReadLine();

    fact1 = 2*n;

    for (i = 2*n - 1; i > 0; i--)
    {
        fact1 = fact1 * i;
    }
    Console.WriteLine("" + fact1);
    Console.ReadLine();

    fact2 = n+1;

    for (i = (n+1)-1; i > 0; i--)
    {
        fact2 = fact2 * i;
    }
    Console.WriteLine("" + fact2);
    Console.ReadLine();

    CatalanN = fact1 / (fact2 * fact);
    Console.WriteLine("Catalan Number of the given number is : " + CatalanN);
    Console.ReadLine();
}

Answer 1

If you change your second loop to:

for (i = 2*n - 1; i > 0; i--)
{
    int old = fact1;
    fact1 = fact1 * i;
    Console.WriteLine("" + old + " " + fact1);
}

then you'll see that you're suffering from overflow (slightly reformatted to line up values):

        14        182
       182       2184
      2184      24024
     24024     240240
    240240    2162160
   2162160   17297280
  17297280  121080960
 121080960  726485760
 726485760 -662538496 <- overflow occurs here.
-662538496 1644813312
1644813312  639472640
 639472640 1278945280
1278945280 1278945280

This is due to the factorial-type terms in the calculations. Changing the type to long will give you some more breathing space (allowing you to do C₁₀). Beyond that, decimal can go a little further but you may have to end up using an arbitrary-precision math library (like System.Numerics.BigInteger) for higher numbers.

You may want to use a slightly less onerous calculation which minimises the interim terms a little:

n = Convert.ToInt32(Console.ReadLine());
CatalanN = 1;
Term = 0;
while (n-- > 1) {
    Term++;
    CatalanN = CatalanN * (4 * Term + 2) / (Term + 2);
}

This will give even more breathing space, regardless of which data type you use. Even our lowly int can get to C₁₆ with that calculation, a long can get at least to C₂₅, which is as far as I could be bothered to check.