Combinatory issue due to Factorial overflow

Question

I need a function which can calculate the mathematical combination of (n, k) for a card game.

My current attempt is to use a function based on usual Factorial method :

    static long Factorial(long n)
    {
        return n < 2 ? 1 : n * Factorial(n - 1); 
    }

    static long Combinatory(long n , long k )
    {
        return Factorial(n) / (Factorial(k) * Factorial(n - k)); 
    }

It's working very well but the matter is when I use some range of number (n value max is 52 and k value max is 4), it keeps me returning a wrong value. E.g :

   long comb = Combinatory(52, 2) ; // return 1 which should be actually 1326

I know that it's because I overflow the long when I make Factorial(52) but the range result I need is not as big as it seems.

Is there any way to get over this issue ?

Answer 1

Instead of using the default combinatory formula n! / (k! x (n - k)!), use the recursive property of the combinatory function.

    (n, k) = (n - 1, k) + (n - 1, k - 1)

Knowing that : (n, 0) = 1 and (n, n) = 1.

-> It will make you avoid using factorial and overflowing your long.

Here is sample of implementation you can do :

 static long Combinatory(long n, long k)
    {
        if (k == 0 || n == k )
            return 1;

        return Combinatory(n - 1, k) + Combinatory(n - 1, k - 1); 
    }

---

EDIT : With a faster iterative algorithm

    static long Combinatory(long n, long k)
    {
        if (n - k < k)
            k = n - k;

        long res = 1;

        for (int i = 1; i <= k; ++i)
        {
            res = (res * (n - i + 1)) / i;
        }

        return res;
    }