Title: Calculate the binomial coefficient "N choose K" efficiently in C#
The binomial coefficient, written and pronounced "n choose k," is the number of ways you can pick k items from a set of n items. For example, suppose you have a deck of 5 cards (n = 5) and you want to know how many different hands of 3 cards you can make (k = 3). If you number the cards 1 through 5, then the possible combinations are:
 1,2,3
 1,2,4
 1,2,5
 1,3,4
 1,3,5
 1,4,5
 2,3,4
 2,3,5
 2,4,5
 3,4,5
That means .
Notice that the selections are unordered so, for example, 1,2,3 is the same as 3,2,1.
In addition to its combinatorial meaning, the binomial coefficient also gives the coefficient of the x^{k} term in (1 + x)^{n}.
The value of the binomial coefficient is easy to calculate using the formula:
For example:
Unfortunately the factorial function grows very quickly, this formula only lets you calculate values for relatively small values of n and k. For example, 28! is too big to fit in .NET's decimal data type, so you cannot calculate the binomial coefficient when n > 27.
However, the values on the bottom of the equation are big, too. The two values largely cancel out, leaving a result that is much more manageable. The trick is in calculating the binomial coefficient in a way so the intermediate values don't get too big.
To see how to do this, consider the formula and rearrange it a bit like this:
This lets you write "n choose k" in terms of a simple fraction times "n  1 choose k  1." If you repeat this process, you can represent the original value as a product of simple fractions like this:
If you group the terms from the right and work backwards, you can successively calculate:
Note that the top value is simply n  (k  1). Using that value, you can build the others.
Because each of those values represents a binomial coefficient, it must have an integer value. (There can't be 9.7 ways to pick 3 cards from a deck of 5 cards.) That means you can start with the rightmost term and multiply it by each of the terms to the left, getting an integer result at each step.
Here's the C# code to perform this calculation.
decimal result = 1;
for (int i = 1; i <= K; i++)
{
result *= N  (K  i);
result /= i;
}
return result;
Remarkably simple, isn't it?
For example, . This value isn't very large, but to calculate it using factorials you would need to evaluate 28!, which is too big to fit in a decimal variable.
Download the example to experiment with it and to see additional details.
