1
$\begingroup$

Suppose a person is walking on an n x n grid, starting from the lower, left corner (0,0) walking up to the upper-right corner (n-1, n-1). How many different paths are possible for the person to reach the destination?

Tried to enumerate all the possible paths through order n to n2.

$\endgroup$
3
  • $\begingroup$ what is the result of your trials? $\endgroup$ – Salomo Apr 3 '15 at 20:32
  • 3
    $\begingroup$ There needs to be additional conditions, else you might walk from (0,0) to (1,0) and back again a million times. $\endgroup$ – vadim123 Apr 3 '15 at 20:34
  • $\begingroup$ @anasanzari There is a closed form solution for the walks of length $k$ (a sum) that doesn't involve matrix multiplication. $\endgroup$ – muaddib Jun 8 '15 at 5:21
1
$\begingroup$

One (not necessarily easy) way to approach this is to build a graph whose vertices are the intersections of the grid and two vertices are adjacent if they are "next to each other" on the grid (one step north, south, east, or west).

Let $A$ be the adjacency matrix of this graph. Then each entry $A^{k}$ (call it $a_{ij}$) tells you the number of walks of length $k$ beginning at vertex $i$ ending at vertex $j$. Then, if you want to know how many walks there are from $(0,0)$ to $(n-1,n-1)$ (of length at most $N$), and for convenience I'll call the vertex corresponding to $(0, 0)$ vertex 1 and the vertex corresponding to $(n-1, n-1)$ vertex $n^2$, we have that the number of walks is the $1, n^2$ entry of the matrix:

$$\sum_{k=1}^{N} A^{k}$$

If you have a reasonably small grid, and your choice of $N$ is reasonably small, then this can be easily calculated with a computer. It may be the case that the graph corresponding to a grid has a nice adjacency matrix and you can say something in general, but I don't immediately see it.

$\endgroup$
0
$\begingroup$

As @ vadim123 pointed out, the constraints are important. I am going to go ahead and assume that the constraints are that u can go only $\uparrow$ (up) and $\rightarrow$ (right) (NOTE: the simplest flavors of problems of this kind usually start with these constraints).

Now every path from $(0,0)$ to $(n-1,n-1)$ will look like a sequence of up's and down's. $$ \uparrow \rightarrow \uparrow \uparrow \rightarrow...$$

Now the size of the sequence is of course $2n$, because in every direction (up or right), you'd have to move $n$ steps.

Giving a up movement the symbol $0$ and right, the symbol $1$, this is just a sequence of $n$ $0$'s and $n$ $1$'s.

So the number of such sequences are: $$ \frac{(2n)!}{n! n!}$$

$\endgroup$
0
$\begingroup$

I've heard this problem in my Textbook a hundred times before. The constraints are usually that the user can only move up or right, and cannot go outside of the nxn grid. So basically it is a rearrangement of (right,right,up,right,up) (there are m+n of them). The number of ways to get from point (x1,y1) to (x2,y2) is the same as the number of rearrangements of that set of (right,up). So the real question is how can you rearrange 2n items with two unique items, where order matters? How you have to think about it is, there are 'm' slots for up (the height), and 'n' slots for right (the width). So you just have to place either (1) the m's in the right place, or (2) the n's in the right place. Let's say you choose m's. So you have (m+n) slots, ( _ , _ , _ , _ ,..., _ , _ , _) and you have to put m "up" words in there, how many ways can you do that? Think about the answer before moving on.

There are exactly m+n items to choose from, and you are choosing m of them, so the answer is C(m+n,m), the rest of the items HAVE to be "right" or else the right proportion will not be met and you won't reach your target, try it out. Now the question can be reversed, and you can choose n "up" moves instead, and the combination will be C(m+n,n), which is actually the same exact number, because of the rules of combinatorics. I'm not sure if you are including the "left" move in there, so I left that out of my answer

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.