Motzkin number

In mathematics , the Motzkin -th number is the number of different ways to draw non-intersecting chords between points on a circle . Not every point is necessarily touched by a chord. ${\displaystyle n}$ ${\displaystyle n}$

The Motzkin numbers were named after the American mathematician Theodore Motzkin and have a variety of applications in geometry , combinatorics and number theory .

Examples

• If you draw points on a circle , there are a total of 9 possibilities to draw non-intersecting circular chords through these four points: ${\displaystyle n=4}$

Thus the fourth is Motzkin number . ${\displaystyle M_{4}=9}$

• If you draw points on a circle , there are a total of 21 possibilities to draw non-intersecting circular chords through these five points: ${\displaystyle n=5}$

So the fifth is Motzkin number . ${\displaystyle M_{5}=21}$

• Another interpretation of the Motzkin numbers is provided by the following graphic based on the fourth Motzkin number . Start at the point with the coordinates (i.e. bottom left) and look for as many ways as possible to get to the point with the coordinates (i.e. bottom right). You can only go to the right, to the top right or to the bottom right, you can never go under the x-axis (i.e. the bottom line). There are 9 options: ${\displaystyle M_{4}=9}$ ${\displaystyle (0|0)}$ ${\displaystyle (4|0)}$

So there are a total of 9 ways to get from left to right, making the fourth Motzkin number . ${\displaystyle M_{4}=9}$

• Now start at (bottom left) and look for as many ways as possible to get to (bottom right). You can only proceed as in the example above. There are 21 options: ${\displaystyle (0|0)}$ ${\displaystyle (5|0)}$

So there are a total of 21 ways to get from left to right, making the fifth Motzkin number . ${\displaystyle M_{5}=21}$

In general, the -th Motzkin number is obtained when using this method to search for the number of paths in a coordinate system from to . ${\displaystyle n}$ ${\displaystyle (0|0)}$ ${\displaystyle (n|0)}$

In 1977, Robert Donaghey and Louis W. Shapiro gave a total of 14 ways to graphically represent Motzkin numbers.

• The following numbers are the smallest Motzkin numbers for : ${\displaystyle M_{n}}$ ${\displaystyle n=0,1,2,\dotsc }$

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, ... (Follow A001006 in OEIS )

Motzkin prime numbers

• A Motzkin prime is a Motzkin number that is prime . The following numbers are the smallest Motzkin prime numbers:

2, 127, 15511, 953467954114363 (episode A092832 in OEIS )

No more Motzkin prime numbers are known (as of March 23, 2020).

• The corresponding Motzkin number indices are as follows:

2, 7, 12, 36 (episode A092831 in OEIS )

The next index must be greater than (as of October 17, 2016). ${\displaystyle 10^{5}}$

properties

• The -th Motzkin number can be calculated recursively from previous Motzkin numbers as follows : ${\displaystyle n}$

${\displaystyle M_{n}=M_{n-1}+\sum _{i=0}^{n-2}M_{i}M_{n-2-i}={\frac {2n+1}{n+2}}\cdot M_{n-1}+{\frac {3n-3}{n+2}}\cdot M_{n-2}}$

• The -th Motzkin number can be represented by binomial coefficients : ${\displaystyle n}$

${\displaystyle M_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}\cdot C_{k}=\sum _{k=0}^{\lfloor n/2\rfloor }{\frac {{\binom {n}{2k}}{\binom {2k}{k}}}{k+1}}}$

Here is the rounding function , i.e. the largest whole number that is not greater than , and the -th Catalan number . ${\displaystyle \textstyle \lfloor \cdot \rfloor }$ ${\displaystyle \textstyle \lfloor n/2\rfloor ={\begin{cases}n/2,&{\text{für gerades }}n\\(n-1)/2&{\text{für ungerades }}n\end{cases}}}$ ${\displaystyle n/2}$ ${\displaystyle \textstyle C_{k}={\frac {1}{k+1}}{\binom {2k}{k}}}$ ${\displaystyle k}$

• The generating function of Motzkin numbers satisfies the following equation: ${\displaystyle \textstyle m(x)=\sum _{n=0}^{\infty }M_{n}x^{n}}$

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

See also

• Schröder numbers

literature

• Frank R. Bernhart: Catalan, Motzkin, and Riordan numbers . In: Discrete Mathematics . tape 204 , no. 1-3 , June 1999, pp. 73–112 , doi : 10.1016 / S0012-365X (99) 00054-0 ( full text as PDF on uniud.it ).
• Olivier Guibert, Elisa Pergola, Renzo Pinzani: Vexillary Involutions are Enumerated by Motzkin Numbers . In: Annals of Combinatorics . tape 5 , no. 2 , September 2001, p. 153–174 , doi : 10.1007 / PL00001297 ( summary as PDF on psu.edu ).
• Roy Oste, Joris Van der Jeugt: Motzkin paths, Motzkin polynomials and recurrence relations . In: The Electronic Journal of Combinatorics . tape 22 , no. 2 , April 21, 2015, p. 1-19 , doi : 10.37236 / 4781 ( researchgate.net ).

Web links

• Eric W. Weisstein : Motzkin Number . In: MathWorld (English).

Individual evidence

1. ^ Theodore Motzkin : Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products . In: Bull. Amer. Math. Soc. tape 54 , no. 4 , 1948, pp. 352–360 , doi : 10.1090 / S0002-9904-1948-09002-4 ( full text as PDF on ams.org ).
2. ^ Robert Donaghey, Louis W. Shapiro: Motzkin numbers . In: Journal of Combinatorial Theory , Series A . tape 23 , no. 3 , November 1977, pp. 291-301 , doi : 10.1016 / 0097-3165 (77) 90020-6 ( sciencedirect.com ).
3. ↑ Comments on OEIS A092831
4. ↑ ^{a b} Eric W. Weisstein : Motzkin Number . In: MathWorld (English).
5. ↑ Jiao-Lian Zhao, Feng Qi: Two explicit formulas for the generalized Motzkin numbers . In: Journal of Inequalities and Applications . tape 2017 , 2017, 44, doi : 10.1186 / s13660-017-1313-3 ( researchgate.net ).