TOPICS
Search

Nonnegative Partial Sum


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 n 1s and n -1s (Bailey 1996, Brualdi 1997) is given by the Catalan numbers C_n. For example, the C_3=5 permutations of (-1,-1,-1,1,1,1) having nonnegative partial sums are (1,1,1,-1,-1,-1), (1,1,-1,1,-1,-1), (1,1,-1,-1,1,-1), (1,-1,1,1,-1,-1), and (1, -1, 1, -1, 1, -1).

Similarly, the number of nonnegative partial sums of n 1s and k -1s (Bailey 1996) is given by

 c_(nk)=((n+k)!(n-k+1))/(k!(n+1)!),

where these coefficients form Catalan's triangle

 1      ; 1 1     ; 1 2 2    ; 1 3 5 5   ; 1 4 9 14 14  ; 1 5 14 28 42 42 ; 1 6 20 48 90 132 132

(OEIS A009766) and c_(nk)=C_n


See also

Catalan Number, Catalan's Triangle, Partial Sum

Explore with Wolfram|Alpha

References

Bailey, D. F. "Counting Arrangements of 1's and -1's." Math. Mag. 69, 128-131, 1996.Brualdi, R. A. Introductory Combinatorics, 4th ed. New York: Elsevier, 1997.

Referenced on Wolfram|Alpha

Nonnegative Partial Sum

Cite this as:

Weisstein, Eric W. "Nonnegative Partial Sum." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NonnegativePartialSum.html

Subject classifications