On a 2-d grid how many different move paths can be made that begin at $(0,0)$ and end at $(x,y)$ with $x\gt 0$,$y\gt 0$. Restriction : left,down and diagonally moves aren't allowed .
Asked
Active
Viewed 249 times
0
-
So you can use only up and right moves right ?? – Jan 07 '16 at 18:32
-
Note that you will need a total of $x$ "Right" moves and a total of $y$ "Up" moves. Reword the question to instead how many sequences of R's and U's exist with $x$ R's and $y$ U's. – JMoravitz Jan 07 '16 at 18:32
1 Answers
0
At each position except the boundaries we can go two different directions: "up" and "right".
At point ($x_0,y_0$) this is $f(x_0,y_0) = f(x_0,y_0-1)+f(x_0-1,y_0)$. We also have the boundary conditions above that there is only one path along each boundary $f(k,1) = f(1,k) = 1$. We can now write a linear equation system to express $f(a,b)$ which we can solve with our favourite method.
However we have a symmetry of our problem which would allow us to simplify it a great deal if you have studied some more algebra. For simplifying using this symmetry we can take a look at this question which uses matrix exponentiation to find the numbers. This can in some sense be compared to using the numerical conjugate-gradient scheme on the above equation system - which results in investigating the Krylov Subspace $\{Iv,Av,A^2v,\cdots,A^nv\}$ which is precisely what the exponentiation above does but in a more compact form. In particular, we have the $$A = \left[\begin{array}{ccc}1&0&0\\1&1&0\\0&1&1\end{array}\right]$$ $$(A^{13})_{3,1} = 78 \hspace{0.5cm} \text{and} \hspace{0.5cm} nCr(13,2) = 78$$ Where nCr is the same function as Alex mentions in his answer. If we want to find a solution for larger grids we just need to increase the size of $A$ accordingly.
mathreadler
- 25,824