How to calculate the number of combinations of n choose k?

AlgorithmsJunior~2 min read

Short answer

The number of combinations of n choose k (denoted C(n, k)) is computed by the formula: C(n, k) = n! / (k! · (n − k)!). Also useful equivalents: C(n, k) = C(n, n−k), C(n, k) = C(n−1, k) + C(n−1, k−1), C(n, k) = ∏_{i=1..k} (n−k+i)/i.

Detailed explanation

Definitions and formulas

Factorial formula: C(n, k) = n! / (k! · (n − k)!), where n and k are nonnegative integers, k ≤ n.
Symmetry: C(n, k) = C(n, n−k). It is always beneficial to take k = min(k, n−k) to reduce the number of operations.
Recurrence formula (Pascal's triangle): C(n, k) = C(n−1, k) + C(n−1, k−1), with base cases C(n, 0) = C(n, n) = 1.
Iterative "multiply-and-divide" formula (resistant to overflow when using large integers): C(n, k) = ∏_{i=1..k} (n−k+i)/i. The division at each step is integer division.

Worked example

Example: C(5, 2). By definition: 5! / (2! · 3!) = 120 / (2 · 6) = 120 / 12 = 10.

Via the product: k = 2, so C(5, 2) = ((5−2+1)/1) · ((5−2+2)/2) = (4/1) · (5/2) = 4 · 2.5 = 10 (the sequential integer division at each step yields an integer value).

Computation algorithms in practice

Directly via factorials. Simple, but quickly overflows standard numbers and requires arbitrary-precision arithmetic. Suitable only for very small n.
Iterative method (preferred): successively multiply by (n−k+i) and divide by i for i = 1..k. Use BigInt (JS) or a bigint type to avoid overflow.
DP over Pascal's triangle: O(n·k) in time. Useful when many values are needed at once and n is not too large; only one row needs to be stored (O(k) memory).
Modulo a prime p. If p > n, you can multiply step by step and divide using modular inverses modulo p (Fermat's theorem). If p ≤ n, special methods are required (for example, Lucas' theorem).

Code: over integers (BigInt, JavaScript)

function comb(n, k) {
  if (!Number.isInteger(n) || !Number.isInteger(k)) {
    throw new TypeError("n and k must be integers");
  }
  if (n < 0 || k < 0 || k > n) return 0n;
  // Symmetry: C(n, k) = C(n, n-k)
  k = Math.min(k, n - k);
  let N = BigInt(n);
  let K = BigInt(k);
  let res = 1n;
  for (let i = 1n; i <= K; i++) {
    res = (res * (N - K + i)) / i; // The division is always exact
  }
  return res; // BigInt
}

// Examples:
console.log(comb(5, 2).toString());    // "10"
console.log(comb(52, 5).toString());   // "2598960"
console.log(comb(100, 50).toString()); // "100891344545564193334812497256"

Code: modulo a prime p (correct when p > n)

// Combinations modulo a prime p, correct when p > n
function modPow(a, e, p) {
  a = BigInt(a) % BigInt(p);
  e = BigInt(e);
  p = BigInt(p);
  let r = 1n;
  while (e > 0n) {
    if (e & 1n) r = (r * a) % p;
    a = (a * a) % p;
    e >>= 1n;
  }
  return r;
}

function modInv(a, p) {
  // p is prime; inverse via Fermat's little theorem
  return modPow(a, BigInt(p) - 2n, p);
}

function combModPrime(n, k, p) {
  if (!Number.isInteger(n) || !Number.isInteger(k)) {
    throw new TypeError("n and k must be integers");
  }
  if (n < 0 || k < 0 || k > n) return 0n;
  if (p <= n) {
    throw new Error("This method is correct only if p > n. For the general case, use, for example, Lucas' theorem.");
  }
  k = Math.min(k, n - k);
  let N = BigInt(n);
  let K = BigInt(k);
  let P = BigInt(p);
  let res = 1n;
  for (let i = 1n; i <= K; i++) {
    res = (res * (N - K + i)) % P;
    res = (res * modInv(i, P)) % P;
  }
  return res;
}

// Example:
console.log(combModPrime(5, 2, 1000000007n).toString()); // "10"

Pitfalls and recommendations

Overflow: almost all C(n, k) quickly exceed 64-bit numbers; in JS use BigInt.
Do not use floating-point arithmetic for division - you will get rounding errors. The division must be integer at every step.
Reduce k to min(k, n−k) - this cuts the number of operations roughly in half.
Boundaries: if k < 0 or k > n, the result is 0; if k = 0 or k = n, the result is 1.

Verification values

C(0, 0) = 1; C(1, 0) = 1; C(1, 1) = 1.
C(5, 2) = 10; C(10, 1) = 10; C(10, 9) = 10.
C(52, 5) = 2,598,960.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.