## Nonnegative Partial Sum

The number of sequences with Nonnegative partial sums which can be formed from 1s and s (Bailey 1996, Brualdi 1992) is given by the Catalan Numbers. Bailey (1996) gives the number of Nonnegative partial sums of 1s and s , , ..., , so that

 (1)

for all . The closed form expression is
 (2)

for ,
 (3)

for , and
 (4)

for . Setting then recovers the Catalan Numbers
 (5)

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