Consider $m \times n$ grid. a path from left corner $(0,0)$ to the grid point $(m,n)$ can use three kinds of steps namely,
Derive an expression for $D_{m,n}$, the number of such distinct paths.
HINT:
Let $f(m,n)$ be the desired function.
Calling horizontal movement as $E$, vertical movement as $N$ and diagonal $NE$ movement as $D$,
it is obvious that for a $1 \times 1$ grid, there are $3$ paths, $N, E, D$
If you work out for a $2\times 2$ grid, you should be able to count $13$ paths. Taking $f(0,0) = 1$, can you find a recursive relationship for $f(2,2)$ and generalize ?
$f(m,n) = f(m-1,n) + f(m,n-1) + f(m-1,n-1).$
There is also a closed form possible. Can you think how ?
Suppose there were $k$ diagonal steps, then there must necessarily be $m-k$ horizontal steps and $(n-k)$ vertical steps, which can be performed in any order, thus $$f(m,n) = \binom{m+n-k}{k,m-k,n-k}$$ and you can sum up from $k=0$ to minimum of $m,n$
Look up Delannoy numbers
