# 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 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).

• @ParclyTaxel thank you for pointing out the parity issue that I forgot to add. Actually, 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 loose one dollar for each tail. What is the probability that, keeping 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 ${2n+1\choose n} (2/3)^n (1/3)^{n+2}$ over $n$ from $0$ to $\infty$, one gets $1/2$ because subsequences leading to win $2$\$ are overcounted. Apr 28 at 12:04
• @ParclyTaxel Hence, I wanted to find a way the use the above described approach to solve the original problem, by excluding the subsequences overcounded. Apr 28 at 12:07
• @ParclyTaxel Thank you for improving the question. The only approach that I have in mind to solve the problem is based on the inclusion–exclusion principle, but the calculations seem too complicated and I guess there is something simpler I am missing here. Apr 28 at 12:14
• André's reflection method will work here. Cf. here. Apr 28 at 12:27
• Apr 28 at 12:42

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*}