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
for
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
:
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:
:
and inversely,
:
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 ...
of the Motzkin numbers satisfies
:
and is explicitly expressed as
:
An integral representation of Motzkin numbers is given by
:
.
They have the asymptotic behaviour
:
.
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