In mathematics, There are a few known identities to find combinations.

1. Pascal Formula

   $C(n,r)=C(n-1,r) + C(n-1,r-1)$

   

2. General Formula

   $C(n, r) = \frac{n!}{r!(n-r)!}$

   // Factorial function
   function factorial(n) {
     if (n === 0 || n === 1) {
       return 1;
     } else {
       return n * factorial(n - 1);
     }
   }
   
   // Example usage
   console.log(factorial(5)); 
   // Output: 120
   

   // Combination function
   function combination(n, r) {
     return factorial(n) / (factorial(r) * factorial(n - r));
   }
   
   // Example usage
   console.log(combination(5, 2)); 
   // Output: 10
   

3. Fermat’s Little Theorem

   We know,

   $C(n, r) = \frac{n!}{r!(n-r)!}$

   ⇒ $C(n, r) = n!\frac{1}{r!}\frac{1}{(n-r)!}$

   ⇒ $C(n,r)=n! * inverse(r!) * inverse((n-r)!)$

   Fermet says,

   $\frac{1}{fact(n)} = mod(fact(n) ^ {m-2} ,{m} )$

   inverse(fact(n)) = fact(n)^{m-2} % m

   where,

   n = given number m = modular constant

Therefore,

If we have

1. An array fact that stores factorial of n
2. An array invFact that stores inverse of fact(n)

Then we can find any C(n,r) by the formula

((fact[n] * invfact[r]) % M * invFact[n-r]) % M

<aside> 💡 You might need to multiply two values at a time and mod it

</aside>

Time Complexity: $O(n^2)$

Space Complexity: $O(n^2)$

Time Complexity: $O(n)$

Space Complexity: $O(n)$

<aside> 💡 Due to the auxillary space used by the call stack, the factorial function would progressively take more time to execute. This auxillary space can be reduced by recursion with memoization. That would need some extra space usage by the memo object

</aside>

Time Complexity: $O(n)$

Space Complexity: $O(n)$

Previous

Introduction to Combinatorics

Next

Problems on Combinatorics