A nonnegative partial sum is a partial sum that is nonnegative. The number of sequences
with nonnegative partial
sums which can be formed from the permutations
of 
1s and 
s (Bailey 1996, Brualdi 1999) is given
by the Catalan numbers 
. For example, the 
permutations of 
having nonnegative partial sums are 
, 
, 
, 
, and (1, 
, 1, 
,
1, 
).
Similarly, for integers 
, the number of sequences
with nonnegative partial
sums formed from 
1s and 
s (Bailey 1996) is given by
 |
where these coefficients form Catalan's triangle
 |
(OEIS A009766) and 
.
's."
Math. Mag. 69, 128-131, 1996.Brualdi, R. A.