How do I compute binomial coefficients efficiently?

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.