Monday, October 14, 2013

Calculate Binomial Coefficient

In this post I want to publish code for calculating the binomial coefficient, which is for example used frequently in combinatorics.
The binomial coefficient of two numbers n and k is written as

and is calculated by n!/(k! * (n-k)!), where x! denotes the factorial.
Instead of implementing this form directly in C#, I first calculate the part n!/k! = n * (n - 1) * ... * (k + 1), which dramatically decreased the used numbers, increases the speed and lets overflows occur only later.
The code, I use the function Factorial() from the previous post for calculating factorials:

        public ulong BinC(ulong n, ulong k)
        {
            if (n < k)
                return 0;

            ulong Numerator = 1;
            for (ulong i = n; i > k; i--)
            {
                Numerator *= i;
            }
            ulong Demoninator = Factorial(n - k);
            return (Numerator / Demoninator);
        }

        public ulong Factorial(ulong n)
        {
            ulong Result = 1;
            for (ulong i = 1; i <= n; i++)
            {
                Result *= i;
            }
            return Result;
        }

No comments:

Post a Comment