Motzkin Number
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the th Motzkin number is the number of different ways of drawing non-intersecting
chords Chord may refer to: * Chord (music), an aggregate of musical pitches sounded simultaneously ** Guitar chord a chord played on a guitar, which has a particular tuning * Chord (geometry), a line segment joining two points on a curve * Chord ( ...
between points on a
circle A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is const ...
(not necessarily touching every point by a chord). The Motzkin numbers are named after
Theodore Motzkin Theodore Samuel Motzkin (26 March 1908 – 15 December 1970) was an Israeli-American mathematician. Biography Motzkin's father Leo Motzkin, a Ukrainian Jew, went to Berlin at the age of thirteen to study mathematics. He pursued university studi ...
and have diverse applications in
geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
,
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
and
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
. The Motzkin numbers M_n for n = 0, 1, \dots form the sequence: : 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, ...


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

The Motzkin numbers satisfy the
recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
s :M_=M_+\sum_^M_iM_=\fracM_+\fracM_. The Motzkin numbers can be expressed in terms of
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s and
Catalan number In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Cata ...
s: :M_n=\sum_^ \binom C_k, and inversely, :C_=\sum_^ \binom M_k. The
generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
m(x) = \sum_^\infty M_n x^n of the Motzkin numbers satisfies :x^2 m(x)^2 + (x - 1) m(x) + 1 = 0 and is explicitly expressed as :m(x) = \frac. An integral representation of Motzkin numbers is given by :M_=\frac\int_0^\pi \sin(x)^2(2\cos(x)+1)^n dx. They have the asymptotic behaviour :M_\sim \frac\left(\frac\right)^ 3^n,~ n \to \infty. A Motzkin prime is a Motzkin number that is
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. , only four such primes are known: : 2, 127, 15511, 953467954114363


Combinatorial interpretations

The Motzkin number for is also the number of positive integer sequences of length 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. Equivalently, the Motzkin number for is the number of positive integer sequences of length in which the opening and ending elements are 1, and the difference between any two consecutive elements is −1, 0 or 1. Also, the Motzkin number for gives the number of routes on the upper right quadrant of a grid from coordinate (0, 0) to coordinate (, 0) in steps if one is allowed to move only to the right (up, down or straight) at each step but forbidden from dipping below the = 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 in their survey of Motzkin numbers. showed that
vexillary involution In mathematics, a vexillary permutation is a permutation ''ÎĽ'' of the positive integers containing no subpermutation isomorphic to the permutation (2143); in other words, there do not exist four numbers ''i'' < ''j'' < ''k''&n ...
s are enumerated by Motzkin numbers.


See also

*
Telephone number A telephone number is a sequence of digits assigned to a landline telephone subscriber station connected to a telephone line or to a wireless electronic telephony device, such as a radio telephone or a mobile telephone, or to other devices f ...
which represent the number of ways of drawing chords if intersections are allowed *
Delannoy number In mathematics, a Delannoy number D describes the number of paths from the southwest corner (0, 0) of a rectangular grid to the northeast corner (''m'', ''n''), using only single steps north, northeast, or east. The Delannoy numbers are named aft ...
*
Narayana number In combinatorics, the Narayana numbers \operatorname(n, k), n \in \mathbb^+, 1 \le k \le n form a triangular array of natural numbers, called the Narayana triangle, that occur in various counting problems. They are named after Canadian mathemati ...
*
Schröder number In mathematics, the Schröder number S_n, also called a ''large Schröder number'' or ''big Schröder number'', describes the number of lattice paths from the southwest corner (0,0) of an n \times n grid to the northeast corner (n,n), using only ...


References

* * * *


External links

* {{Classes of natural numbers Integer sequences Enumerative combinatorics