Motzkin number

In mathematics, the nth Motzkin number 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 diverse applications in geometry, combinatorics and number theory. The Motzkin numbers for form the sequence: 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, ... The following figure shows the 9 ways to draw non-intersecting chords between 4 points on a circle (M4 = 9): The following figure shows the 21 ways to draw non-intersecting chords between 5 points on a circle (M5 = 21): The Motzkin numbers satisfy the recurrence relations The Motzkin numbers can be expressed in terms of binomial coefficients and Catalan numbers: and inversely, This gives The generating function 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. , only four such primes are known: 2, 127, 15511, 953467954114363 The Motzkin number for n is also the number of positive integer sequences of length n − 1 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 n is the number of positive integer sequences of length n + 1 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 n gives the number of routes on the upper right quadrant of a grid from coordinate (0, 0) to coordinate (n, 0) in 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 in their survey of Motzkin numbers.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (2)

Narayana number

In combinatorics, the Narayana numbers form a triangular array of natural numbers, called the Narayana triangle, that occur in various counting problems. They are named after Canadian mathematician T. V. Narayana (1930–1987). The Narayana numbers can be expressed in terms of binomial coefficients: The first eight rows of the Narayana triangle read: An example of a counting problem whose solution can be given in terms of the Narayana numbers , is the number of words containing n pairs of parentheses, which are correctly matched (known as Dyck words) and which contain k distinct nestings.

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 n ≥ k ≥ 0 and is written It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n; this coefficient can be computed by the multiplicative formula which using factorial notation can be compactly expressed as For example, the fourth power of 1 + x is and the binomial coefficient is the coefficient of the x2 term.