TOPICS
Search

Dyck Path

StaircaseWalkDiagonal

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.

nlists
1{1,-1}
2{1,1,-1,-1}
3{1,1,-1,1,-1,-1}, {1,1,1,-1,-1,-1}
4{1,1,-1,1,-1,1,-1,-1}, {1,1,-1,1,1,-1,-1,-1},
{1,1,1,-1,-1,1,-1,-1}, {1,1,1,-1,1,-1,-1,-1},
{1,1,1,1,-1,-1,-1,-1}

See also

Catalan Number, Lattice Path, Narayana Number, Staircase Walk

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.Degenhardt, S. L. and Milne, S. C. "Weighted Inversion Statistics and Their Symmetry Groups." J. Combin. Theory Ser. A 90, 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."

Referenced on Wolfram|Alpha

Dyck Path

Cite this as:

Weisstein, Eric W. "Dyck Path." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DyckPath.html

Subject classifications