# How many ways are there to go from the point $(0,0)$ to $(m,n)$ using,right up and down moves that we don't pass a point more than once?

How many ways are there to go from the point $(0,0)$ to $(m,n)$ using,right up and down moves that we don't pass a point more than once?

I tried using to calculate every case(depending on the down moves) then maybe the identity $\sum\limits_{r=0}^m n^r \binom{m}{r}=(n+1)^m$ will work.(because the answer in the book is $(n+1)^m$).But it didn't work.Any hints?

• You might need to be a bit more specific about what you mean by "...right up and down..." If these moves are all possible then there are an infinite number of n or u shaped paths. – N. Shales Apr 26 '17 at 18:34
• There's an error here methinks - for every $k \in \mathbb{Z}$, what stops me from going down $k$ steps, right $m$ steps, and up $k + n$ steps. This gives at least one path for every $k$, giving countably infinite paths (much larger than $(n+1)^m$. – Artimis Fowl Apr 26 '17 at 18:34
• Maybe you want us to stay in the rectangle defined by $(0,0), (m,0), (0,n), (m,n)$? In that case, the answer below is the correct one. Maybe you want paths of a set length? In that case, it might be possible to adapt the proof for the number of paths using only up or right moves. – Arthur Apr 26 '17 at 18:36

Under the assumption that movement is only allowed in the grid formed by corner points $(0,0), (m, 0), (0, n), (m,n)$:
For each column, there are $n+1$ ways to pick where the horizontal movement occurs. After placing the horizontal movements for each column, there's only one way to connect them all (and these connections are done entirely in terms of up/down movements that do not revisit any position more than once).
Over all $m$ columns, that's $(n+1)^m$ paths in total, which matches the answer in your book.
• @Arthur Normally for path problems like these, it's a grid bounded from $(0,0)$ to $(m,n)$ for positive integers $m,n$. But yes, the OP should probably mention this. – Marcus Andrews Apr 26 '17 at 18:37
• @Arthur If that were the case, his book's answer would likely not be $(n+1)^m$. – Marcus Andrews Apr 26 '17 at 18:50