A Dyck path is a staircase walk from to
that lies strictly below (but may touch) the diagonal . The number of Dyck paths of order is given by the Catalan number
Equivalently, the number of sequences with nonnegative partial sums that can be formed from 1s and s is (Bailey 1996, Brualdi 1997, Mays and Wojciechowski 2000).
The first few of these are summarized in the following table.
Bailey, D. F. "Counting Arrangements of 1's and 's." Math. Mag.69,
128-131, 1996.Brualdi, R. A. Introductory
Combinatorics, 4th ed. New York: Elsevier, 1997.Degenhardt,
S. L. and Milne, S. C. "Weighted Inversion Statistics and Their Symmetry
Groups." J. Combin. Theory Ser. A90, 49-103, 2000.Mays,
M. E. and Wojciechowski, J. "A Determinant Property of Catalan Numbers."
Disc. Math.211, 125-133, 2000.Sloane, N. J. A.
Sequence A000108/M1459 in "The On-Line
Encyclopedia of Integer Sequences."