algorithmlanguage-agnosticcombinationsoverflowfactorial

Best way of calculating n choose k?

What is the most efficient method to evaluate the value of "n choose k" ? The brute force way I think would be to find n! / k! / (n-k)! by calculating each factorial separately.

A better strategy may be to use DP according to this recursive formula, nCk == (n-1)C(k-1) + (n-1)C(k). Is there any other better method to evaluate n choose k in terms of complexity and avoiding risk of overflow?

Solution

  • You could use the Multiplicative formula for this:

    enter image description here

    choose(n, k) = falling_factorial_pow(n, k) / factorial(k)
             = ( n * (n - 1) * (n - 2) * ... * (n - (k - 1)) )
             / ( k * (k - 1) * (k - 2) * ... * 1 )
             = Product (n - (k - i))) / i from i = 1 to k
             = Product (n + 1 - i) / i    from i = 1 to k

    http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula