Grid Problem in Maths related to number of ways to reach from one point to another

Solution 1:

It's sometimes convenient to make a sketch of the problem. Let's consider a $4\times 4$ grid as given below.

We are looking for the number of paths from $A$ to $B$ where we are allowed to make up (U), down (D) and right (R) steps without ever passing a node more than once.

In order to go from $A$ to $B$ we have to take $4$ horizontal steps $R$. A choice of $4$ $R$ steps is given in the graphic by $a,b,c,d$.

• We observe there is one and only one path (marked in dashed green) from $A$ to $B$ which goes along $a\to b\to c\to d$.

• We are free to specify the height of $a,b,c,d$ and there are $5$ choices for each of these heights.

We conclude there are $\color{blue}{5^4=625}$ different valid paths from $A$ to $B$.

Solution 2:

Assume you are going from bottom left corner to upper right corner.

To obtain $\frac{8!}{4!^2}=\binom{8}{4}$, you can think of words on the alphabet $\{U,R\}$ (for up and right) with 4 $U$s and 4 $R$s.

For your problem with three moves $\{U, R, D\}$, you will have 4 $R$s and 4 four more $U$s than $D$s, but you also have to make sure you stay in the grid ($U$ count $\ge D$ count at each step). For a simpler approach, note that once you specify which "rung of the ladder" corresponds to each $R$ move, the path is completely determined. There are $5$ choices (correction from @MarkusScheuer) for each $R$, and these choices are independent, so there are $5^4$ paths.