https://stackoverflow.com/questions/9330915/number-of-combinations-n-choose-r-in-c

The definition of N choose R is to compute the two products and divide one with the other,

nChooseR = n! / ((n - r)! * r!)

         = (N * N-1 * N-2 * ... * N-R+1) / (1 * 2 * 3 * ... * R)

However, the multiplications may become too large really quick and overflow existing data type. The implementation trick is to reorder the multiplication and divisions as,

     (N)/1 * (N-1)/2 * (N-2)/3 * ... * (N-R+1)/R

It's guaranteed that at each step the results is divisible (for n continuous numbers, one of them must be divisible by n, so is the product of these numbers).

For example, for N choose 3, at least one of the N, N-1, N-2 will be a multiple of 3, and for N choose 4, at least one of N, N-1, N-2, N-3 will be a multiple of 4.

C++ code given below.

int NCR(int n, int r)
{
    if (r == 0) return 1;

    /*
     Extra computation saving for large R,
     using property:
     N choose R = N choose (N-R)
    */
    if (r > n / 2) return NCR(n, n - r); 

    long res = 1; 

    for (int k = 1; k <= r; ++k)
    {
        res *= n - k + 1;
        res /= k;
    }

    return res;
}

nChooseR = n! / ((n - r)! * r!)

5 choose 3 : n - r + 1 = 4

5 x 4 x 3 x 2 x 1 / ( 1 x 2 * 1 x 2 x 3) = 5/1  x 4/2  = n choose ( n - r )

7 choose 3 : n - r + 1 = 5

7 6 5 4 3 2 1 / 1 2 3 4 * 1 2 3 = 7/1 * 6/2 * 5/3