I'm trying to count the number of paths from $(0,0)$ to $(n,k)$, ($n,k> 0$) when only diagonal and vertical moves are allowed. I know that if only horizontal and vertical moves are allowed than its $n+k \choose n$, but can it help solving the question?
edit: by diagonal moves I mean moves from $(x,y)$ to $(x+1,y+1)$.
On
Let's examine a few cases to clarify.( Hereafter $D$ means diagonally right step and $U$ means vertically up step.)
It is also clearly visible that $n\le k$ to reach (n, k) with given restrictions.
Case 1) When $n\neq k$
Consider for example $n=2$ and $k=3$ we can simply write out the ways to reach $(2,3)$ as $DUD,DDU,UDD$
Lets consider $n=2$ and $k=4$. Here too we simply write out the ways as $DUDU, DDUU, DUUD, UUDD,UDUD,UDDU$
Lets consider $n=1$ and $k=3$ . Here the ways are $DUU, UDU, UUD$
Hence after looking at some examples we simply that for $n\neq k$ the number of paths are $\binom {k}{n}$
Case 2) $n=q$
Using basic intuition we simply have only one way to go to the point $(n, n) $ with given restrictions which is by taking diagonal steps at every point. Hence we get $1=\binom {n}{n}$
Hence for generalized formula to reach $(n, k) $ where $n\le k$ with given restrictions is $\binom {k}{n}$
This problem is quite simple. Note that reaching from $(0,0)$ to $(n,k)$ requires $n$ horizontal steps and $k$ vertical steps.
But, regardless of whether you take a vertical or a diagonal step, the $y$ coordinate of your position always increases by $1$. Therefore, it will take you exactly $k$ steps to reach your position.
But then, you can decide, out of these $k$ steps, which $n$ of these should be diagonal, and which should be only vertical.
Therefore, the following statement is true:
Therefore, the answer is just $\binom kn$(exclaim).
Note : a similar argument applies for the only "horizontal and vertical steps allowed" problem, since there you must reach your target in $n+k$ steps, out which you can choose the $n$ horizontal, or $k$ vertical ones, giving the answer $\binom{n+k}{n} = \binom{n+k}{k}$.