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.

Hope this helps...

  • $\begingroup$ 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? $\endgroup$ – Nxt3 Jan 29 '15 at 18:02

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.