Amusements

The well-known formula for calculating the number of combinations of n objects with r objects taken a t a time is

but this requires calculating three factorials which may be expensive and may cause overflow. A better way is to use the other definition

and doing multiplication and division alternatively. An example is the C++ code below:

int nCr (int n, int r)
{
   int ncr = n;
   int k = 1;
   int r1 = n - r;

   // Handle special cases
   if (r1 < 0) { return 0;}    // Invalid value
   if (r1 < r) { r = r1;}      // nCr = nC(n-r)
   if (r == 0) { return 1;}    // nC0 = 1

   // To avoid integer overflow, divide as early as possible
   for (int k = 2; k <= r; ++k) {
     ncr *= --n;
     ncr /= k;
   }
   return ncr;
}