Number of routes Suppose there is an ant on the point $(0,0)$ that can move one step right
($(x,y)\mapsto(x+1, y)$), one step up ($(x,y)\mapsto(x, y+1)$) or one step diagnolly ($(x,y)\mapsto(x+1, y+1)$). How many ways are there for the ant to travel from $(0, 0)$ to $(m, n)$?
The answer should be $\sum_{k=0}^n \binom{m}{k} \binom{n+k}{m}$.
My attempt: let $k$ be the numbers of diagnol steps. So we have $m-k$ right steps and $n-k$ up steps, and total of $n+m-k$ steps.
There are  $\binom{n+m-k}{k, n-k, m-k}$ ways to choose the order of those steps.
So the total should be $\sum_{k=0}^n \binom{n+m-k}{k, n-k, m-k}$ but I can't derive the right answer from this expression. 
Am I right? If so, how do I continue?
 A: Just by definition of binomial and multinomial coefficients, and a little "trick"
$$
\begin{gathered}
  \left( \begin{gathered}
  n + m - k \\ 
  m - k,\;n - k,\;k \\ 
\end{gathered}  \right) = \frac{{\left( {n + m - k} \right)!}}
{{\left( {m - k} \right)!\;\left( {n - k} \right)!\;k!}} =  \hfill \\
   = \left[ \begin{gathered}
  \frac{{m!}}
{{m!}}\frac{{\quad \left( {n + m - k} \right)!}}
{{\left( {m - k} \right)!\;\left( {n - k} \right)!\;k!}} = \frac{{m!}}
{{\left( {m - k} \right)!k!}}\frac{{\quad \left( {n + m - k} \right)!}}
{{\;\left( {n - k} \right)!\;m!}} = \left( \begin{gathered}
  m \\ 
  k \\ 
\end{gathered}  \right)\left( \begin{gathered}
  n + m - k \\ 
  m \\ 
\end{gathered}  \right) \hfill \\
  \frac{{n!}}
{{n!}}\frac{{\quad \left( {n + m - k} \right)!}}
{{\left( {m - k} \right)!\;\left( {n - k} \right)!\;k!}} = \frac{{n!}}
{{\left( {n - k} \right)!\;k!}}\frac{{\quad \left( {n + m - k} \right)!}}
{{n!\left( {m - k} \right)!\;}} = \left( \begin{gathered}
  n \\ 
  k \\ 
\end{gathered}  \right)\left( \begin{gathered}
  n + m - k \\ 
  n \\ 
\end{gathered}  \right) \hfill \\ 
\end{gathered}  \right. \hfill \\ 
\end{gathered} 
$$
Now, the sum in $k$ shall go from $0$ to the the lesser between $n$ and $m$.
Supposing this is $m$,  taking the first expression
$$
\sum\limits_{0\, \leqslant \,k\, \leqslant \,\min (n,m)} {\left( \begin{gathered}
  m \\ 
  k \\ 
\end{gathered}  \right)\left( \begin{gathered}
  n + m - k \\ 
  m \\ 
\end{gathered}  \right)} \quad  \Rightarrow m \leqslant n \Rightarrow \quad \sum\limits_{0\, \leqslant \,k\, \leqslant \,m} {\left( \begin{gathered}
  m \\ 
  m - k \\ 
\end{gathered}  \right)\left( \begin{gathered}
  n + m - k \\ 
  m \\ 
\end{gathered}  \right)}  = \sum\limits_{0\, \leqslant \,k\, \leqslant \,m} {\left( \begin{gathered}
  m \\ 
  k \\ 
\end{gathered}  \right)\left( \begin{gathered}
  n + k \\ 
  m \\ 
\end{gathered}  \right)} 
$$
So, the expression you gave as result shall have $m$, not $n$, as the upper limit of the sum (unless it is clear that it is actually, inherently, stopped at $m$ by the binomial)
A: Without loss of generality, but for definiteness, assume $m \geq n$ and, accordingly, write $m = n + n'$, where $n' \geq 0$. This decomposition shows that every path must contain at least $n'$ horizontal moves.
So, the computation should be:
[# of ways of choosing $n'$ out of $n$ places to put a horizontal move] * [# of ways of getting from $(0,0)$ to $(n,n)$].
To find the latter quantity in []'s, note that, in a path from $(0,0)$ to $(n,n)$, for each horizontal move there must be one vertical move.  So, we are looking for the number of partitions
$n = 2l + d$, where $l$ is the number of horizontal moves (and there would be as many vertical ones), and $d$ is the number of diagonal moves.
