 | ||
In mathematics, a Motzkin number for a given number n 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). The Motzkin numbers are named after Theodore Motzkin, and have very diverse applications in geometry, combinatorics and number theory.
Contents
Motzkin numbers
Examples
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.
Properties
Motzkin numbers satisfy the recurrence relations
Motzkin numbers can be expressed in terms of binomial coefficients and Catalan numbers:
A Motzkin prime is a Motzkin number that is prime. As of October 2013, four such primes are known:
2, 127, 15511, 953467954114363 (sequence A092832 in the OEIS)Combinatorial interpretations
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 & Shapiro (1977) in their survey of Motzkin numbers. Guibert, Pergola & Pinzani (2001) showed that vexillary involutions are enumerated by Motzkin numbers.