0

The idea is to travel from the top left corner to the bottom right corner of a N*N matrix, where the only movement allowed is either down or to the right. No back tracking allowed. This is simple using dynamic programming as can be seen in the following geeks for geeks link. I have tried to understand how the same could be achieved using simple permutations and combinations. I have come across the following BetterExplained link. There's surely a mismatch in the problem they are solving. Is there a way to find a solution using the permutation and combination? A pointer that can help me understand the solution better?

Edit 1:

Following is an example of 3X3 matrix, when we go by Dynamic programming it shows 6 ways to reach from left topmost point to the bottom right most point, which is only feasible when use the formula 2(N-1)!/ (N-1)!(N-1)!. but I have listed 20 ways to reach from origin to destination underneath, which is 2N!/N!*N! or it is feasible that I have understood the question incorrectly, it is that we are already in left topmost cell and traversing to the right bottom most cell, in that case answer would be 6

enter image description here

Mrinal Kamboj
  • 11,300
  • 5
  • 40
  • 74
  • 1
    I'm voting to close this question as off-topic because the OP doesn't want to understand the correct answer he receives – fjardon Apr 03 '19 at 12:44
  • @fjardon that surely doesn't makes it off topic, i am browsing through the solutions suggested via link and I don't need to accept it, just to convince you. you may want to add an explanation in case you have got a better understanding – Mrinal Kamboj Apr 03 '19 at 12:50

3 Answers3

2

There are (n-1) among 2(n-1) ways to traverse a n*n matrix with the rules you gave.

A simple explanation: Since the only movements allowed are downward or rightward, the path has to be of length exactly 2(n-1).
More than that, in this path, there will be n-1 moves downward, and n-1 moves rightward(this is the only possible way to reach the bottom right corner from the top left corner).
So the (n-1) among 2(n-1) comes from all the possible ways to fit the n-1 moves downwards within the 2(n-1) moves to execute.

m.raynal
  • 2,983
  • 2
  • 21
  • 34
  • Are you suggesting that result would be **2nCn**, which would be **2n!/n!n!**, then that's not the correct solution, would be better if you can provide an example – Mrinal Kamboj Apr 03 '19 at 11:16
  • It is the correct solution, you can have a look at the answers to [this question](https://stackoverflow.com/questions/9105699/algorithm-for-finding-all-paths-in-a-nxn-grid) (especially the first one) if you're not convinced. But the reasoning is simple, so it should be self-sufficient. – m.raynal Apr 03 '19 at 12:23
  • If the matrix is NxN, then the path length is 2(N-1) – Matt Timmermans Apr 03 '19 at 12:50
  • @Matt, that's right, I'll edit the answer to include this fact. – m.raynal Apr 03 '19 at 13:24
  • thanks for the response, what I have understood is, for a `N*N` matrix, total number of paths are `2(N-1)`, now if we do `2(N-1)!/(N-1)!(N-1)!`, response is same as dynamic programming, but what I am confused about is 2(N-1) itself, since if create a simple 4X4 matrix, then total path in each direction would be 4 not 3, but dynamic programming is solving using the N-1 value, i just need to understand why N-1, otherwise am clear about usage of Permutation and Combination here – Mrinal Kamboj Apr 04 '19 at 06:11
  • please check the **Edit1**, where I have explained my perspective, its quite possible that my understanding of the problem set is not correct, then solution that you have suggested is correct – Mrinal Kamboj Apr 07 '19 at 12:40
  • It entirely depends on how long the path is, ultimately. In the `3x3` case, I'd go for 6 possibilities, since it takes 4 moves to go from top left to bottom right (Matt was right about the `2(N-1)`). I believe the important part in this problem is to 'see' why the `n among 2n` formula works (independently of whether it is `n` or `n-1`), because such a way to 'see' the problem will allow you to solve other ones where the `k among n` appears. – m.raynal Apr 07 '19 at 14:39
1

If the matrix is square (N x N), I believe the number of paths can be calculated as follows where n = N - 1:

from math import factorial

def number_of_paths(n):
    return int(factorial(2 * n) / (factorial(n) ** 2))

As for why... that's a little more complicated. First of all instead of thinking about going down and right, lets turn the matrix 45 degrees so that we are always going down, but choosing left or right.

Our matrix is now a diamond standing on it's end and forms the center of Pascal's triangle. This means we can look at the binomial coefficient at the center of the bottom row of Pascal's triangle which is twice the size of our matrix - 1.

We use the binomial coefficient because one interpretation of this is it shows the number of paths we can choose to get there.

For example in the 3 x 3 case, 2 * 3 - 1 = 5:

       [1]                          C(0,0)
     [1   1]                    C(1,0), C(1,1)
   [1   2   1]              C(2,0), C(2,1), C(2,2)
  1  [3   3]   1        C(3,0), C(3,1), C(3,1), C(3,1)
1   4 [!6!]  4   1  C(4,0), C(4,1), C(4,2), C(4,3), C(4,4)

   Answer is 6!              Answer is C(4, 2)!

The answer turns out to be (2n)! / n! ** 2 (derivation below) which we can calculate directly.

You can also generalise to non-square matrices by moving about the item in the bottom row you care about, at which point you basically just end up with C(n, k). Hopefully it's clear why.

Just the maths!

We can see from the diagram above that the first three values for N are:

N | Value
- + -------
1 | C(0, 0)
2 | C(2, 1)
3 | C(4, 2)

We can therefore see that the answer is:

= C(2(N - 1), N - 1)

let n = N-1
Given C(a, b) = a! / b!(a - b)!

= C(2n, n)
= (2n)! / n!(2n - n)!
= (2n)! / n! ** 2

A geometric interpretation of path length

Imagine the case of a 4x4 matrix to try and see why the length is 2(N-1). First a few observations:

  • All path lengths are identical
  • We can therefore consider any particular path to examine the length for all
  • Therefore lets consider the path from:
    • Top left to top right (all going right)
    • Then top right to bottom right (all down)

To begin we start at the top left with no moves having been made, and progress along the top side:

0 - - -     0 1 - -     0 1 2 -     0 1 2 3
- - - -  >  - - - -  >  - - - -  >  - - - -  
- - - -     - - - -     - - - -     - - - - 
- - - -     - - - -     - - - -     - - - -

After 3 moves we have traversed the length 4 side. So for a side of length N it takes N-1 moves to traverse. The same is true for the vertical, it will take us another N-1 moves to traverse from the top to the bottom:

0 1 2 3     0 1 2 3     0 1 2 3     0 1 2 3
- - - -  >  - - - 4  >  - - - 4  >  - - - 4  
- - - -     - - - -     - - - 5     - - - 5 
- - - -     - - - -     - - - -     - - - 6

Therefore the total path length is 2(N-1)

Jon Betts
  • 3,053
  • 1
  • 14
  • 12
  • thanks for the detailed explanation, where you have explained how do we use `C(N,K)` for the given question, which I was already clear about, please see my comments to other response, what i lack in understanding is why `N*N` matrix has `2(N-1)` paths, I have drawn `4*4 matrix` and number of paths or steps are` 2N = 8` not `2(N-1) = 6` – Mrinal Kamboj Apr 04 '19 at 06:17
  • I'm not quite sure how you are doing it, but a `4*4` matrix should have 20 different paths. If you are curious why the `N-1` instead of the `N` (like I substituted `n = N-1`), it's because `C(n, r)` starts at zero, not one. The top row of the pyramid represents `[C(0, 0)]`, the next is `[C(1, 0), C(1, 1)]`. Therefore to get the right values, we need the matrix size - 1. – Jon Betts Apr 04 '19 at 11:47
  • I've updated the answer to include more explicitly why it's N-1. Hope that helps. – Jon Betts Apr 04 '19 at 12:03
  • please check the **Edit1**, where I have explained my perspective, its quite possible that my understanding of the problem set is not correct, then solution that you have suggested is correct – Mrinal Kamboj Apr 06 '19 at 11:09
  • Accepting your one as a solution, though do review my edit, i hope that does clarify my understanding of the problem set – Mrinal Kamboj Apr 07 '19 at 12:39
  • I'm not sure how to review your edit. I've updated the explanation with a geometric reason why the path length is 2(N-1). Hopefully that will help. – Jon Betts Apr 09 '19 at 11:26
0

The total number of ways to travel from top left to the bottom right of a m*n grid using combinatorics is (n-1+m-1)!/(n-1)!(m-1)!

#include <iostream> 
using namespace std; 

int numberOfPaths(int m, int n) 
{ 
// We have to calculate m+n-2 C n-1 here 
// which will be (m+n-2)! / (n-1)! (m-1)! 
int path = 1; 
for (int i = n; i < (m + n - 1); i++) { 
    path *= i; 
    path /= (i - n + 1); 
} 
return path; 
} 
int main() 
{ 
cout << numberOfPaths(3, 3); 
return 0; 
}

output:6

confused_
  • 1,133
  • 8
  • 10