In mathematics, the nth Motzkin number is the number of different ways of drawing non-intersecting chords between n points on a circle (not necessarily touching every point by a chord).
form the sequence: The following figure shows the 9 ways to draw non-intersecting chords between 4 points on a circle (M4 = 9): The following figure shows the 21 ways to draw non-intersecting chords between 5 points on a circle (M5 = 21): The Motzkin numbers satisfy the recurrence relations The Motzkin numbers can be expressed in terms of binomial coefficients and Catalan numbers: and inversely,[1] This gives The generating function
Equivalently, the Motzkin number for n is the number of positive integer sequences of length n + 1 in which the opening and ending elements are 1, and the difference between any two consecutive elements is −1, 0 or 1.
Also, the Motzkin number for n gives the number of routes on the upper right quadrant of a grid from coordinate (0, 0) to coordinate (n, 0) in n steps if one is allowed to move only to the right (up, down or straight) at each step but forbidden from dipping below the y = 0 axis.
Guibert, Pergola & Pinzani (2001) showed that vexillary involutions are enumerated by Motzkin numbers.