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) 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
- Eric W. Weisstein, Motzkin Number at MathWorld.
- Donaghey, R. & Shapiro, L. W. (1977), “Motzkin numbers”, Journal of Combinatorial Theory, Series A 23 (3): 291–301, 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
