How many ways can a moving object reach the point $(m,n)$ with exactly $k$ changes in direction? Assume that a moving object like $O$ is at the point $(0,0)$. ( We are talking in a $2$D-space )
In each step, $O$ can move from $(x,y)$ to $(x,y+1)$ or $(x+1,y)$.  ( So, $O$ can either go right or go up. )
Question :
How many ways can $O$ reach the point $(m,n)$ with exactly $k$ changes in direction?  
Note 1 ( I know its simple but anyway ... ) :    
By "change in direction", I mean this :
Assume that $O$ is going right and the next step is to go up.  When $O$ has taken the next step, we say that $O$ has changed its direction.  
Note 2 :  I think it's like that sum of  $k+1$ numbers are equal to $m+n$ but i'm not sure.   
Note 3 ( another way of looking at the question ) :  Assume that each move to right is a triangle and each move to up is a rectangle. We have $m$ triangles, $n$ rectangles and $k$ plus signs. We want to arrange these things such that no plus signs are next to each other. Also, if two shapes ( triangle and rectangle ) are next to each other, then these two shapes are the same. I mean, no rectangle and triangle are next to each other. How many ways can we arrange these rectangles, triangles and plus signs ?
Thanks in advance.
 A: To get to $\langle m,n\rangle$, you must take $m$ right-steps and $n$ up-steps. Letting $0$ represent a right-step and $1$ an up-step, we can code a path as a sequence of $m$ zeroes and $n$ ones. There is one change of direction every time a $0$ is followed by a $1$ or vice versa. Thus, if we divide the $(m+n)$-bit string into blocks of consecutive zeroes and ones, there is one change of direction between each pair of adjacent blocks. If we want $k$ changes of direction, we need to have $k+1$ blocks. The question then becomes:

How many $(m+n)$-bit strings are there with $m$ zeroes, $n$ ones, and $k+1$ blocks?

There are two possibilities: we can start with a block of zeroes or with a block of ones. Suppose that we start with a block of zeroes. If $k=2\ell$, we’ll have $\ell+1$ blocks of zeroes and $\ell$ blocks of ones, and if $k=2\ell+1$, we’ll have $\ell+1$ blocks of each.
The number of ways to distribute $m$ zeroes amongst $\ell+1$ blocks is given by a standard stars and bars calculation as $\binom{m-1}{\ell}$. The number of ways to distribute $n$ ones amongst $\ell$ blocks is $\binom{n-1}{\ell-1}$, and the number of ways to distribute them amongst $\ell+1$ blocks is $\binom{n-1}\ell$. Thus, if $k=2\ell$ there are
$$\binom{m-1}\ell\binom{n-1}{\ell-1}$$
acceptable strings starting with a zero block, and if $k=2\ell+1$ there are
$$\binom{m-1}\ell\binom{n-1}\ell$$
of them.
The calculation of the number of acceptable strings beginning with a one block is entirely similar; once you’ve make it, it’s just a matter of adding the results.
A: For $k=2s-1$, you are asking for the number of positive integer sequences:
$$(a_1,b_1,a_2,b_2,\dots,a_s,b_s)$$ such that $a_i,b_i>0$ with $\sum a_i=m$ and $\sum b_i=n$, times $2$ (because one directions starts first.)
This is, by the usual "stars and bars" argument, equal to $2\binom{m-1}{s-1}\binom{n-1}{s-1}$.
For $k=2s$, you are seeking sequences $(a_1,b_1,\dots,a_s,b_s,a_{s+1})$ where $\sum a_i = m, \sum b_i=n$ plus sequences $(b_1,a_1,\dots,b_s,a_s,b_{s+1})$, where $\sum a_i=m,\sum b_i=n$. This amounts to:
$$\binom{m-1}{s}\binom{n-1}{s-1} + \binom{m-1}{s-1}\binom{n-1}{s}$$
The general formula can be written as:
$$\binom{m-1}{\left\lceil\frac{k-1}{2}\right\rceil}\binom{m-1}{\left\lfloor\frac{k-1}{2}\right\rfloor}+\binom{m-1}{\left\lfloor\frac{k-1}{2}\right\rfloor}\binom{m-1}{\left\lceil\frac{k-1}{2}\right\rceil}$$
