info prev up next book cdrom email home

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
\end{displaymath} (1)

for all $1\leq i\leq n+k$. The closed form expression is
\left\{\matrix{n\cr 0\cr}\right\}=1
\end{displaymath} (2)

for $n\geq 0$,
\left\{\matrix{n\cr 1\cr}\right\}=n
\end{displaymath} (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!},
\end{displaymath} (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}.
\end{displaymath} (5)

See also Catalan Number


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.

© 1996-9 Eric W. Weisstein