How many ways are there to walk from A to B by only moving rightward or upward?
I believe I remember how to do this, but.......someone will have to check me on it !!!.....
In any m x n grid, there are C ( m + n , m) paths to the right and upward, assuming that we start at the lower left vertex of the grid and end up at the top right vertex.... or, alternatively, C ( m + n, n) paths......these should work out the same
So.....the first grid is a 2 x 3 grid, which means there are C ( 2 + 3, 2) = C ( 5, 2) = 10 paths from the lower left starting point and moving to the right and up to the intersection of the two grids .......this would be the same as C ( 2 + 3, 3) = C (5, 3) = 10
The next grid is a 4 x 3 grid.....which implies that there are C(4 + 3 , 3) = C(7, 3) = 35 paths which we can take [ moving in the specified manner ] from the intersection of the two grids to the top right vertex of the upper grid
So....the total paths become C(5,2) * C (7,3) = 10 * 35 = 350 distinct paths moving to the right and upward from the lower left vertex of the bottom grid to the upper left vertex of the top grid.
Here's a good website that presents the logic behind this........http://betterexplained.com/articles/navigate-a-grid-using-combinations-and-permutations/
\( nodes: \begin{array}{ccccccccccc} & & & & 27 & \rightarrow & 28 & \rightarrow & 29 & \rightarrow & 30 & \rightarrow & B(31)\\ & & & & \uparrow & & \uparrow & & \uparrow & & \uparrow & & \uparrow \\ & & & & 22 & \rightarrow & 23 & \rightarrow & 24 & \rightarrow & 25 & \rightarrow & 26 \\ & & & & \uparrow & & \uparrow & & \uparrow & & \uparrow & & \uparrow \\ & & & & 17 & \rightarrow & 18 & \rightarrow & 19 & \rightarrow & 20 & \rightarrow & 21 \\ & & & & \uparrow & & \uparrow & & \uparrow & & \uparrow & & \uparrow \\ 10 & \rightarrow & 11 &\rightarrow & 12 & \rightarrow & 13 & \rightarrow & 14 & \rightarrow & 15 & \rightarrow & 16 \\ \uparrow & & \uparrow & & \uparrow \\ 7 & \rightarrow & 8 &\rightarrow & 9 \\ \uparrow & & \uparrow & & \uparrow \\ 4 & \rightarrow & 5 &\rightarrow & 6 \\ \uparrow & & \uparrow & & \uparrow \\ A(1)& \rightarrow & 2 &\rightarrow & 3 \\ \end{array} \)
\(\small{\text{ entrys $ \qquad 1 = $ one way $\quad 0 = $no way from node x to node y}}\)
Matrix A =
Marix A*A =
...
\(\text{Matrix }\ A^{12} =A\cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A = \)
\( A^{12} : \text{ Matrix element[A][B] } =350 \quad\text{ (12-station-way)}\)