1

Suppose we start at the origin and we're interested in how many paths there are such that we only return back to the origin after m steps and not before. where m is some even integer.

Each step can be up one unit or down one unit. Suppose for simplicity we can only have positive values. Then if m=8, one path could be (1,2,3,2,3,2,1,0) another could be (1,2,3,4,3,2,1,0).

I dont see how to remove paths that return to the origin too soon from my count of possible paths.

JJ chips
  • 53

2 Answers2

2

You can use slightly modified Catalan Numbers. Note that the first move has to be $0 \to 1$, while the last one has to be $1 \to 0$. Then we need to determine the other $m-2$ moves, s.t. we never go below $1$ and starting at $1$ we return to $1$. This number is exactly the $(m-2)$-th Catalan Number. So the wanted number is:

$$C_{m-2} = \frac1{m-1}\binom{2m-4}{m-2}$$

Stefan4024
  • 35,843
  • But since we require the sequence to not revert to the origin before m steps, the second move must be 1->2 and the second last must be 2->1. So then there are m-4 other moves to determine? – JJ chips May 19 '18 at 19:12
  • @JJchips Actually the Catalan Numbers take care of that. The Catalan Numbers count the number of such ways that if we start on the $x$-axis we never go below it, but being on it multiple times during the path is allowed. That's why I used the first and the last step arguement to address that problem. – Stefan4024 May 19 '18 at 19:14
  • Could you explain why it is the m-2th catalan number? – JJ chips May 19 '18 at 19:18
  • @JJchips Because we need $m-2$ steps to go from $1$ back to $1$. If we want to make it from $0$ back to $0$ in $m$ steps. – Stefan4024 May 19 '18 at 19:20
  • The first move could also be $0 \to -1$, in which case the last move has to be $-1 \to 0$, with $m - 2$ moves that never go above $-1$. Therefore, your answer should be doubled. – N. F. Taussig May 20 '18 at 10:37
  • @N.F.Taussig But the OP says: "Suppose for simplicity we can only have positive values". I was answering that question. – Stefan4024 May 20 '18 at 10:38
  • @Stefan4024 Sorry, I missed that. – N. F. Taussig May 20 '18 at 10:39
1

Hint: Consider $(u+d)^{2k}$ and try to find the coefficient of $u^kd^k$, which will correspond to the number of ways to obtain a path with $k$ total steps up and $k$ total steps down, so that you have indeed returned to the origin.

Andres Mejia
  • 20,977
  • see here for the case of lattices and see if you can adapt this approach – Andres Mejia May 19 '18 at 19:06
  • But what if the downs come all at once and we pass the origin before m steps is up? Ie one combination could be (u,d,d,u), which would violate the "must return to origin only at m steps and not before". Also if d came first recall we require that the sequence stay positive.Don't we need to done how not count those paths? – JJ chips May 19 '18 at 19:09