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 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).

Catalan number | Catalan's triangle | partial sum