Nonnegative Partial Sum

The number of sequences with Nonnegative partial sums which can be formed from $n$ 1s and $n$ $-1$s (Bailey 1996, Brualdi 1992) is given by the Catalan Numbers. Bailey (1996) gives the number of Nonnegative partial sums of $n$ 1s and $k$ $-1$s $a_1$, $a_2$, ..., $a_{n+k}$, so that

$$a_1+a_2+\ldots+a_i\geq 0$$ (1)

for all $1\leq i\leq n+k$. The closed form expression is

$$\left\{\matrix{n\cr 0\cr}\right\}=1$$ (2)

for $n\geq 0$,

$$\left\{\matrix{n\cr 1\cr}\right\}=n$$ (3)

for $n\geq 1$, and

$$\left\{\matrix{n\cr k\cr}\right\}={(n+1-k)(n+2)(n+3)\cdots(n+k)\over k!},$$ (4)

for $n\geq k\geq 2$. Setting $k=n$ then recovers the Catalan Numbers

$$C_n=\left\{\matrix{n\cr n\cr}\right\}={1\over n+1}{2n\choose n}.$$ (5)

See also Catalan Number

References

Bailey, D. F. ``Counting Arrangements of 1's and $-1$'s.'' Math. Mag. 69, 128-131, 1996.

Brualdi, R. A. Introductory Combinatorics, 2nd ed. New York: Elsevier, 1992.