Motzkin number
From Wikipedia, the free encyclopedia
In mathematics, a Motzkin number for a given number n (named after Theodore Motzkin) 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 (sequence A001006 in 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 following figure shows the 9 ways to draw non-intersecting chords between 4 points on a circle.
The following figure shows the 21 ways to draw non-intersecting chords between 5 points on a circle.
A Motzkin prime is a Motzkin number that is prime. As of October 2007, four such primes are known (sequence A092832 in OEIS):
2, 127, 15511, 953467954114363
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 routes from coordinate (0, 0) to coordinate (n, 0) on 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.
For example, the following figure shows the 9 valid Motzkin paths from (0, 0) to (4, 0):
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.
[edit] See also
[edit] References
- Weistein, Eric W., "Motzkin Number" from MathWorld.
- Donaghey, R.; Shapiro, L. W. (1977), "Motzkin numbers", Journal of Combinatorial Theory, Series A 23 (3): 291–301, doi:, MR0505544
- Motzkin, T. S. (1948), "Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products", Bulletin of the American Mathematical Society 54: 352–360, doi:
