Status: #good
Tags: #definition

Dyck path

A Dyck path of length $2n$ is a path on the coordinate plane from $(0,0)$ to $(2n,0)$ where your allowed moves are:

• (up) given by the vector (1, 1) - so up and to the right
• (down) given by the vector (-1, 1) - down and to the right
• You cannot ever end up below the $x$-axis (you are allowed to touch it though)
  Let the number of Dyck paths of length $2n$ be ${\tilde{C}}_n$.

We say a peak of a Dyck path is a up step followed by a down step.

We note that you need the ending point to be even.

Examples

• ${\tilde{C}}_0=1$, there is exactly 1 path of length 0 (doing nothing)
• ${\tilde{C}}_1=1$, you have to go up and then go back down (because you can't go down first)
• ${\tilde{C}}_2=2$
  • up up down down
  • up down up down
• ${\tilde{C}}_3=5$
  • up up up down down down
  • up up down up down down
  • up up down down up down
  • up down up up down down
  • up down up down up down

Properties

• The number of Dyck paths is equal to the Catalan numbers, which we shall denote $C_n$. proofs here