Combinatoric 'N choose R' in java math?

The apache-commons "Math" supports this in org.apache.commons.math4.util.CombinatoricsUtils

The recursive definition gives you a pretty simple choose function which will work fine for small 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);
}

Improving the runtime of this function is left as an exercise for the reader :)

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? :)

binomialCoefficient, in Commons Math

Returns an exact representation of the Binomial Coefficient, "n choose k", the number of k-element subsets that can be selected from an n-element set.

The mathematical formula for this is:

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

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

The following routine will compute the n-choose-k, using the recursive definition and memoization. The routine is extremely fast and accurate:

inline unsigned long long n_choose_k(const unsigned long long& n,
                                     const unsigned long long& k)
{
   if (n  < k) return 0;
   if (0 == n) return 0;
   if (0 == k) return 1;
   if (n == k) return 1;
   if (1 == k) return n;
   typedef unsigned long long value_type;
   value_type* table = new value_type[static_cast<std::size_t>(n * n)];
   std::fill_n(table,n * n,0);
   class n_choose_k_impl
   {
   public:

      n_choose_k_impl(value_type* table,const value_type& dimension)
      : table_(table),
        dimension_(dimension)
      {}

      inline value_type& lookup(const value_type& n, const value_type& k)
      {
         return table_[dimension_ * n + k];
      }

      inline value_type compute(const value_type& n, const value_type& k)
      {
         if ((0 == k) || (k == n))
            return 1;
         value_type v1 = lookup(n - 1,k - 1);
         if (0 == v1)
            v1 = lookup(n - 1,k - 1) = compute(n - 1,k - 1);
         value_type v2 = lookup(n - 1,k);
         if (0 == v2)
            v2 = lookup(n - 1,k) = compute(n - 1,k);
         return v1 + v2;
      }

      value_type* table_;
      value_type dimension_;
   };
   value_type result = n_choose_k_impl(table,n).compute(n,k);
   delete [] table;
   return result;
}

Already there are a lots of solutions submitted.

1. Some solution didn't consider integer overflow.

2. Some solution calculated all possible nCr while given n and r. Result is more time and space needed.

In most cases we need to calculate nCr directly. I am going to share one more solution.

static long gcd(long a, long b) {
    if (a == 0) return b;
    return gcd(b%a, a);
}

// Compute (a^n) % m
static long bigMod(long a, long n, long m) {
    if (n == 0) return 1;
    if (n == 1) return a % m;
    long ret = bigMod(a, n/2, m);
    ret = (ret * ret) % m;
    if (n % 2 == 1) return (ret * a) % m;
    return ret;
}

// Function to find (1/a mod m).
// This function can find mod inverse if m are prime
static long modInverseFarmetsTheorem(long a, long m) {
    if (gcd(a, m) != 1) return -1;

    return bigMod(a, m-2, m);
}

// This function finds ncr using modular multiplicative inverse
static long ncr(long n, long r, long m) {
    if (n == r) return 1;
    if (r == 1) return n;

    long start = n - Math.max(r, n - r) + 1;

    long ret = 1;
    for (long i = start; i <= n; i++) ret = (ret * i) % m;

    long until = Math.min(r, n - r), denom = 1;
    for (long i = 1; i <= until; i++) denom = (denom * i)  % m;

    ret = (ret * modInverseFarmetsTheorem(denom, m)) % m;

    return ret;
}

Instead of implementing n choose k recursively (which can get slow with large numbers), we can also make use of the fact that:

                n(n-1)(n-2)...(n-k+1)
  n choose k =  --------------------
                        k!

We still need to calculate k!, but this can be done much faster than the recursive method.

private static long choose(long n, long k) {
    long numerator = 1;
    long denominator = 1;

    for (long i = n; i >= (n - k + 1); i--) {
        numerator *= i;
    }

    for (long i = k; i >= 1; i--) {
        denominator *= i;
    }

    return (numerator / denominator);
}

Be aware that the choose method above assumes that neither n nor k is negative. Also, the long data type can overflow for large enough values. A BigInteger version should be used if the result resp. numerator and/or denominator are expected to exceed 64 bits.