Calculate nCr in counting all possible paths problem

Question

I have a doubt in how did the author reach the intuition behind the formula to calculate the (m + n -2)C n-1 in this problem - https://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/

Please scroll down to solution by using combinatorics.

Particularly talking, I don't understand how the below code was developed for what is basically a nCr

 for (int i = n; i < (m + n - 1); i++) { 
        path *= i; 
        path /= (i - n + 1); 
    }

I mean, if I put values into it, I get it. But, if you understand my pain, how will I reach this had I not known. Searching for how to calculate nCr gives different solutions.

And this is some observation put into practice. Even if anyone can point me to a different straightforward formula for calculating the same thing will be great. It is not that easy to consume this after all without the observation put behind it which may have taken time. Just curious at the same time why is this not solved using standard way to solve nCr. Like the one here - https://www.geeksforgeeks.org/program-to-calculate-the-value-of-ncr-efficiently/

IMHO your question is more a mathematical question. You can proof the formula Npath(n,m) = (m+n-2)! / ((n-1)! (m-1)!) by using the fact that Npath(n,m) = Npath(n-1,m) +Npath(n,m-1) holds. Use also the fact that Npath(n,1) = Npath(1,m) =1. You can do the proof with mathematical induction. — BlueTune, Mar 15 '20 at 18:38

score 1 · Answer 1 · answered Nov 19 '20 at 11:16

The formula for nCr(n,k) is:

| n |      n!
|   | = ---------
| k |   k!.(n-k)!

The problem is that the factorials will get very big soon and overflow standard variables even for small inputs. To avoid that we just eliminate redundant operations... I can rewrite to this:

| n |      n!       1*2*3*...*n
|   | = --------- = -----------------------------
| k |   k!.(n-k)!   1*2*3*...*k * 1*2*3*...*(n-k)

Now we can see that first n-r or k (depends on which is bigger) multiplications are the same on both sides of the division so we can skip them so (in case k>=n-r):

| n |      n!       (k+1)*(k+2)*(k+3)*...*n
|   | = --------- = -----------------------------
| k |   k!.(n-k)!       1*2*3*...*(n-k)

Also if we do this in loop and divide after each multiplication the sub result will keep small:

| n |      n!       (k+1)   (k+2)   (k+3)          (n)
|   | = --------- = ----- * ----- * ----- * ... * -----
| k |   k!.(n-k)!     1       2       3           (n-k)

And yes there is the same number of therms on both sides of the division. If I understood it correctly your code should do nCr(m+n-2,n-1) so the substitution to match formula will be:

n` = m+n-2
k` = n-1

rewriting to:

| m+n-2 |   (n-1+1)   (n-1+2)   (n-1+3)           (m+n-2)
|       | = ------- * ------- * ------- * ... * -----------
|  n-1  |     1          2         3            (m+n-2-n+1)

| m+n-2 |   (n)   (n+1)   (n+2)         (m+n-2)
|       | = --- * ----- * ----- * ... * -------
|  n-1  |    1      2       3            (m-1)

so your loop is doing a PI of i/(i-n+1) where i={ n,n+1,...,m+n-1 } which matches the equation above...

Beware this is not exact nCr as it needs to be computed on floating point so rounding errors occurs on each iteration !!! So the output can be off a small bit !!! However this can be computed on Integers in similar manner (without any precision loss) but instead of dividing at each iterations you divide both dividents with common divisors to keep them "small". Ideally by first few primes. Here a small C++ example of this (both float and int versions) I just bustled together:

//---------------------------------------------------------------------------
//
//  | n |      n!       combinations = fact(n)/(fact(k)*fact(n-k))
//  |   | = ---------   how many combinations of k items from n items are possible
//  | k |   k!.(n-k)!   when order does not matter
//
DWORD nCr(DWORD n,DWORD k)
    {
    DWORD a,b,ia,ib,j,m,p;
    const DWORD prime[]={2,3,5,7,11,13,17,19,23,29,31,0};
    if (k> n) return 0;
    if (k==n) return 1;
    m=n-k;
    for (a=1,b=1,ia=k+1,ib=2;(ia<=n)||(ib<=m);)
        {
        if ((b<=a)&&(ib<=m)){ b*=ib; ib++; }    // multiply the smaller number if possible
        else     if (ia<=n) { a*=ia; ia++; }
        for (;((a|b)&1)==0;a>>=1,b>>=1);        // divide a,b by 2 if possible
        for (j=1;;j++)                          // divide a,b by next few prmes (skip 2) if possible
            {
            p=prime[j];
            if (!p) break;
            if (a<p) break;
            if (b<p) break;
            for (;(a%p)+(b%p)==0;a/=p,b/=p);
            }
        }
    return a/b;
    }
//---------------------------------------------------------------------------
float nCr_approx(DWORD n,DWORD k)
    {
    if (k> n) return 0;
    if (k==n) return 1;
    float c;
    DWORD i,m=n-k;
    for (c=1.0,i=1;i<=m;i++)
        {
        c*=(k+i);
        c/=(i);
        }
    return c;
    }
//---------------------------------------------------------------------------

Where DWORD is 32 bit unsigned integer (but any integer variable type can be used)... This works correctly (on 32 bit ) up to nCr(32,15) Here comparison between the two:

 n    k   nCr(n,k)     nCr_approx(n,k)
 32   0          1               1.000 
 32   1         32              32.000 
 32   2        496             496.000 
 32   3       4960            4960.000 
 32   4      35960           35960.000 
 32   5     201376          201376.000 
 32   6     906192          906191.938  *** float is off
 32   7    3365856         3365856.000 
 32   8   10518300        10518300.000 
 32   9   28048800        28048802.000  *** float is off 
 32  10   64512240        64512240.000 
 32  11  129024480       129024488.000  *** float is off 
 32  12  225792840       225792864.000  *** float is off 
 32  13  347373600       347373632.000  *** float is off 
 32  14  471435600       471435584.000  *** float is off 
 32  15  565722720       565722688.000  *** float is off 
 32  16   64209478       601080384.000  *** int overflow
 32  17  565722720       565722752.000  *** float is off  
 32  18  471435600       471435584.000  *** float is off 
 32  19  347373600       347373600.000 
 32  20  225792840       225792832.000  *** float is off  
 32  21  129024480       129024488.000  *** float is off  
 32  22   64512240        64512236.000  *** float is off  
 32  23   28048800        28048800.000 
 32  24   10518300        10518299.000  *** float is off  
 32  25    3365856         3365856.000 
 32  26     906192          906192.000 
 32  27     201376          201376.000 
 32  28      35960           35960.000 
 32  29       4960            4960.000 
 32  30        496             496.000 
 32  31         32              32.000 
 32  32          1               1.000

Yes you can use double instead but always take in mind the result might be slightly off !!!

Calculate nCr in counting all possible paths problem

1 Answers1

Linked