# Prove that a sequence can be enumerated using Catalan numbers

This problem is taken from R.P. Stanley’s Enumerative Combinatorics.

Give bijective arguments to show that sequences of $n$ $1$'s and $n$ $-1$'s in which the sum of the first $i$ terms is non-negative for all $i$ can be enumerated by $C(n)$.

I think it has something to do with the proof that there are $\frac{1}{(n+1)}\cdot \binom{2n}{n}$ lattice paths from $(0,0)$ to $(n,n)$ that never go above the diagonal $y=x$; but I'm unsure how these two things are related.

Note that the lattice problem in your question is equivalent to going from $(0,0)$ to $(2n,0)$ using steps $(1,1)$ and $(1,-1)$ and staying in the region $y\geq 0$. You just rotate your problem by angle $-\frac\pi 4$ around origin, reflect using $x$ axis as mirror and scale it by a factor of $\sqrt 2$ to get this one.
Coming back to the original question, can you see that if $s_i$ is the sum of first $i$ terms then $(i,s_i)$ for $0\leq i\leq 2n$ with the condition $s_i\geq 0$ will trace such a path?
EDIT: Suppose that you are constructing the sequence of $1$'s and $-1$'s from scratch, and at the $i$-th step, the sum is $s_i$. Look at the pair $(i, s_i)$. In the next step, it is going to be $(i+1,s_i\pm 1)= (i, s_i)+(1,\pm1)$. Initially it was $(0,0)$ and finally it will be $(2n,0)$, while the sum satisfies $s_i\geq 0$ for all $i$. This is exactly the lattice problem that I stated earlier.
• In other words, are you just saying there has to be more $1$'s than $-1$'s? Is that the proof? That a "bad path" would have more $-1$'s? – Nxt3 Jan 29 '15 at 18:02