Inmathematics, thenthMotzkin number is the number of different ways of drawing non-intersectingchords betweenn points on acircle (not necessarily touching every point by a chord). The Motzkin numbers are named afterTheodore Motzkin and have diverse applications ingeometry,combinatorics andnumber theory.

The Motzkin numbers${\displaystyle M_n}$ for${\displaystyle n=0,1,\dots }$ form the sequence:

1,1,2,4,9,21,51,127, 323, 835, ... (sequenceA001006 in theOEIS)

The following figure shows the 9 ways to draw non-intersecting chords between 4 points on a circle (M₄ = 9):

The following figure shows the 21 ways to draw non-intersecting chords between 5 points on a circle (M₅ = 21):

The Motzkin numbers satisfy therecurrence relations

${\displaystyle 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 ofbinomial coefficients andCatalan numbers:

${\displaystyle M_n=\sum _{k=0}^{\lfloor n/2\rfloor }(\genfrac{}{}{0ex}{}{n}{2k})C_k,}$

and inversely,^[1]

${\displaystyle C_{n+1}=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})M_k}$

This gives

${\displaystyle \sum _{k=0}^n{C}_k=1+\sum _{k=1}^n(\genfrac{}{}{0ex}{}{n}{k})M_{k-1}.}$

Thegenerating function${\displaystyle m(x)=\sum _{n=0}^{\mathrm{\infty }}{M}_n{x}^n}$ of the Motzkin numbers satisfies

${\displaystyle x^{2}m(x{)}^2+(x-1)m(x)+1=0}$

and is explicitly expressed as

${\displaystyle m(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}.}$

An integral representation of Motzkin numbers is given by

${\displaystyle M_n=\frac{2}{\pi }{\int }_0^{\pi }\sin (x{)}^2(2\cos (x)+1{)}^{n}dx}$.

They have the asymptotic behaviour

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

AMotzkin prime is a Motzkin number that isprime. Four such primes are known:

2, 127, 15511, 953467954114363 (sequenceA092832 in theOEIS)

The Motzkin number forn is also the number of positive integer sequences of lengthn − 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 forn is the number of positive integer sequences of lengthn + 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 forn gives the number of routes on the upper right quadrant of a grid from coordinate (0, 0) to coordinate (n, 0) inn steps if one is allowed to move only to the right (up, down or straight) at each step but forbidden from dipping below they = 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 byDonaghey & Shapiro (1977) in their survey of Motzkin numbers.Guibert, Pergola & Pinzani (2001) showed thatvexillary involutions are enumerated by Motzkin numbers.

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

• Bernhart, Frank R. (1999), "Catalan, Motzkin, and Riordan numbers",Discrete Mathematics,204 (1–3):73–112,doi:10.1016/S0012-365X(99)00054-0
• Donaghey, R.; Shapiro, L. W. (1977), "Motzkin numbers",Journal of Combinatorial Theory, Series A,23 (3):291–301,doi:10.1016/0097-3165(77)90020-6,MR 0505544
• Guibert, O.; Pergola, E.; Pinzani, R. (2001), "Vexillary involutions are enumerated by Motzkin numbers",Annals of Combinatorics,5 (2):153–174,doi:10.1007/PL00001297,ISSN 0218-0006,MR 1904383,S2CID 123053532
• Motzkin, T. S. (1948), "Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products",Bulletin of the American Mathematical Society,54 (4):352–360,doi:10.1090/S0002-9904-1948-09002-4

• Weisstein, Eric W."Motzkin Number".MathWorld.

• Integer sequences
• Enumerative combinatorics

• Articles with short description
• Short description is different from Wikidata