Combinatoric 'N choose R' in java math?

Question

Is there a built in method in a java library that can compute 'N choose R' for any N, R?

Answer 1

The mathematical formula for this is:

N!/((R!)(N-R)!)

Shouldn't be hard to figure it out from there :)

Answer 2

The apache-commons "Math" supports this: MathUtils.binomialCoefficient

Answer 3

binomialCoefficient, in Commons Math

Answer 4

I am just trying to calculate number of 2 card combinations with different deck sizes...

No need to import an external library - from the definition of combination, with n cards that would be n*(n-1)/2

Bonus question: This same formula calculates the sum of the first n-1 integers - do you see why they're the same? :)

Answer 5

The recursive definition gives you a pretty simple choose function which won't have trouble except for large values. If you're planning on running this method a lot, or on large values, it would pay to memoize it, but otherwise works just fine.

public static long choose(long total, long choose){
    if(total < choose)
        return 0;
    if(choose == 0 || choose == total)
        return 1;
    return choose(total-1,choose-1)+choose(total-1,choose);
}

Answer 6

N!/((R!)(N-R)!)

There is a lot you can cancel down in this formula, so usually the factorials are no problem. Let's say that R > (N-R) then cancel down N!/R! to (R+1) * (R+2) * ... * N. But true, int is very limited (around 13!).

But then one could with each iteration also divide. In pseudocode:

d := 1
r := 1

m := max(R, N-R)+1
for (; m <= N; m++, d++ ) {
    r *= m
    r /= d
}

It is important to start the division with one, even though this seems to be superfluous. But let's make an example:

for N = 6, R = 2: 6!/(2!*4!) => 5*6/(1*2)

If we leave 1 out we would calculate 5/2*6. The division would leave the integer domain. Leaving 1 in we guarantee that we don't do that as either the first or second operand of the multiplication is even.

For the same reason we do not use r *= (m/d).

The whole thing could be revised to

r := max(R, N-R)+1
for (m := r+1,d := 2; m <= N; m++, d++ ) {
    r *= m
    r /= d
}

Answer 7

The Formula

It's actually very easy to compute N choose K without even computing factorials.

We know that the formula for (N choose K) is:

    N!
 --------
 (N-K)!K!

Therefore, the formula for (N choose K+1) is:

       N!                N!                   N!               N!      (N-K)
---------------- = --------------- = -------------------- = -------- x -----
(N-(K+1))!(K+1)!   (N-K-1)! (K+1)!   (N-K)!/(N-K) K!(K+1)   (N-K)!K!   (K+1)

That is:

(N choose K+1) = (N choose K) * (N-K)/(K+1)

We also know that (N choose 0) is:

 N!
---- = 1
N!0!

So this gives us an easy starting point, and using the formula above, we can find (N choose K) for any K > 0 with K multiplications and K divisions.

---

Easy Pascal's Triangle

Putting the above together, we can easily generate Pascal's triangle as follows:

    for (int n = 0; n < 10; n++) {
        int nCk = 1;
        for (int k = 0; k <= n; k++) {
            System.out.print(nCk + " ");
            nCk = nCk * (n-k) / (k+1);
        }
        System.out.println();
    }

This prints:

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 

---

BigInteger version

Applying the formula for BigInteger is straightforward:

static BigInteger binomial(final int N, final int K) {
    BigInteger ret = BigInteger.ONE;
    for (int k = 0; k < K; k++) {
        ret = ret.multiply(BigInteger.valueOf(N-k))
                 .divide(BigInteger.valueOf(k+1));
    }
    return ret;
}

//...
System.out.println(binomial(133, 71));
// prints "555687036928510235891585199545206017600"

According to Google, 133 choose 71 = 5.55687037 × 10³⁸.

---

References

• Wikipedia/Binomial coefficient
• Wikipedia/Pascal's triangle
• Wikipedia/Combination