How do I compute binomial coefficients efficiently?

I'm trying to reproduce Excel's COMBIN function in C#. The number of combinations is as follows, where number = n and number_chosen = k:

$${n \choose k} = \frac{n!}{k! (n-k)!}.$$

I can't use this formula because the factorial overflows the computer's capacity really quick. Int32 can only do up to 12!, Int64 up to 20!, and double up to a whopping 170! after that I'm on my own.

How can I get the same results with a formula more gentle to the computer?

André Nicolas correctly identifies that we should maybe use: $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$$

But we should also use:

$$\binom{n}{k}=\binom{n}{n-k}$$

And this also seems important:

$$\binom{n}{0} = \frac{n!}{(n-0)!} = \frac{n!}{n!} = 1$$

Great, we have everything we need to implement the function recursively!

I like to implement n choose k in a functional language like so:

n `choose` k
  | k > n           = undefined
  | k == 0          = 1
  | k > (n `div` 2) = n `choose` (n-k)
  | otherwise       = n * ((n-1) `choose` (k-1)) `div` k

Or in an imperative language like so:

f(n, k) {
  if(k >  n)
    throw some_exception;
  if(k == 0)
    return 1;
  if(k > n/2)
    return f(n,n-k);
  return n * f(n-1,k-1) / k;
}

It is pretty easy to see that both implementations run in $O(k)$ time and avoids overflow errors of fixed precision numbers much better then calculating n!/(n-k)!.

Maybe use $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}.$$

I presume you are looking for a floating point answer here.

$\prod_{i=0}^{k-1} \frac{n-i}{k-i} $. Compute each term $\frac{n-i}{k-i}$ and multiply.

Note that $$ \frac{n!}{k!(n-k)!} = \frac{n(n-1)(n-2)\cdots (n-k+1)}{k!} $$ When doing this by hand, there is much cancellation that can be done. In fact, since $\binom{n}{k}$ is an integer, we are guaranteed to be able to cancel all of $k!$.

By they way, since $\binom{n}{k} = \binom{n}{n-k}$, we can always set up the fraction so that there are no more than $n/2$ factors on top and bottom.

Hope this helps!

You can use Stirling's approximation to calculate the logarithm. $\ln n!\approx n \ln n - n + \frac 12 \ln (2 \pi n)$. It is quite accurate as $n$ gets large (even $10$)