A Catalan-like counting of walks of length $n$ on $\mathbb{Z}$

Question

I would like to count the number of walks of length $n$ on $\mathbb{Z}$ starting at $0$, where in each step you move either one left or one right, such that you never land on a negative integer (i.e. you can't go left more times than you go right at on any given step). Notice that I don't require the walk to terminate at $0$, just at a non-negative integer. Clearly, if we denote $$C_{s,t}=\frac{s-t+1}{s+1}\binom{s+t}{t}$$ then $C_{s,t}$ is the number of such walks with $n=s+t$ in which there are exactly $s$ steps right (and hence $t$ steps left). The the number I look for will be $$\sum_{t=0}^{\left\lfloor\frac n2\right\rfloor}C_{n-t,t}$$ I found in this forum that this number is also equal to $$\binom{n}{\left\lfloor\frac n2\right\rfloor}$$ My question is: why is it true - it is mentioned there that there exists a bijection between my desired walks and walks of length $n$ with exactly $\left\lfloor\frac n2\right\rfloor$ steps left, but no restriction on staying non-negative. Can anyone show me an explicit bijection between the two or an another way to see this equality?

Answer 1

There is a simple bijection that maps such walks to unconstrained walks that end at $0$ or $1$ (depending on the parity of $n$). First mark in the original (constrained) walk the positive (rightward) steps that are the last ones to leave from a particular element of $\Bbb Z$; if the path ends in $k$ then there are precisely $k$ such steps. Now reverse the direction of the first $\lfloor\frac k2\rfloor$ marked steps, which will move the end point back $2\lfloor\frac k2\rfloor$ units so that it becomes $k\bmod 2=n\bmod 2\in\{0,1\}$.

The reason this is a reversible operation is that after the modification, the step that have been reversed can be recognised at the first steps that reach the point $-i$, for $i=1,2,\ldots,\lfloor\frac k2\rfloor$, and that $-\lfloor\frac k2\rfloor$ is the most negative value reached by the modified walk.