How to Compute Binomial Coefficients in Java

1. Binomial Coefficients
2. Use CERN’s Colt Library to Compute Binomial Coefficients in Java
3. Use Apache Commons Numbers Library to Compute Binomial Coefficients in Java
4. References
5. Conclusion

This article will look at two popular Java libraries that we can use to compute binomial coefficients.

Binomial Coefficients

Binomial coefficients also referred to as n choose r or choose(n, r) (sometimes n choose k), are always integers. They rapidly grow to large values as n rises, and r is neither close to 1 nor n.

However, programming languages can only represent integers within a limited range using their integer data types.

Therefore, software libraries return binomial coefficients as integers only up to a limit. For larger values of n, they use methods that return binomial coefficients as decimal values of the double data type.

Use CERN’s Colt Library to Compute Binomial Coefficients in Java

CERN’s colt library’s binomial() function can be used to compute a binomial coefficient. This library always returns double type decimal values only.

In the example, the values of n and r are hard-coded; these may be changed per need, or the program may be modified to accept user input.

Example Code:

import cern.jet.math.Arithmetic;

class combinatorial {
  public static void main(String args[]) {
    long N = 60, R = 15;
    double chs;
    chs = Arithmetic.binomial(N, R);
    System.out.println(chs);
  }
}

Output:

5.319408919271999E13

Use Apache Commons Numbers Library to Compute Binomial Coefficients in Java

The Apache Commons Numbers library has a BinomialCoefficient class that returns long type integers for n as large as 66.

For larger values of n, we need to use the BinomialCoefficientDouble class from the same package.

Both methods are demonstrated in the code segments given below. The n and r values are hard-coded in the examples.

Example Code for BinomialCoefficient:

import org.apache.commons.numbers.combinatorics.BinomialCoefficient;

public class apa_bincoeff {
  public static void main(String args[]) {
    int N = 60, R = 15;
    long nchr;
    nchr = BinomialCoefficient.value(N, R);
    System.out.println(nchr);
  }
}

Output:

53194089192720

We can see from the output that this class returns an exact integer rather than a rounded decimal for the specific n and r used.

Example Code for BinomialCoefficientDouble:

import org.apache.commons.numbers.combinatorics.BinomialCoefficientDouble;

public class apa_binom_dbl {
  public static void main(String args[]) {
    int N = 95, R = 35;
    double nchrd;
    nchrd = BinomialCoefficientDouble.value(N, R);
    System.out.println(nchrd);
  }
}

Output:

1.2014118724871557E26

References

For the Colt library, see its website.

For the Apache Commons Number library, see the package documentation.

Conclusion

For n up to 66, the Apache BinomialCoefficient class gives an exact integer. For larger n, either Apache’s BinomialCoefficientDouble class or colt’s binomial function may be used.