# Motzkin number

Named after Theodore Motzkin 1948 Theodore Motzkin infinity see Properties 1, 1, 2, 4, 9, 21, 51 .mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}A001006Motzkin

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 $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, ... (sequence A001006 in the OEIS)

## Examples

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): ## Properties

The Motzkin numbers satisfy the recurrence relations

$M_{n}=M_{n-1}+\sum _{i=0}^{n-2}M_{i}M_{n-2-i}={\frac {2n+1}{n+2}}M_{n-1}+{\frac {3n-3}{n+2}}M_{n-2}.$ The Motzkin numbers can be expressed in terms of binomial coefficients and Catalan numbers:

$M_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}C_{k},$ and inversely,

$C_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}M_{k}.$ The generating function $m(x)=\sum _{n=0}^{\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 {1-x-{\sqrt {1-2x-3x^{2}}}}{2x^{2}}}.$ An integral representation of Motzkin numbers is given by

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

They have the asymptotic behaviour

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

A Motzkin prime is a Motzkin number that is prime. As of 2019, only 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 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 Donaghey & Shapiro (1977) in their survey of Motzkin numbers. Guibert, Pergola & Pinzani (2001) showed that vexillary involutions are enumerated by Motzkin numbers.