To compute total possible paths in a rectangular grid if steps to the right, up, or diagonally up are allowed

Question

How should I answer this-"Compute the total number of possible paths from $(0,0)$ to $(7,9)$ if the steps R (to the right) and U (up) are allowed, along with the diagonal step $D:(x,y) \to (x +1,y+ 1)$."

Answer 1

The answer to this problem belongs to a family of numbers are known as the Delannoy numbers. You can arrive at this equation by solving the corresponding recurrence relation which represents the possible moves at each step:

$D_{m,n} = D_{m-1,n} + D_{m-1,n-1} + D_{m,n-1}$

For m = 7 and n = 9 the answer comes out to:

$$\sum_{k=0}^{min(7,9)} {7 \choose k} {9 \choose k} 2^k = 224143$$

Answer 2

if you have $k$ diagonals you must be making $(9-k)$ up moves and $(7-k)$ right moves and you will be making $(16-k)$ moves in total

The number of ways you can do this is $$N(k) =\binom{16-k}k \binom {16-2k}{7-k}$$

To get your final answer, sum $N(k)$ from 0 to 7.

Wolfram Alpha gives 224143 for the sum, in agreement with the first answer.