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?

  • $\begingroup$ 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. $\endgroup$ – N. Shales Apr 26 '17 at 18:34
  • 2
    $\begingroup$ 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$. $\endgroup$ – Artimis Fowl Apr 26 '17 at 18:34
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ As the question stands, there are an infinite number of places to pick a crossover point. $\endgroup$ – Arthur Apr 26 '17 at 18:36
  • 1
    $\begingroup$ @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. $\endgroup$ – Marcus Andrews Apr 26 '17 at 18:37
  • $\begingroup$ Normally, yes. But not necessarily. What if he instead of the rectangle were limited to paths of some specified length? Whatever limitation the original problem author intended, it got lost when transcribing it to this site, and you have no way of knowing what that limitation is until we get some form of confirmation. $\endgroup$ – Arthur Apr 26 '17 at 18:39
  • 1
    $\begingroup$ @Arthur If that were the case, his book's answer would likely not be $(n+1)^m$. $\endgroup$ – Marcus Andrews Apr 26 '17 at 18:50
  • 1
    $\begingroup$ @Arthur Good idea - disclaimer added $\endgroup$ – Marcus Andrews Apr 26 '17 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.