Motzkin number explained

Named After:	Theodore Motzkin
Publication Year:	1948
Author:	Theodore Motzkin
Terms Number:	infinity
Formula:	see Properties
First Terms:	1, 1, 2, 4, 9, 21, 51
Oeis:	A001006
Oeis Name:	Motzkin

In mathematics, the th Motzkin number is the number of different ways of drawing non-intersecting chords between 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

M _{n} for n = 0 , 1 , ... form the sequence:

1, 1, 2, 4, 9, 21, 51, 127, 323, 835, ...

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 relations

M _{n} = M _{n-1} + \sum ^{n -2} _{i =0} M _{iM} _{n-2-i} = (2 n +1)/(n +2) M _{n-1} + (3 n -3)/(n +2) M _{n-2} .

The Motzkin numbers can be expressed in terms of binomial coefficients and Catalan numbers:

M _{n=\sum} ^{\lfloor n/ 2 \rfloor} ^{k =0} \binom{n}{ 2 k} C _{k,}

and inversely,^[1]

C _{n+1} = \sum ^{n} _{k =0} \binom{n}{k} M _{k}

This gives

\sum ^{n} _{k =0} C _{k} = 1 + \sum ^{n} _{k =1} \binom{n}{k} M _{k-1} . m(x) = \sum ^{inf ty} _{n =0} M _{n} x ^{n} of the Motzkin numbers satisfiesx ^{2} m(x) ^{2} + (x - 1 ) m(x) + 1 = 0 and is explicitly expressed asm(x) = (1- x - \sqrt{ 1-2 x -3 x ^{2})/() }.

An integral representation of Motzkin numbers is given by

M _{n} = (2)/(\pi) \int ^{\pi} _{0} \sin(x) ^{2(2\cos(x)+1)} ^{n} dx .

They have the asymptotic behaviour

M _{n} \sim (1)/(2 \sqrt{\pi) }\left(\frac\right)^ 3^n,~ n \to \infty.

A Motzkin prime is a Motzkin number that is prime. 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 involutions are enumerated by Motzkin numbers.

See also

• Telephone number which represent the number of ways of drawing chords if intersections are allowed
• Delannoy number
• Narayana number
• Schröder number

Notes and References

1. Yi Wang and Zhi-Hai Zhang. Combinatorics of Generalized Motzkin Numbers. Journal of Integer Sequences. 18. 2015.