Consider the number of sequences that can be formed from permutations of a set of elements such that each partial sum is nonnegative.
The number of sequences with nonnegative partial sums which can be formed from the
permutations of 
1s and 
s (Bailey 1996, Brualdi 1997) is given
by the Catalan numbers 
. For example, the 
permutations of 
having nonnegative partial sums are 
, 
, 
, 
, and (1, 
, 1, 
, 1, 
).
Similarly, the number of nonnegative partial sums of 
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.