Motzkin number

Summary

The Motzkin number $M_n$ counts certain lattice paths from $(0, 0)$ to $(n, 0)$, see the definition. The paths use up, down and flat steps and never go below the horizontal axis. It also counts the ways to draw non-crossing chords between $n$ points on a circle. The sequence starts $1, 1, 2, 4, 9, 21, 51, 127$. The Motzkin numbers are a close relative of the Catalan numbers, which count the same paths without flat steps.