Editing Motzkin number (section)

== Combinatorial interpretations ==

The Motzkin number for {{mvar|n}} is also the number of positive integer sequences of length {{math|1=''n'' &minus; 1}} in which the opening and ending elements are either 1 or 2, and the difference between any two consecutive elements is &minus;1, 0 or 1. Equivalently, the Motzkin number for {{mvar|n}} is the number of positive integer sequences of length {{math|1=''n'' + 1}} in which the opening and ending elements are 1, and the difference between any two consecutive elements is &minus;1, 0 or 1.

Also, the Motzkin number for {{mvar|n}} gives the number of routes on the upper right quadrant of a grid from coordinate (0, 0) to coordinate ({{mvar|n}}, 0) in {{mvar|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 {{mvar|y}} = 0 axis.

For example, the following figure shows the 9 valid Motzkin paths from (0, 0) to (4, 0):

:[[Image:Motzkin4.svg|300px]]

There are at least fourteen different manifestations of Motzkin numbers in different branches of mathematics, as enumerated by {{harvtxt|Donaghey|Shapiro|1977}} in their survey of Motzkin numbers.
{{harvtxt|Guibert|Pergola|Pinzani|2001}} showed that [[vexillary involution]]s are enumerated by Motzkin numbers.