Number of permutations in a given set with given properties 
Given a set of $n$ $1$s and $n$ $-1$s, what's the number of permutation, such that, if we keep summing the terms of this permutation (from left to right, two at the time), we never get $-1$ as result of the sum?

Remark: we assume that we do not start with $-1$.
e. g. the permutation $(1, -1, -1, 1 )$ is invalid because if we sum the first two elements we get $( 0, -1, 1 )$, summing again and we get $( -1, 1 )$; the permutation $( 1, 1, -1, -1 )$ is valid because if we keep summing the terms from left to right we never get $-1$ as result of the sum.
I'm searching for a general formula in terms of $n$. I thought about it for a while but I couldn't solve it, and honestly I don't even know if it has a general formula.
 A: Hint: The number of $-1's$ that you encounter at any stage should be less than or equal to the number of $1's$. This means that we have to form "Dyck words" with $n$ $1's$ and $n$ $-1's$. This can be done in $C_n=\frac {\binom {2n}{n}}{n+1}$ ways, where $C_n$ is the $n^{th}$ Catalan number. This can be shown using Andre's reflection method.
Note: A good reference for this is-
https://en.m.wikipedia.org/wiki/Catalan_number
Check the second proof under the "Proof of the formula" sub-section.
A: Call the number of such words $a_n$ where $n$ is the length of the word. If $n$ is odd, then we have $a_{n+1}=2a_n$ as the sum of all entries contributing to $a_n$ cannot be zero. Hence it must be strictly positive and for each word contributing to $a_n$ you can add two words (one with final letter $1$ and one with final letter $-1$) to contribute to $a_{n+1}$. If $n$ is even, you have $a_{n+1}=2a_n-C_{n/2}$ where $C_n$ is the Catalan number. This comes from the fact that $C_n$ is equal to
Consider all the binomial(2n,n) paths on squared paper that (i) start at (0, 0), (ii) end at (2n, 0) and (iii) at each step, either make a (+1,+1) step or a (+1,-1) step. Then the number of such paths that never go below the x-axis (Dyck paths) is C(n). [Chung-Feller]
by the integer squence encyclpedia. The paths that contribute one istead of two in the passage from $a_n$ to $a_{n+1}$ come from the $C_{n/2}$ paths which have sum of all entries equal to zero.
I claim that $a_n= {n\choose [n/2]}$. Indeed, we proceed by induction on $n$. For $n=1$, we have $a_n=1$ which is consisten with the formula. For odd $n=2m+1\geq 1$, we have $${n+1\choose m+1}=\frac{2(m+1)(2m+1)!}{(m+1)!(m+1)!}=2\frac{(2m+1)}{m!(m+1)!}=2{n\choose [n/2]}=2a_n=a_{n+1}\,.$$ For even $n=2m>1$, we have $$a_{n+1}=2a_n-C_{n/2}=2{n\choose m}-\frac{n\choose m}{m+1}=\frac{n!}{m!m!}\left(2-\frac{1}{m+1}\right)=\frac{(2m+1)!}{m!(m+1)!}={n+1\choose [(n+1)/2]}\,.$$
