6. Binomial coefficients

The following method simply uses the formula for calculating the binomial coefficient:

// Calculate the binomial coefficient.
private long CalculatedNchooseK(int n, int k)
{
    checked
    {
        return Factorial(n) / Factorial(k) / Factorial(n - k);
    }
}

This is quick and easy, but it only works if the factorials are all small enough to be calculated. For example, it is obvious that  because there's only one way to pick 100 items out of 100 items, namely picking all of them.

Unfortunately, to use the formula, the method must calculate 100!, and we know from the Solution to Problem 4. Factorials, that a program can only calculate factorials up to 20!. Larger values such as 100! cause integer overflow. Even though the final solution may be perfectly reasonable, the formula is impractical if N or K is greater than 20.

The problem statement asked you to verify the following:

Unfortunately, 28! is too big to fit in a long integer, so this method cannot calculate that value. Fortunately, there's another way to calculate binomial coefficients.

Recall that  gives the number of ways that you can pick K items from a set of N items. Now, think about how you might pick K items. The selection could include the first item or not. The total number of ways you could pick K items equals the sum of the numbers of ways the selection could include the first item, plus the number of ways it could not include that item.

Suppose the selection includes the first item. If this is the case, you still need to pick K – 1 items from the remaining N – 1 items to make a full selection. The number of ways to pick K – 1 items from the remaining N – 1 items is the following:

Now, suppose the selection does not include the first item. In that case, you still need to pick K items from the remaining N – 1 items to make a full selection. The number of ways to pick K items out of N – 1 items is as follows:

That means the total number of ways you can pick K items from N items is given by the following formula:

This formula leads to the following recursive method for calculating binomial coefficients:

// Use recursion to find the binomial coefficient.
private long RecursiveNchooseK(int n, int k)
{
    checked
    {
        if (k == 1) return n;
        if (k == n) return 1;
        return
            RecursiveNchooseK(n - 1, k) +
            RecursiveNchooseK(n - 1, k - 1);
    }
}

If k is 1, the method returns n because there are n ways to pick 1 value from a set of n values.

Next, if k equals n, the method returns 1 because there is one way to pick n values from a set of n values, namely, pick every item.

If k is neither 1 nor n, the method calls itself recursively to calculate the following:

The method then returns the result.

This method works and does not have a problem with integer overflow, so it can calculate . Unfortunately, it has a problem similar to the one encountered by the straightforward method to calculate Fibonacci numbers recursively: it calculates too many intermediate values.

To calculate a value, the method calculates two smaller values. Calculating those values requires the method to calculate two other smaller values, and so forth. If you draw a tree showing the calculations similar to the tree shown earlier for Fibonacci numbers, you get a binary tree with height and business depending on N and K. In the worst case scenario, the tree contains a huge number of nodes, so the calculation takes an extremely long time. The problem statement asked you to calculate , and this method is just not up to the challenge.

Solution 5. Fibonacci Numbers, described several methods for avoiding this sort of problem with Fibonacci numbers. Unfortunately, a table or cache won't work in this case because the recursive binomial coefficient method calculates a huge number of values but no duplicates.

The other Fibonacci solution takes a bottom-up approach, using smaller values to calculate larger ones. That approach also works here, although it's a bit hard to understand.

To use this approach, consider the original binomial coefficient formula again and rearrange it as follows:

This lets you write  as the simple fraction N/K times the smaller value . If you repeat this process, you can rewrite the original value as a product of simple fractions:

The last term simplifies to  (N - (K - 1)) / 1, which has the value N - (K - 1).

Now, if you work from right-to-left, you can calculate each value in this sequence in terms of previous values (to the right).

Because each of the intermediate values is also a binomial coefficient, such as , you know that it must be an integer value. (There cannot be 6.3 ways to pick 20 items from a set of 40.) This means that at each stage of calculation, the numbers must cancel out to give an integer result.

All of this gives the following surprisingly simple method for calculating binomial coefficients:

// Use canceling to find the binomial coefficient
private long CancelingNchooseK(int n, int k)
{
    checked
    {
        long result = 1;
        for (int i = 1; i <= k; i++)
        {
            result *= n - (k - i);

            result /= i;
        }
        return result;
    }
}

This method is fast, only requiring K steps. The numbers also cancel as the calculation progresses, so there's no integer overflow unless the final result is too big. For example,  is just plain huge, no matter how you try to calculate it.

This method can verify the following:

Download the BinomialCoefficients example solution to see additional details.