Motzkin number
|
|
A Motzkin number for a given number n is the number of different ways of drawing non-intersecting chords on a circle between n points. The Motzkin numbers have very diverse applications in geometry, combinatorics and number theory. The first few Motzkin numbers are Template:OEIS:
1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829
The Motzkin number for n is also the number of positive integer sequences n - 1 long in which the opening and ending elements are either 1 or 2, and the difference between any two consecutive elements is -1, 0 or 1.
Also on the upper right quadrant of a grid, the Motzkin number for n gives the number of steps from coordinate (0, 0) to coordinate (n, 0) if one is only allowed to move to the right (either up, down or straight) but forbidden from dipping below the y = 0 axis.
All together, there are at least fourteen different manifestations of Motzkin numbers in different branches of mathematics, as enumerated by Donaghey and Shapiro in their 1977 survey of Motzkin numbers.