Number of paths in 2D matrix - PrismoSkills

Number of paths in 2D matrix - PrismoSkills

Puzzle: Given a 2D matrix with N rows and M columns.
You have to move from upper left corner to diagonally opposite, lower right corner.
If only valid moves at any given cell are Move 1 cell Right or Move 1 cell down, then
calculate the total number of ways in which you can move from source to destination.




Solution: In any path, total moves required to move from start to end are N+M-2

Out of these, (N-1) moves must be down and (M-1) moves must be towards right.

(N-1) moves can be chosen from (N+M-2) moves in ^N+M-2C_N-1 ways.

So total number of ways to move are also the same = ^N+M-2C_N-1 = (N+M-2)! / (N-1)! (M-1)!

Verification:

For 3x2 matrix, ways = 3!/2!1! = 3

Read full article from Number of paths in 2D matrix - PrismoSkills