Number of Shortest Paths in an n x m Grid (Combinatorics Puzzle)
Source: Solved it during Algorithms Course under Prof Diwan, and discussed with Nikhil Jain (IT BHU 2008 Alumnus, Product Manager at AskLaila)
1. (Easy)
Consider a n x m rectangular grid. The problem is to find the number of shortest (or monotonic in this case) paths along the edges of the cell that start at (0,0) and end at (n,m).
A monotonic path is a path always moving towards the goal, i.e. consists of moving up or right but not down or left. Figure 1 illustrates such a path for a grid of size 5 x 3.
2. (Difficult)
Now we need to print all monotonic paths that do not go above the diagonal y = x. Figure 2 shows such a path. Note that the path in figure 1 goes above the diagonal, hence not desirable in this case. How many such paths exist for n x m grid (n >= m)?
Disclaimer:
The first problem is too simple, and the second is very challenging. Have fun :-)
Solution:
Highlight the part between the * symbols for the answer.
* Part 1: C(n+m, m). Every monotonic path from (0,0) to (n,m) consists of n right-moves and m up-moves in some order, and any ordering works - so the count is the number of ways to choose which of the n+m steps are up-moves: (n+m)! / (n! m!).
Part 2 (paths never going above y = x, with n >= m): C(n+m, m) - C(n+m, m-1) = (n - m + 1)/(n + 1) * C(n+m, m). Proof by the reflection principle: a "bad" path is one that touches the line y = x + 1. Reflect the portion of each bad path up to its first contact with y = x + 1 across that line; this gives a bijection between bad paths from (0,0) to (n,m) and ALL monotonic paths from (-1,1) to (n,m). The latter need n+1 right-moves and m-1 up-moves: C(n+m, m-1). Subtracting from the total gives the formula. For n = m this is the Catalan number C(2n, n)/(n+1).
Solution by Shubham Gupta from the comments. *
8C3 or 8C5 = 56 i.e., (n+m)Cn for the first one. Still figuring the second one.
ReplyDeletefirst problem which is too simple :
ReplyDeletestatic int counter;
int noOfRows = 3;
int noOfColumns = 3;
int noOfPaths = numberOfWays(noOfRows, noOfColumns, 0, 0)
public static int numberOfWays(int rows, int cols, int row, int col){
if(row > rows || col > cols) return 0;
if(row == rows && col == cols){
counter++;
}
numberOfWays(rows, cols, row+1, col);
numberOfWays(rows, cols, row, col+1);
return counter;
}
For second problem simply adding one more condition as suggested in the question itself should do:
ReplyDelete//counter is static variable
static int counter;
int noOfRows = 3;
int noOfColumns = 3;
int noOfPaths = numberOfWays(noOfRows, noOfColumns, 0, 0)
public static int numberOfWays(int rows, int cols, int row, int col){
if(row > rows || col > cols) return 0;
if(! (row>=col)) return 0; //--> this has been //added.
if(row == rows && col == cols){
counter++;
}
numberOfWays(rows, cols, row+1, col);
numberOfWays(rows, cols, row, col+1);
return counter;
}
Solving this problem in non-recursive call would be interesting.
For the difficult puzzle: If m=n, the answer is Catalan numbers. Maybe it's possible to generalize that proof idea for m!=n?
ReplyDelete1) 56
ReplyDelete2) by first eliminating the left most row and converting the problem to 4*3 since no steps can be on left most edge and than subtracting the rest of ways involving steps above the diagonal: 27
Let W(m,n) be the total number of ways of going from point (0,0) to (m,n) monotonically.
ReplyDeleteSolution to part 1
Let S(0,n) = 1. (for all n)
Then S(l,n) = Summation from k=1 to k=n (S(l-1,k)).
ie. S(1,n) = n.
S(2,n) = n(n+1)/2.
and so on..
Then W(m,n) = Summation from l=0 to l=m (S(l,n)).
Solution to part 2
If W'(m,n) be total no. of ways then
W'(m,n) = W(m,n) - no. of paths which lie above the diagonal - no. of paths which cut the diagonal at (1,1) while going towards north - no. of paths which cut the diagonal at (2,2) while going towards north - and so on.
W'(m,n) = W(m,n) - summation from p=0 to p=m-1 (W(p,n-m+2+p)).
The second part of my first post was wrong..
ReplyDeleteLet W(m,n) be the total number of ways of going from point (0,0) to (m,n) monotonically.
Solution to part 1
Let S(0,n) = 1. (for all n)
Then S(l,n) = Summation from k=1 to k=n (S(l-1,k)).
ie. S(1,n) = n.
S(2,n) = n(n+1)/2.
and so on..
Then W(m,n) = Summation from l=0 to l=m (S(l,n)).
Solution to part 2
If W'(m,n) be total no. of ways in which the path doesn't go above the diagonal, then
W'(m,n) = W(m,n) - no. of paths which starts above the diagonal - no. of paths which cut the diagonal at (1,1) while going towards north - no. of paths which cut the diagonal at (2,2) while going towards north - and so on.
W'(m,n) = W(m,n) - summation from p=0 to p=m-1 (W(p,n-m+1+p)).
Again there is a mistake in my second part :P
ReplyDeleteThe answer should be
W'(m,n) = W(m,n) - summation from p=0 to p=m-1 [f(p)x(W(p,n-m+1+p))].
where f(m-1) = f(m-2) = 1
and f(p) = 2f(p+1) +1.
For (3,5) the answer comes out to be 56 and 28.
Also W(m,n) = (m+n)Cn.
I guess the answer to the 2nd part is 47.
ReplyDeleteLet i denote the row number and j denote the column number
Let f(i, j) denote the count of possible number of options to go in the (i+1)th row from the point (i,j) after MANDATORY 1st STEP IN THE NORTH. So,
Correct Options = f(0,0) + f(0,1) + f(0,2) + f(0,3) + f(0,4) + f(0,5)
Now, f(0,0) = 0 since we can't go north on the first step.
Now, we can go to points (1,1), (1,2)...(1,5) from (1,1), but not on (0,0) because then we have to take a step back.
So,
f(0,1) = f(1,1) + f(1,2) + f(1,3) + f(1,4) + f(1,5)
Similarly,
f(0,2) = f(1,2) + f(1,3) + f(1,4) + f(1,5)
f(0,3) = f(1,3) + f(1,4) + f(1,5)
f(0,4) = f(1,4) + f(1,5)
f(0,5) = f(1,5)
So Correct Options = 0 + f(1,1) + 2f(1,2) + 3f(1,3) + 4f(1,4) + 5f(1,5)
= f(1,1) + 2f(1,2) + 3f(1,3) + 4f(1,4) + 5f(1,5)
On the same lines,
f(1,1) = 0
f(1,2) = f(2,2) + f(2,3) + f(2,4) + f(2,5)
f(1,3) = f(2,3) + f(2,4) + f(2,5)
f(1,4) = f(2,4) + f(2,5)
f(1,5) = f(2,5)
So Correct Options = 0 + 2f(2,2) + 5f(2,3) + 9f(2,4) + 9f(2,5)
Now f(2,2) = 0
And the points (2,3), (2,4) and (2,5) can be treated as normal points since there is no restriction on any three of them as y=x line doesn't interfere for any of these points now.
So,
f(2,3) = 3C1 = 3
f(2,4) = 2C1 = 2
f(2,5) = 1C1 = 1
So, Correct options = 0 + 5*3 + 9*2 + 14*1
= 47
The answer to second part is 28.
ReplyDeleteE(m,n)= no. of ways of reaching coordinate m,n.
E(m,n) =E(m-1,n)+E(m,n-1).
base cases
E(x,0)=1;
E(x,x)=E(x,x-1);
Running time using dynamic programming is O(mn).
To reach the destination let us consider our journey along y direction. since it is a n*m field we could divide the y journey into a max of n+1 different steps y1,y2,y3...
ReplyDeleteand proceed as follows:
Answer to the first part is number of solutions to the equation y1+y2+y3.....yn+1=m with the condition that yi>=0. It is the coefficient x^m in (1+x+x^2....x^m)^n+1 which is (n+m)Cm.
in part 2: n>m
for the second part there are extra constraints on y1 to ym such that y1<=0 y2<=1 y3<=2.....ym<=m-1.
number of ways is the coefficent of x^m in 1*(1+x)*(1+x+x^2)....*(1+x+x^2+....x^(m-1))*((1+x+x^2..x^m)^(n-m+1)).
I am unable to figure out how to evaluate the coefficient in the above expression by using binomial expansions( infinite series formulae) .
If the above thing works we could have a general formula.
First Part is trivial. Ans : (m+n)Cm
ReplyDeleteSecond part is tricky. Use principal of Reflection to solve this. Ans : (m+n)Cm - (m+n)C(m-1)
Solution :
Use following graph to visualise this. On the Xnew = X+Y, and Ynew as X-Y.
Every step in new axis is 45 degree upward or 45 degree downward. And constraint will be that no point should touch Y=-1 line. Aim is to find #paths from (0,0) to (n+m, n-m).
Take the reflection of (0,0) in Y=-1 line i.e. (0,-2).
So, #path which touches Y=-1 line will be equivalent to #paths from (0,-2) to (n+m, n-m) (Principle of Reflection)and that will be (m+n)C(m-1).
Assumption made in my previous post was that we can allow points on the diagonal but not above that. If we don't even allow points on diagonal then we can start from (1,1) (in new axis) to get total #paths and from (1,-1) to wrong paths.(i.e. taking reflection along line Y=0).
ReplyDeleteSo, solution in this case will be (n+m-1)Cm - (n+m-1)C(m-1).
Consider any path from (0,0) to (m,m) which does not go above diagonal. If we add (n-m) horizontal step to this path it will still gives us a path from (0,0) to (n,m) which does not go above diagonal. Conversely, any such path can be represented as a path from (0,0) to (m,m) with (n-m) horizontal steps added to it. Now number of ways in which you can add (n-m) horizontal steps to a path having m horizontal steps and m vertical steps is nCm. We also know that paths from (0,0) to (m,m) which does not go above diagonal are given by well known Catalan number C_m. So total number of paths = nCm * C_m. So I think the answer should be: (nCm)*(2mCm) /(m+1)
ReplyDeleteThis idea is wrong mate, as clearly, adding n-m horizontal edges can make some paths that were originally going above the diagonal satisfy the condition now....
Deletesecond has a classic solution using bijection principle..!! read it in a book
ReplyDelete1. C(8,3)
ReplyDelete2. C(8,3) - C(8,2).
Explanations for 2: flip every step after the first "up" arrow that goes across the diagonal, you will get a bijection to another problem where you will have a 6*2 board, whose solution is C(8,2). Subtract them out is the solution to the original problem.
Details please see: http://en.wikipedia.org/wiki/Catalan_number#Second_proof
ans=56,
ReplyDeletein quardinate geometry for (5,3) total moves in x direction is 5 and in y direction 3.
total path is =[ factorial(5+3) ] / [ fac(5) * fac(3) ] = 56
for the first part of question -
ReplyDeleteif you want to go from (0,0) to (n,m) [n horizontal moves and m vertical moves]
we can arrange n 'H' and m 'V' by ((n+m)! / (n)! * (m)!)
here n = 5 and m = 3 so ans is 8C3 = 56
Second part-
We don't want to cross diagonal (0,0) to (3,3) here. In this case we count the faulty cases, where we are crossing that diagonal and remove this from total ((n+m)Cm) to get required answer.
to get faulty cases , we can observe whenever we cross (0,0)->(3,3) diagonal , path will touch or cross diagonal (-1,0)->(2,3).
Now take a part of path ((0,0) to first cut on the diagonal(-1,0)->(2,3)) and reflect it with respect to diagonal (-1,0)->(2,3) . by doing all this, we can observe point (0,0) will map to (-1,-1) and each path from (0,0) to (5,3) will have a corresponding path from (-1,-1) to (5,3)
so faulty cases = number of paths from (-1,-1) to (5,3) is 10C4 (ANSWER)
Please ignore my previous answer.
ReplyDeletefor the first part of question -
if you want to go from (0,0) to (n,m) [n horizontal moves and m vertical moves]
we can arrange n 'H' and m 'V' by ((n+m)! / (n)! * (m)!)
here n = 5 and m = 3 so ans is 8C3 = 56
Second part-
We don't want to cross diagonal (0,0) to (3,3) here. In this case we count the faulty cases, where we are crossing that diagonal and remove this from total ((n+m)Cm) to get required answer.
to get faulty cases , we can observe whenever we cross (0,0)->(3,3) diagonal , path will touch or cross diagonal (-1,0)->(2,3).
Now take a part of path ((0,0) to first cut on the diagonal(-1,0)->(2,3)) and reflect it with respect to diagonal (-1,0)->(2,3) . by doing all this, we can observe point (0,0) will map to (-1,1) and each path from (0,0) to (5,3) will have a corresponding path from (-1,1) to (5,3)
so faulty cases = number of paths from (-1,1) to (5,3) is 8C2
ANSWER = total - faulty = 8C3 - 8C2
By this approach you can find number of paths even for any kind of restricting path like same problem with barrier (0,0) -> (2,2) instead of (0,0) -> (3,3)
Part 1 correct. For part 2, look at Aashay's reflection-principle comments at the end of the thread: C(n+m, m) - C(n+m, m-
ReplyDeleteCorrect but exponential - the recursion recomputes subproblems. Either memoize it (O(nm)) or just note the closed form: ev
ReplyDeleteYes - the Catalan reflection proof generalizes directly: paths from (0,0) to (n,m) staying weakly below the diagonal (n >=
ReplyDeletePart 1 right. Part 2 is 28, not 27: by reflection, bad paths (touching y = x+1) biject to all paths to (m-1, n+1)... count
ReplyDeleteYour part 1 recursion is the hypergeometric-sum form of C(m+n, n) - fine. For part 2, the corrected final answer (28) is r
ReplyDelete47 is not right - the answer is 28 (reflection principle: 56 - 28). Check your boundary conditions: states on the diagonal
ReplyDeleteCorrect - that boundary rule E(x,x) = E(x,x-1) is exactly "never step above the diagonal," and 28 it is. The closed
ReplyDeleteLegitimate approach - the truncated-geometric product encodes exactly the "cumulative vertical steps never exceed h
ReplyDeleteTextbook-perfect - rotate 45 degrees, reflect in y = -1, bad paths biject to paths from (0,-2), count C(m+n, m-1).
ReplyDeleteOvercounts - different insertion choices produce the SAME final path (a path with several up-runs can arise from ma
ReplyDeleteYes - the reflection/bijection argument; see Aashay's two comments for it done carefully. (rep
ReplyDeleteCorrect - that is the reflection principle, and the Wikipedia "second proof" of the Catalan formula is the right re
ReplyDeleteCorrect for part 1. (replied using AI)
ReplyDelete(Second version noted.) Correct both parts - your shifted-diagonal reflection is the same bijection as Aashay's: b
ReplyDelete