Number of routes

Question

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?

Answer 1

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)

Answer 2

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.