CombinatoricsUtils { public static long binomialCoefficient(final int n, final int k) throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException { CombinatoricsUtils.checkBinomial(n, k); if ((n == k) || (k == 0)) { return 1; } if ((k == 1) || (k == n - 1)) { return n; } if (k > n / 2) { return binomialCoefficient(n, n - k); } long result = 1; if (n <= 61) { int i = n - k + 1; for (int j = 1; j <= k; j++) { result = result * i / j; i++; } } else if (n <= 66) { int i = n - k + 1; for (int j = 1; j <= k; j++) { final long d = ArithmeticUtils.gcd(i, j); result = (result / (j / d)) * (i / d); i++; } } else { int i = n - k + 1; for (int j = 1; j <= k; j++) { final long d = ArithmeticUtils.gcd(i, j); result = ArithmeticUtils.mulAndCheck(result / (j / d), i / d); i++; } } return result; } private  CombinatoricsUtils(); static long binomialCoefficient(final int n, final int k); static double binomialCoefficientDouble(final int n, final int k); static double binomialCoefficientLog(final int n, final int k); static long factorial(final int n); static double factorialDouble(final int n); static double factorialLog(final int n); static long stirlingS2(final int n, final int k); static Iterator<int[]> combinationsIterator(int n, int k); static void checkBinomial(final int n,
                                     final int k);  }
@Test public void testBinomialCoefficient() { long[] bcoef5 = { 1, 5, 10, 10, 5, 1 }; long[] bcoef6 = { 1, 6, 15, 20, 15, 6, 1 }; for (int i = 0; i < 6; i++) { Assert.assertEquals("5 choose " + i, bcoef5[i], CombinatoricsUtils.binomialCoefficient(5, i)); } for (int i = 0; i < 7; i++) { Assert.assertEquals("6 choose " + i, bcoef6[i], CombinatoricsUtils.binomialCoefficient(6, i)); } for (int n = 1; n < 10; n++) { for (int k = 0; k <= n; k++) { Assert.assertEquals(n + " choose " + k, binomialCoefficient(n, k), CombinatoricsUtils.binomialCoefficient(n, k)); Assert.assertEquals(n + " choose " + k, binomialCoefficient(n, k), CombinatoricsUtils.binomialCoefficientDouble(n, k), Double.MIN_VALUE); Assert.assertEquals(n + " choose " + k, FastMath.log(binomialCoefficient(n, k)), CombinatoricsUtils.binomialCoefficientLog(n, k), 10E-12); } } int[] n = { 34, 66, 100, 1500, 1500 }; int[] k = { 17, 33, 10, 1500 - 4, 4 }; for (int i = 0; i < n.length; i++) { long expected = binomialCoefficient(n[i], k[i]); Assert.assertEquals(n[i] + " choose " + k[i], expected, CombinatoricsUtils.binomialCoefficient(n[i], k[i])); Assert.assertEquals(n[i] + " choose " + k[i], expected, CombinatoricsUtils.binomialCoefficientDouble(n[i], k[i]), 0.0); Assert.assertEquals("log(" + n[i] + " choose " + k[i] + ")", FastMath.log(expected), CombinatoricsUtils.binomialCoefficientLog(n[i], k[i]), 0.0); } }