Logo

Programming-Idioms

  • Ada
  • Js

Idiom #67 Binomial coefficient "n choose k"

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

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)

JavaScript is concise even when it has no builtins. The integer type (BigInt) is only supported by Firefox, NodeJS, and Chrome at the moment.
long long binom(long long n, long long k){
  long long outp = 1;
  for(long long i = n - k + 1; i <= n; ++i) outp *= i;
  for(long long i = 2; i <= k; ++i) outp /= i;
  return outp;
}

c does not have a BigInt type, as a substitute long long is used.
To increase the range as much as possible, the formula is slightly different than the one presented in the idiom, but it gives the same results.

New implementation...
< >
programming-idioms.org