Combinatorial problem on counting binary sequences Let $\mathcal{S}_n$ be the set of all binary sequences formed by $n$ values in $\{-1,1\}$ and let $k<n$ a given non-negative integer with the same parity of $n$. For every sequence $\mathcal{S}\ni S=\langle x_1, x_2, \ldots, x_n\rangle$, let $\sigma_j(S)$ be the sum $\Sigma_{i=1}^j x_i$ of its first $j$ elements, where $j\le n$.

Question: What is the total number of possible sequences $S\in\mathcal{S}$ such that $\sigma_n(S)=k$ and $\sigma_j(S)\le k$ for all $j\in\{1, 2, \ldots, n-1\}$?

This is part of the following problem: Flipping a biased coin landing on head with probability $1/3$, we win one dollar for each head and lose one dollar for each tail. What is the probability that when we keep flipping the coin, we gain $2$ dollars? I know that the answer is $1/4$, but the solution is a bit involved. Hence, I wanted to find a simpler solution. Summing $\binom{2n+1}n(2/3)^n(1/3)^{n+2}$ over $n$ from $0$ to $\infty$, one gets $1/2$ because subsequences leading to winning $2$ dollars are overcounted. Hence, I would like to use this approach to solve the original problem, by suitably reducing the term $\binom{2n+1}n$ to exclude the subsequences overcounted in the above summation (in the above question $k=1$, because the target is winning $2$ dollars, and the total length $n$ of the sequence $S$ is the number of coin flips minus one, because the last outcome must be head).
 A: Your problem is equivalent to the following one. Start at $\langle 0,0\rangle$ on the integer grid, and take $n$ steps, where each step is either an up-step (from $\langle a,b\rangle$ to $\langle a+1,b+1\rangle$) for a down-step (from $\langle a,b\rangle$ to $\langle a+1,b-1\rangle$). How many ways are there to reach $\langle n,k\rangle$ while staying below the line $y=k$ for the first $n-1$ steps?
For any such path the last step must be an upstep from $\langle n-1,k-1\rangle$, so we can equivalently count paths of length $n-1$ from $\langle 0,0\rangle$ to $\langle n-1,k-1\rangle$ that never rise above the line $y=k-1$. Let $\mathscr{P}$ be the set of all paths from the origin to $\langle n-1,k-1\rangle$, and let $\mathscr{P}_0$ be the subset of paths that do not rise above the line $y=k-1$.
Clearly $n-k$ must be even, so let $n=2m+k$. Clearly any path in $\mathscr{P}$ must have $m+k-1$ up-steps and $m$ downsteps, and any combination of $m+k-1$ up-steps and $m$ down-steps is a path in $\mathscr{P}$, so $|\mathscr{P}|=\binom{2m+k-1}m=\binom{n-1}m$.
Now suppose that $P\in\mathscr{P}\setminus\mathscr{P}_0$; then $P$ hits the line $y=k$, so there is a least $\ell$ such that $\langle\ell,k\rangle$ is in $P$. Reflect the part of $P$ from $\langle\ell,k\rangle$ to $\langle n-1,k-1\rangle$ in the line $y=k$, converting each down-step into an up-step and vice versa, to get a new path $P'$. That part of $P$ has a net fall of $1$ unit, so its reflection has a net rise of $1$ unit, and $P'$ therefore ends at $\langle n-1,k+1\rangle$. Thus, $P'$ has
$$\frac{(n-1)-(k+1)}2=\frac{2m-2}2=m-1$$
down-steps and $(m-1)+(k+1)=m+k$ up-steps. Clearly there are $\binom{n-1}{m-1}$ such paths. Moreover, every path from the origin to $\langle n-1,k+1\rangle$ crosses the line $y=k$ at some point, and reflecting the part of it to the right of that point in the line $y=k$ produces a path in $\mathscr{P}\setminus\mathscr{P}_0$, so $|\mathscr{P}\setminus\mathscr{P}_0|=\binom{n-1}{m-1}$.
It follows that
$$\begin{align*}
|\mathscr{P}_0|&=\binom{n-1}m-\binom{n-1}{m-1}\\
&=\frac{(n-1)!}{m!(n-m-1)!}-\frac{(n-1)!}{(m-1)!(n-m)!}\\
&=\frac{\big((n-m)-m\big)(n-1)!}{m!(n-m)!}\\
&=\frac{k}m\binom{n-1}{m-1}\,.
\end{align*}$$
As a quick sanity check, note that when $k=1$ the paths in $\mathscr{P}_0$ are just the reflections in the $x$-axis of the Dyck paths from $\langle 0,0\rangle$ to $\langle n-1,0\rangle$, and it is well known that there are
$$\begin{align*}
C_m&=\frac1{m+1}\binom{2m}m=\frac{(2m)!}{m!(m+1)!}\\
&=\frac1m\binom{2m}{m-1}=\frac{k}m\binom{n-1}{m-1}\,.
\end{align*}$$
