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

| first_terms = 1, 1, 2, 4, 9, 21, 51

| OEIS = A001006

| OEIS_name = Motzkin

}}

In mathematics, the {{mvar|n}}th Motzkin number is the number of different ways of drawing non-intersecting 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 $M_n$ for $n = 0, 1, \dots$ form the sequence:

: 1, 1, 2, 4, 9, 21, 51, 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₄ = 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₅ = 21}}):

:Image:MotzkinChords5.svg

Properties

The Motzkin numbers satisfy the recurrence relations

: $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}.$

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,{{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}}

: $C_{n+1}=\sum_{k=0}^{n} \binom{n}{k} M_k$

This gives

: $\sum_{k=0}^{n}C_{k} = 1 + \sum_{k=1}^{n} \binom{n}{k} M_{k-1}.$

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. 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 − 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 {{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 −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):

: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 involutions are enumerated by Motzkin numbers.

References

{{citation

| last = Bernhart

| first = Frank R.

| title = Catalan, Motzkin, and Riordan numbers

| 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

}}