If Anna goes from point A to point B, each step can only move up or move right. How many method(s) is / are there?(reference the grid below)
I’ve just recently learned permutations and combinations. Therefore, I understood how to answer problems regarding grids but only the type of questions with definite number of columns and rows. As shown in the picture above, the grids are different in size. I’m confused on how to solve this. I’d be happy if anyone could help.. Thank you.
On
This problem can be solved using dynamic programming, let's define the function $n(P_1, P_2) =$ number of ways to go from $P_1$ to $P_2$. Then we need to find $n(A,B)$, which can be computed by solving smaller subproblems (in bottom-up fashion, from left to right and from bottom to top) and combining the results of the subproblems, as shown in the below figure
Simpler such problems ask for the number of paths from $A$ to $B$ "in a $(7\times11)$-grid". Here the numbers $7$ and $11$ give the full information about the grid in question, and there is then also a simple answer in terms of a formula containing these two numbers.
But your grid is much more complicated. To describe the grid you needed an explicit figure, or the full contents of a $01$-matrix of size $5\times6$. A "formula" for the number of paths would have to operate with the full contents of this arbitrary matrix.
Instead you can think about an algorithm that solves this kind of problem for arbitrary input figures. Such an algorithm could begin with writing $1$ at $A$ and then writing recursively the sum of the "entering numbers" at each "ready" lattice point, until you are at $B$, as in Pascal's triangle.