android/guava/src/com/google/common/math/BigIntegerMath.java
public static BigInteger binomial(int n, int k) {
    checkNonNegative("n", n);
    checkNonNegative("k", k);
    checkArgument(k <= n, "k (%s) > n (%s)", k, n);
    if (k > (n >> 1)) {
      k = n - k;
    }
    if (k < LongMath.biggestBinomials.length && n <= LongMath.biggestBinomials[k]) {
      return BigInteger.valueOf(LongMath.binomial(n, k));
    }

    BigInteger accum = BigInteger.ONE;

    long numeratorAccum = n;
    long denominatorAccum = 1;

    int bits = LongMath.log2(n, RoundingMode.CEILING);

    int numeratorBits = bits;

    for (int i = 1; i < k; i++) {
      int p = n - i;
      int q = i + 1;

      // log2(p) >= bits - 1, because p >= n/2

      if (numeratorBits + bits >= Long.SIZE - 1) {
        // The numerator is as big as it can get without risking overflow.
        // Multiply numeratorAccum / denominatorAccum into accum.
        accum =
            accum
                .multiply(BigInteger.valueOf(numeratorAccum))
                .divide(BigInteger.valueOf(denominatorAccum));
        numeratorAccum = p;
        denominatorAccum = q;
        numeratorBits = bits;
      } else {
        // We can definitely multiply into the long accumulators without overflowing them.
        numeratorAccum *= p;
        denominatorAccum *= q;
        numeratorBits += bits;
      }
    }
    return accum
        .multiply(BigInteger.valueOf(numeratorAccum))
        .divide(BigInteger.valueOf(denominatorAccum));
  }
public static BigInteger binomial(int n, int k) {
    checkNonNegative("n", n);
    checkNonNegative("k", k);
    checkArgument(k <= n, "k (%s) > n (%s)", k, n);
    if (k > (n >> 1)) {
      k = n - k;
    }
    if (k < LongMath.biggestBinomials.length && n <= LongMath.biggestBinomials[k]) {
      return BigInteger.valueOf(LongMath.binomial(n, k));
    }

    BigInteger accum = BigInteger.ONE;

    long numeratorAccum = n;
    long denominatorAccum = 1;

    int bits = LongMath.log2(n, RoundingMode.CEILING);

    int numeratorBits = bits;

    for (int i = 1; i < k; i++) {
      int p = n - i;
      int q = i + 1;

      // log2(p) >= bits - 1, because p >= n/2

      if (numeratorBits + bits >= Long.SIZE - 1) {
        // The numerator is as big as it can get without risking overflow.
        // Multiply numeratorAccum / denominatorAccum into accum.
        accum =
            accum
                .multiply(BigInteger.valueOf(numeratorAccum))
                .divide(BigInteger.valueOf(denominatorAccum));
        numeratorAccum = p;
        denominatorAccum = q;
        numeratorBits = bits;
      } else {
        // We can definitely multiply into the long accumulators without overflowing them.
        numeratorAccum *= p;
        denominatorAccum *= q;
        numeratorBits += bits;
      }
    }
    return accum
        .multiply(BigInteger.valueOf(numeratorAccum))
        .divide(BigInteger.valueOf(denominatorAccum));
  }
public static BigInteger binomial ( int n , int k ) { checkNonNegative ( "n" , n ) ; checkNonNegative ( "k" , k ) ; checkArgument ( k <= n , "k (%s) > n (%s)" , k , n ) ; if ( k > ( n >> 1 ) ) { k = n - k ; } if ( k < LongMath . biggestBinomials . length && n <= LongMath . biggestBinomials [ k ] ) { return BigInteger . valueOf ( LongMath . binomial ( n , k ) ) ; } BigInteger accum = BigInteger . ONE ; long numeratorAccum = n ; long denominatorAccum = 1 ; int bits = LongMath . log2 ( n , RoundingMode . CEILING ) ; int numeratorBits = bits ; for ( int i = 1 ; i < k ; i ++ ) { int p = n - i ; int q = i + 1 ; // log2(p) >= bits - 1, because p >= n/2 if ( numeratorBits + bits >= Long . SIZE - 1 ) { // The numerator is as big as it can get without risking overflow. // Multiply numeratorAccum / denominatorAccum into accum. accum = accum . multiply ( BigInteger . valueOf ( numeratorAccum ) ) . divide ( BigInteger . valueOf ( denominatorAccum ) ) ; numeratorAccum = p ; denominatorAccum = q ; numeratorBits = bits ; } else { // We can definitely multiply into the long accumulators without overflowing them. numeratorAccum *= p ; denominatorAccum *= q ; numeratorBits += bits ; } } return accum . multiply ( BigInteger . valueOf ( numeratorAccum ) ) . divide ( BigInteger . valueOf ( denominatorAccum ) ) ; }
Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and
{@code k}, that is, {@code n! / (k! (n - k)!)}.

<p><b>Warning:</b> the result can take as much as <i>O(k log n)</i> space.

@throws IllegalArgumentException if {@code n < 0}, {@code k < 0}, or {@code k > n}
Returns { @code n } choose { @code k } also known as the binomial coefficient of { @code n } and { @code k } that is { @code n! / ( k! ( n - k ) ! ) } .