This language bar is your friend. Select your favorite languages!

Idiom #67 Binomial coefficient "n choose k"

Calculate binom(n, k) = n! / (k! * (n-k)!). Use an integer type able to handle huge numbers.

Illustration
import math
def binom(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)
import std.bigint;
BigInt binom(uint n, uint k)
{
   assert(n >= k);
   BigInt r = 1;
   for(uint i = 0; i <= k; ++i)
   {
      r *= n-i;
      r /= i+1;
   }
   return r;
}
int binom(int n, int k) {
  int result = 1;
  for (int i = 0; i < k; i++) {
    result = result * (n - i) ~/ (i + 1);
  }
  return r;
}
import "math/big"
z := new(big.Int)
z.Binomial(n, k)
binom n k = product [1+n-k..n] `div` product [1..k]
const fac = x => x ? x * fac (x - 1) : x + 1
const binom = (n, k) => fac (n) / fac (k) / fac (n - k >= 0 ? n - k : NaN)
import java.math.BigInteger;
static BigInteger binom(int N, int K) {
    BigInteger ret = BigInteger.ONE;
    for (int k = 0; k < K; k++) {
        ret = ret.multiply(BigInteger.valueOf(N-k))
                 .divide(BigInteger.valueOf(k+1));
    }
    return ret;
}
uses ncalc;
var
  N, K, Res: TValue;
begin
  Res := BinomN(N, K);
end.
use bigint;
sub binom {
   my ($n, $k) = @_;
   my $fact = sub {
      my $n = shift;
      return $n<2 ? 1 : $n * $fact->($n-1);
   };
   return $fact->($n) / ($fact->($k) * ($fact->($n-$k)));
}
def binom(n,k)
  (1+n-k..n).inject(:*)/(1..k).inject(:*)
end
extern crate num;

use num::bigint::BigInt;
use num::bigint::ToBigInt;
use num::traits::One;
fn binom(n: u64, k: u64) -> BigInt {
    let mut res = BigInt::one();
    for i in 0..k {
        res = (res * (n - i).to_bigint().unwrap()) /
              (i + 1).to_bigint().unwrap();
    }
    res
}

Do you know the best way to do this in your language ?
New implementation...

Idiom created by

programming-idioms.org