Combinations and Modular Inverse

1. Combinations

• Purpose: Calculates the number of ways to choose r items from n items, where order doesn't matter
• Example: If you have 5 colors and want to pick 2, nCr(5,2) tells you how many different color pairs are possible
• Formula: C(n,r) = n!/(r! * (n-r)!)

2. Modular Inverse:

• Purpose: Used when we need to perform division in modular arithmetic
• When we calculate large combinations, we often need to take modulo to prevent overflow
• Division in modular arithmetic isn't straightforward, so we use modular multiplicative inverse
• For (a/b) % m, we calculate (a * modInverse(b,m)) % m

// Calculate combinations C(n,r) using modular arithmetic
function modInverse(a, m) {
  // Extended Euclidean Algorithm to find modular multiplicative inverse
  let m0 = m;
  let x0 = 0;
  let x1 = 1;

  if (m === 1) return 0;

  while (a > 1) {
    const q = Math.floor(a / m);
    let t = m;

    m = a % m;
    a = t;
    t = x0;

    x0 = x1 - q * x0;
    x1 = t;
  }

  return x1 < 0 ? x1 + m0 : x1;
}

function nCr(n, r, mod = 1e9 + 7) {
  if (r > n) return 0;
  if (r === 0 || r === n) return 1;

  // Calculate using formula: C(n,r) = n!/(r! * (n-r)!)
  let numerator = 1;
  let denominator = 1;

  for (let i = 0; i < r; i++) {
    numerator = (numerator * (n - i)) % mod;
    denominator = (denominator * (i + 1)) % mod;
  }

  // Use modular inverse for division
  return (numerator * modInverse(denominator, mod)) % mod;
}

// Example usage
console.log(nCr(5, 2));  // Calculates 5C2 = 10
console.log(nCr(10, 3)); // Calculates 10C3 = 120

For Big Numbers

const kMod = BigInt(1e9 + 7); // Modulo 10^9+7

// Modular exponentiation
const modPow = (base, exp, mod) => {
  let result = BigInt(1);
  while (exp > 0) {
    if (exp % BigInt(2) === BigInt(1)) result = (result * base) % mod;
    base = (base * base) % mod;
    exp >>= BigInt(1); // Bitwise shift for efficiency
  }
  return result;
};

// Compute (nCr) % mod using modular inverse
const comb = (n, r, mod = kMod) => {
  if (r > n) return BigInt(0);

  let numerator = BigInt(1), denominator = BigInt(1);
  for (let i = BigInt(0); i < r; i++) {
    numerator = (numerator * (n - i)) % mod;
    denominator = (denominator * (i + BigInt(1))) % mod;
  }

  // Compute modular inverse of denominator using Fermat’s theorem
  return (numerator * modPow(denominator, mod - BigInt(2), mod)) % mod;
};

// Example usage
console.log(comb(BigInt(5), BigInt(2)));  // 10
console.log(comb(BigInt(10), BigInt(3))); // 120
console.log(comb(BigInt(1000), BigInt(500))); // Large nCr % 10^9+7
/* 
10n
120n
159835829n
*/