A Dyck path is a staircase walk from (0, 0) to (n, n) that lies strictly below (but may touch) the diagonal y = x. The number of Dyck paths of order n is given by the Catalan number C_n = 1/(n + 1)(2n n), i.e., 1, 2, 5, 14, 42, 132, ... (OEIS A000108). Equivalently, the number of sequences with nonnegative partial sums that can be formed from n 1s and n -1s is C_(n - 1) (Bailey 1996, Brualdi 1997, Mays and Wojciechowski 2000). The first few of these are summarized in the following table.

Catalan number | lattice path | Narayana number | staircase walk