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?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ 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. $\endgroup$– luluCommented May 7, 2017 at 14:10
-
$\begingroup$ Your formulas never say anything corresponding to the "equal number of $1$ and $-1$" of the title. $\endgroup$– Marc van LeeuwenCommented May 7, 2017 at 14:56
-
$\begingroup$ @MarcvanLeeuwen I fixed that already! $\endgroup$– Parcly TaxelCommented May 7, 2017 at 15:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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}$.
answered May 7, 2017 at 14:49
$\begingroup$
$\endgroup$
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.
