Calculate the binomial coefficient “N choose K” efficiently in C#

binomial coefficient

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. 1,2,3
  2. 1,2,4
  3. 1,2,5
  4. 1,3,4
  5. 1,3,5
  6. 1,4,5
  7. 2,3,4
  8. 2,3,5
  9. 2,4,5
  10. 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 xk 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 Example   Follow me on Twitter   RSS feed

This entry was posted in algorithms, mathematics and tagged , , , , , , , , , , , , , . Bookmark the permalink.

9 Responses to Calculate the binomial coefficient “N choose K” efficiently in C#

  1. Henrique says:

    Wow… now this is really simple! And it works like a charm. 🙂

    Thanks for both the explanation and the code, i’ve been struggling on a way to calculate it for a while now. Every other solution I found made use of external libraries to handle the fatorials.

  2. Pingback: Generate all selections of K items from a set of N items in C#

  3. Khan N S says:

    Nice but already known issue. I was searching calculate between elements of a cluster.

  4. KM says:

    Very clever and clean solution. Just another example of how first thinking about refactoring a problem into a reduced form (if possible of course) wins over brute force computation. Cheers!

  5. Sonson says:

    What would be the code if the k is not user-input?

    For example, you have n = 3 (user-input). So there would be k =0, k = 1, k = 2, and k = 3. How do I get the value of C(n,k) for each k?

    • RodStephens says:

      This example calculates C(n-(k-1), 1), C(n-(k-2), 2), …, C(n-2, k-2), C(n-1, k-1), C(n, k) so it doesn’t naturally calculate the values of C(n, k) for different k.

      One approach would be to put the code in a method that calculates C(n, k) and then simply call the method for each of the k values.

      This would be easy and fairly quick, but there’s an even better approach. See this post:

  6. Pingback: Calculate a row of Pascal's triangle in C# - C# HelperC# Helper

  7. Bradley says:

    Thank You for this wonderful explanation. There were some other solutions for this issue on other websites that I just didn’t really understand. The code is stupidly simple. And I mean that in the best possible way. 🙂 Your solution was the one for me.

    Thank You. Long live the Internet!

    • RodStephens says:

      Thanks for the kind words. It actually kind of blew my mind when I discovered this approach. One of those, “How can code this simple do something so complicated?” moments. 😉

Comments are closed.