1. ## Probability Grid

Hi, I've got a problem with a 4x3 grid. I can move right and vertically only. I need to know how many different ways I can go from (0,0) to (4,3). I know how to do it if only going right and up. But in this problem I can go right, up, or down.

Thanks!

Kelli

2. I'd say infinitely many since it is possible to go up-down-up-down-up-down-...

3. Originally Posted by Laurent
I'd say infinitely many since it is possible to go up-down-up-down-up-down-...
what if you had to alternate vertical and horizontal movements? and of course, you can only move to the right, so you can't go around the same square infinitely, for instance

4. Yeah, I'm having trouble understanding what the question is saying. All it says is right and vertical. How about we pretend you can't backtrack. Could anyone figure that out? I'm pretty sure vertical means up and down because another part of the question asks how many possible paths are there if you must pass through points (2,3) and (3,2). Thanks everyone!

Kelli

5. In the usual ‘city-block’ problem we say that one can move east or north.
In the problem, we would move 4 blocks east and 3 blocks north.
So how many ways can we arrange the string “EEEENNN”?

Now in the present problem let’s do add no backtracks.
One possibility is 4 E’s, 1 S and 4 N’s: ex. ENESENNEN.
But note there are restrictions. No string can begin or end with S.
Moreover, S cannot appear next to an N.

The most extreme case: NNNESSSENNNESSSENNN.

The job is to count all these possiblites.

6. Originally Posted by Plato
Now in the present problem let’s do add no backtracks.
One possibility is 4 E’s, 1 S and 4 N’s: ex. ENESENNEN.
But note there are restrictions. No string can begin or end with S.
Moreover, S cannot appear next to an N.

The most extreme case: NNNESSSENNNESSSENNN.

The job is to count all these possiblites.
Here's another way to code the problem. In fact, it is equivalent (under the no-backtrack condition) to be given the whole trajectory (sequence of N,S,E) or only the arrival points in each new column.
The walk starts at $\displaystyle (0,n_0)$ where $\displaystyle n_0=0$. It goes up a few steps, and then to $\displaystyle (1,n_1)$. From there, it goes either up or down (but not both) and then to $\displaystyle (2,n_2)$. And so on, until $\displaystyle (5,n_5)$ where $\displaystyle n_5=3$ (I add a column for the sake of simplifying the presentation, but the walk doesn't go up/down in this new column so it doesn't affect the computation). If you know the $\displaystyle n_i$'s, you can deduce the trajectory.
The nice thing is: there is no constraint on the $\displaystyle n_i$'s, except that they belong to $\displaystyle \{0,1,2,3\}$ and that $\displaystyle n_0$ and $\displaystyle n_5$ are fixed.
As a consequence, there are exactly $\displaystyle 4^4$ paths satisfying the asumptions: number of choices of $\displaystyle n_1,n_2,n_3,n_4$. The same reasoning works for any number instead of 4 or 3.

7. thank you so much!

8. How would this change if I had to go through both (2,3) and (3,2) on the way up to (4,3)?

9. Originally Posted by kelli_rie
How would this change if I had to go through both (2,3) and (3,2) on the way up to (4,3)?
Then $\displaystyle n_2$ and $\displaystyle n_3$ would be fixed, so it remains to choose $\displaystyle n_1$ and $\displaystyle n_4$: $\displaystyle 4^2=16$ possible paths.

10. Ah ha! Thanks, now I see exactly what you're doing!

11. Originally Posted by Laurent
Then $\displaystyle n_2$ and $\displaystyle n_3$ would be fixed, so it remains to choose $\displaystyle n_1$ and $\displaystyle n_4$: $\displaystyle 4^2=16$ possible paths.
In fact I was wrong... "The walks goes through (3,2) and (2,3)" doesn't mean that $\displaystyle n_3=2$ and $\displaystyle n_2=3$: this is only one possibility.
Since 3 is the top row, we notice that the possibilities are:
- $\displaystyle n_2\leq 2$ and $\displaystyle n_3=3$ (because the walk goes through (2,3)) and $\displaystyle n_4$ must be $\displaystyle \leq 2$ to go through (3,2) and avoid backtracking;
- $\displaystyle n_2=3$ and $\displaystyle n_3=3$ and $\displaystyle n_4\leq 2$;
- $\displaystyle n_2=3$ and $\displaystyle n_3=2$ and $\displaystyle n_4$ is anything.
- $\displaystyle n_2=3$ and $\displaystyle n_3\leq 1$ and $\displaystyle n_4\geq2$.
So that there are $\displaystyle 3\cdot 1\cdot 3 + 1\cdot 1\cdot 3 + 1\cdot 1\cdot 4+1\cdot1\cdot 2=18$ possibilities to choose $\displaystyle (n_2,n_3,n_4)$. And there are $\displaystyle 4$ choices for $\displaystyle n_1$, so that the final answer is $\displaystyle 18\cdot 4=72$.