how to find n choose r without overflow

Question

I need to find the value of n choose r- the number of ways of selecting r objects out of n.

if i first find the numerator then the denominator. i get an exception.

i am using java.

how to do it for example for 44 choose 42

Answer 1

You can use the fact that NcR is equal to Nc(N-R). The formula is:

 N * (N - 1) * ... * (N - R + 1)
---------------------------------
         1 * 2 * ... * R

You can observe that product of K consecutive numbers is always divisible by K. So, the loop would look like

• multiply two numbers from nominator
• divide by 2
• multiply by the 3rd number from nominator
• divide by 3
• ...
• multiply by the last number from the nominator
• divide by R

Alternatively, just use java.math.BigInteger.

Answer 2

You'll find many good answers here:

http://stackoverflow.com/questions/2201113/combinatoric-n-choose-r-in-java-math