Combinatorics - Possibly catalan number question

Question

How many sequences $a_1a_2...a_{2n}$ are there with the digits $\{-1,1\}$ such that $\forall j: \sum_{i=1}^{j}a_i \geq 0$ ?

this is very similar to what we know of catalan numbers (or dyck words). The problem that arises, is that with dyck words, that sum of the entire sequence has to be zero. Here we just ask that it's not negative.

And so, the dyck words of length $2n$ are merely a subset of the set we are looking for. So the answer (I think) is not exactly $C_{2n}$.

How do I solve this?

Answer 1

One approach starts by considering the partial sums of the sequence. There are only two possibilities: either they stay strictly positive all the time, or they reach zero at least once.

• First case corresponds to sequence starting with $a_1=1$, followed by sub-sequence which satisfies the given inequality.
• In the second case, let the first return to zero happen at index $j$. The sequence then consists of $a_1=1$, $a_j=(-1)$ and the sub-sequence between $2$ and $(j-1)$ behaves like a Dyck word. The rest of the sequence, starting from term $(j+1)$, satisfies the inequality again.

Thus, if $A_n$ denotes the number of sequences satisfying the inequality, we get the recurrence $$\begin{eqnarray}A_0 & = & 1 \\ A_n & = & A_{n-1} + \sum_{k=1}^{\lfloor n/2\rfloor} C_{k-1} A_{n-2k}\end{eqnarray}$$ (where $C_n$ denotes $n$-th Catalan number, the number of Dyck words of length $2n$; and $j=2k+2$ is the point when partial sums reach zero for the first time).

As it turns out, the solution of the recurrence is pretty simple: $A_n=\binom{n}{\lfloor n/2\rfloor}$ which, for even $n$, simplifies to $A_{2n}=\binom{2n}{n}$.

---

Of course, there is always more than one way to prove something; now that we know the answer, it might be easier to come up with some "obvious" combinatorial argument why the answer should be precisely what it is :-)