1
$\begingroup$

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?

$\endgroup$
  • 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$ – lulu May 7 '17 at 14:10
  • $\begingroup$ Your formulas never say anything corresponding to the "equal number of $1$ and $-1$" of the title. $\endgroup$ – Marc van Leeuwen May 7 '17 at 14:56
  • $\begingroup$ @MarcvanLeeuwen I fixed that already! $\endgroup$ – Parcly Taxel May 7 '17 at 15:02
1
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.