CombinatoricsUtils { public static long stirlingS2(final int n, final int k) throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException { if (k < 0) { throw new NotPositiveException(k); } if (k > n) { throw new NumberIsTooLargeException(k, n, true); } long[][] stirlingS2 = STIRLING_S2.get(); if (stirlingS2 == null) { final int maxIndex = 26; stirlingS2 = new long[maxIndex][]; stirlingS2[0] = new long[] { 1l }; for (int i = 1; i < stirlingS2.length; ++i) { stirlingS2[i] = new long[i + 1]; stirlingS2[i][0] = 0; stirlingS2[i][1] = 1; stirlingS2[i][i] = 1; for (int j = 2; j < i; ++j) { stirlingS2[i][j] = j * stirlingS2[i - 1][j] + stirlingS2[i - 1][j - 1]; } } STIRLING_S2.compareAndSet(null, stirlingS2); } if (n < stirlingS2.length) { return stirlingS2[n][k]; } else { if (k == 0) { return 0; } else if (k == 1 || k == n) { return 1; } else if (k == 2) { return (1l << (n - 1)) - 1l; } else if (k == n - 1) { return binomialCoefficient(n, 2); } else { long sum = 0; long sign = ((k & 0x1) == 0) ? 1 : -1; for (int j = 1; j <= k; ++j) { sign = -sign; sum += sign * binomialCoefficient(k, j) * ArithmeticUtils.pow(j, n); if (sum < 0) { throw new MathArithmeticException(LocalizedFormats.ARGUMENT_OUTSIDE_DOMAIN, n, 0, stirlingS2.length - 1); } } return sum / factorial(k); } } } 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(expected=NotPositiveException.class) public void testStirlingS2NegativeN() { CombinatoricsUtils.stirlingS2(3, -1); }
@Test(expected=NumberIsTooLargeException.class) public void testStirlingS2LargeK() { CombinatoricsUtils.stirlingS2(3, 4); }
@Test(expected=MathArithmeticException.class) public void testStirlingS2Overflow() { CombinatoricsUtils.stirlingS2(26, 9); }
@Test public void testStirlingS2() { Assert.assertEquals(1, CombinatoricsUtils.stirlingS2(0, 0)); for (int n = 1; n < 30; ++n) { Assert.assertEquals(0, CombinatoricsUtils.stirlingS2(n, 0)); Assert.assertEquals(1, CombinatoricsUtils.stirlingS2(n, 1)); if (n > 2) { Assert.assertEquals((1l << (n - 1)) - 1l, CombinatoricsUtils.stirlingS2(n, 2)); Assert.assertEquals(CombinatoricsUtils.binomialCoefficient(n, 2), CombinatoricsUtils.stirlingS2(n, n - 1)); } Assert.assertEquals(1, CombinatoricsUtils.stirlingS2(n, n)); } Assert.assertEquals(536870911l, CombinatoricsUtils.stirlingS2(30, 2)); Assert.assertEquals(576460752303423487l, CombinatoricsUtils.stirlingS2(60, 2)); Assert.assertEquals( 25, CombinatoricsUtils.stirlingS2( 5, 3)); Assert.assertEquals( 90, CombinatoricsUtils.stirlingS2( 6, 3)); Assert.assertEquals( 65, CombinatoricsUtils.stirlingS2( 6, 4)); Assert.assertEquals( 301, CombinatoricsUtils.stirlingS2( 7, 3)); Assert.assertEquals( 350, CombinatoricsUtils.stirlingS2( 7, 4)); Assert.assertEquals( 140, CombinatoricsUtils.stirlingS2( 7, 5)); Assert.assertEquals( 966, CombinatoricsUtils.stirlingS2( 8, 3)); Assert.assertEquals( 1701, CombinatoricsUtils.stirlingS2( 8, 4)); Assert.assertEquals( 1050, CombinatoricsUtils.stirlingS2( 8, 5)); Assert.assertEquals( 266, CombinatoricsUtils.stirlingS2( 8, 6)); Assert.assertEquals( 3025, CombinatoricsUtils.stirlingS2( 9, 3)); Assert.assertEquals( 7770, CombinatoricsUtils.stirlingS2( 9, 4)); Assert.assertEquals( 6951, CombinatoricsUtils.stirlingS2( 9, 5)); Assert.assertEquals( 2646, CombinatoricsUtils.stirlingS2( 9, 6)); Assert.assertEquals( 462, CombinatoricsUtils.stirlingS2( 9, 7)); Assert.assertEquals( 9330, CombinatoricsUtils.stirlingS2(10, 3)); Assert.assertEquals(34105, CombinatoricsUtils.stirlingS2(10, 4)); Assert.assertEquals(42525, CombinatoricsUtils.stirlingS2(10, 5)); Assert.assertEquals(22827, CombinatoricsUtils.stirlingS2(10, 6)); Assert.assertEquals( 5880, CombinatoricsUtils.stirlingS2(10, 7)); Assert.assertEquals( 750, CombinatoricsUtils.stirlingS2(10, 8)); }