Editing Motzkin number

{{Short description|Number of unique ways to draw non-intersecting chords in a circle}}
{{ Infobox integer sequence
| named_after = Theodore Motzkin
| publication_year = 1948
| author = Theodore Motzkin
| terms_number = [[infinity]]
| formula = see [[#Properties|Properties]]
| first_terms = 1, [[1 (number)|1]], [[2 (number)|2]], [[4 (number)|4]], [[9 (number)|9]], [[21 (number)|21]], [[51 (number)|51]]
| OEIS = A001006
| OEIS_name = Motzkin
}}
In [[mathematics]], the {{mvar|n}}th '''Motzkin number''' is the number of different ways of drawing non-intersecting [[Chord (geometry)|chords]]  between {{mvar|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 <math>M_n</math> for <math>n = 0, 1, \dots</math> form the sequence:

: 1, [[1 (number)|1]], [[2 (number)|2]], [[4 (number)|4]], [[9 (number)|9]], [[21 (number)|21]], [[51 (number)|51]], [[127 (number)|127]], 323, 835, ... {{OEIS|id=A001006}}

== Examples ==

The following figure shows the 9 ways to draw non-intersecting chords between 4 points on a circle ({{math|1=''M''<sub>4</sub> = 9}}):

:[[Image:MotzkinChords4.svg]]

The following figure shows the 21 ways to draw non-intersecting chords between 5 points on a circle ({{math|1=''M''<sub>5</sub> = 21}}):

:[[Image:MotzkinChords5.svg]]

== Properties ==

The Motzkin numbers satisfy the [[recurrence relation]]s

:<math>M_{n}=M_{n-1}+\sum_{i=0}^{n-2}M_iM_{n-2-i}=\frac{2n+1}{n+2}M_{n-1}+\frac{3n-3}{n+2}M_{n-2}.</math>

The Motzkin numbers can be expressed in terms of [[binomial coefficient]]s and [[Catalan number]]s:

:<math>M_n=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k} C_k,</math>

and inversely,<ref>{{cite journal|last1=Yi Wang and Zhi-Hai Zhang|title=Combinatorics of Generalized Motzkin Numbers| journal=Journal of Integer Sequences|issue=18|date=2015|url=https://cs.uwaterloo.ca/journals/JIS/VOL18/Wang/wang21.pdf}}</ref>

:<math>C_{n+1}=\sum_{k=0}^{n} \binom{n}{k} M_k</math>

This gives

:<math>\sum_{k=0}^{n}C_{k} = 1 + \sum_{k=1}^{n} \binom{n}{k} M_{k-1}.</math>

The [[generating function]] <math>m(x) = \sum_{n=0}^\infty M_n x^n</math> of the Motzkin numbers satisfies
:<math>x^2 m(x)^2 + (x - 1) m(x) + 1 = 0</math>
and is explicitly expressed as
:<math>m(x) = \frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}.</math>

An integral representation of Motzkin numbers is given by
:<math>M_{n}=\frac{2}{\pi}\int_0^\pi \sin(x)^2(2\cos(x)+1)^n dx</math>.

They have the asymptotic behaviour
:<math>M_{n}\sim \frac{1}{2 \sqrt{\pi}}\left(\frac{3}{n}\right)^{3/2} 3^n,~ n \to \infty</math>.

A '''Motzkin prime''' is a Motzkin number that is [[prime number|prime]]. Four such primes are known:

: 2, 127, 15511, 953467954114363 {{OEIS|id=A092832}}

== Combinatorial interpretations ==

The Motzkin number for {{mvar|n}} is also the number of positive integer sequences of length {{math|1=''n'' &minus; 1}} in which the opening and ending elements are either 1 or 2, and the difference between any two consecutive elements is &minus;1, 0 or 1. Equivalently, the Motzkin number for {{mvar|n}} is the number of positive integer sequences of length {{math|1=''n'' + 1}} in which the opening and ending elements are 1, and the difference between any two consecutive elements is &minus;1, 0 or 1.

Also, the Motzkin number for {{mvar|n}} gives the number of routes on the upper right quadrant of a grid from coordinate (0, 0) to coordinate ({{mvar|n}}, 0) in {{mvar|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 {{mvar|y}} = 0 axis.

For example, the following figure shows the 9 valid Motzkin paths from (0, 0) to (4, 0):

:[[Image:Motzkin4.svg|300px]]

There are at least fourteen different manifestations of Motzkin numbers in different branches of mathematics, as enumerated by {{harvtxt|Donaghey|Shapiro|1977}} in their survey of Motzkin numbers.
{{harvtxt|Guibert|Pergola|Pinzani|2001}} showed that [[vexillary involution]]s are enumerated by Motzkin numbers.

==See also==
* [[Telephone number (mathematics)|Telephone number]] which represent the number of ways of drawing chords if intersections are allowed
* [[Delannoy number]]
* [[Narayana number]]
* [[Schröder number]]

==References==
{{Reflist}}
* {{citation
 | last = Bernhart
 | first = Frank R.
 | title = Catalan, Motzkin, and Riordan numbers 
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | volume = 204
 | year = 1999
 | pages = 73–112
 | doi = 10.1016/S0012-365X(99)00054-0
 | issue = 1–3| doi-access = free
 }}
* {{citation
 | last1 = Donaghey
 | first1 = R.
 | last2 = Shapiro
 | first2 = L. W.
 | title = Motzkin numbers
 | journal = [[Journal of Combinatorial Theory]] | series = Series A
 | volume = 23
 | issue = 3
 | year = 1977
 | pages = 291–301
 | mr = 0505544
 | doi = 10.1016/0097-3165(77)90020-6| doi-access = free
 }}
* {{Citation | last1=Guibert | first1=O. | last2=Pergola | first2=E. | last3=Pinzani | first3=R. | title=Vexillary involutions are enumerated by Motzkin numbers | doi=10.1007/PL00001297 | year=2001 | journal=[[Annals of Combinatorics]] | issn=0218-0006 | volume=5 | issue=2 | pages=153–174 | mr=1904383| s2cid=123053532 }}
* {{citation
 | last = Motzkin
 | first = T. S. | author-link = Theodore Motzkin
 | title = Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products
 | journal = [[Bulletin of the American Mathematical Society]]
 | volume = 54
 | year = 1948
 | pages = 352–360
 | doi = 10.1090/S0002-9904-1948-09002-4
 | issue = 4| doi-access = free
 }}

==External links==
* {{MathWorld|title=Motzkin Number|urlname=MotzkinNumber}}

{{Classes of natural numbers}}

[[Category:Integer sequences]]
[[Category:Enumerative combinatorics]]
[[Category:Eponymous numbers in mathematics]]