# Balanced ±1-sequences with no zero partial cumulative sum

Let $S_n$ be the set of all sequences consisting of $n$ each of $\pm1$: $$S_n=\{[s_1,s_2,\dots,s_{2n}]|s_i=\pm1,\sum s_i=0\}$$ Let $T_n$ be the set of sequences in $S_n$ with no partial cumulative sum zero: $$T_n=\{[s_1,s_2,\dots,s_{2n}]|s_i=\pm1,\sum s_i=0,\sum_{i=1}^j s_i\ne0\ \forall j<2n-1\}$$ What is $|T_n|$? And more importantly what's an elegant way to explain the solution?

• Hint: for $n>1$ we know that the last two entries must be the same (else deleting them would give a subsequence that summed to $0$). Let's say they are both $1$. Then the previous sequence has exactly two more $-1's$ than $1's$ so we can apply the Ballot Theorem. – lulu May 7 '17 at 14:10
• Your formulas never say anything corresponding to the "equal number of $1$ and $-1$" of the title. – Marc van Leeuwen May 7 '17 at 14:56
• @MarcvanLeeuwen I fixed that already! – Parcly Taxel May 7 '17 at 15:02

Here is another approach. $s_1\ne s_{2n}$, otherwise the cumulative sum would be zero somewhere. Thus there are two choices for $s_1$; without loss of generality say it is $+1$. Then the remaining $s_i$, $n-1$ each of $\pm1$, must be arranged so that the subsequence $s_2,\dots,s_{2n-1}$ has no negative cumulative sum. By definition, the number of admissible arrangements is the Catalan number $C_{n-1}$, so $|T_n|=2C_{n-1}$.
There is an elegant way to identify this with the Ballot Theorem. Let $a_i$ be the partial sums of the $s_i$. That is, $a_{i+1} = a_i + s_i, a_0=0.$ Consider the sequence of points in the plane $(i,a_i)$. They form a path from the origin to $(2n,0)$ that never crosses the $x$-axis. Now rotate and scale the path so the origin is fixed but now ends at $(n,n)$. Each step is now $(0,1)$ or $(1,0)$ and the path never crosses the line $y=x$. This is the ballot problem.