Motzkin-Zahl

In der Mathematik ist die ${\displaystyle n}${\displaystyle n}-te Motzkin-Zahl die Anzahl der verschiedenen Möglichkeiten, sich nicht schneidende Sehnen zwischen ${\displaystyle n}${\displaystyle n} Punkten eines Kreises zu zeichnen. Dabei wird nicht notwendigerweise jeder Punkt durch eine Sehne berührt.

Die Motzkin-Zahlen wurden nach dem US-amerikanischen Mathematiker Theodore Motzkin benannt^[1] und haben vielfältige Anwendungen in der Geometrie, der Kombinatorik und der Zahlentheorie.

• Wenn man auf einem Kreis ${\displaystyle n=4}${\displaystyle n=4} Punkte einzeichnet, gibt es insgesamt 9 Möglichkeiten, durch diese vier Punkte sich nicht schneidende Kreissehnen zu zeichnen:

Somit ist die vierte Motzkin-Zahl ${\displaystyle M_{4}=9}${\displaystyle M_{4}=9}.

• Wenn man auf einem Kreis ${\displaystyle n=5}${\displaystyle n=5} Punkte einzeichnet, gibt es insgesamt 21 Möglichkeiten, durch diese fünf Punkte nicht schneidende Kreissehnen zu zeichnen:

Somit ist die fünfte Motzkin-Zahl ${\displaystyle M_{5}=21}${\displaystyle M_{5}=21}.

• Eine andere Interpretation der Motzkin-Zahlen liefert die folgende Grafik anhand der vierten Motzkin-Zahl ${\displaystyle M_{4}=9}${\displaystyle M_{4}=9}. Man starte beim Punkt mit den Koordinaten ${\displaystyle (0|0)}${\displaystyle (0|0)} (also links unten) und suche so viele Wege wie möglich, um zum Punkt mit den Koordinaten ${\displaystyle (4|0)}${\displaystyle (4|0)} (also rechts unten) zu gelangen. Dabei darf man nur nach rechts, nach rechts oben oder nach rechts unten gehen, niemals darf man unter die x-Achse (also die unterste Linie). Es gibt 9 Möglichkeiten:

Es gibt somit insgesamt 9 Möglichkeiten, um von links nach rechts zu gelangen, womit die vierte Motzkin-Zahl ${\displaystyle M_{4}=9}${\displaystyle M_{4}=9} ist.

• Man starte nun bei ${\displaystyle (0|0)}${\displaystyle (0|0)} (also links unten) und suche so viele Wege wie möglich, um zu ${\displaystyle (5|0)}${\displaystyle (5|0)} (also rechts unten) zu gelangen. Dabei darf man nur wie im obigen Beispiel vorgehen. Es gibt 21 Möglichkeiten:

Es gibt somit insgesamt 21 Möglichkeiten, um von links nach rechts zu gelangen, womit die fünfte Motzkin-Zahl ${\displaystyle M_{5}=21}${\displaystyle M_{5}=21} ist.

Generell erhält man die ${\displaystyle n}${\displaystyle n}-te Motzkin-Zahl, wenn man mit dieser Methode die Anzahl der Wege in einem Koordinatensystem von ${\displaystyle (0|0)}${\displaystyle (0|0)} nach ${\displaystyle (n|0)}${\displaystyle (n|0)} sucht.

Robert Donaghey und Louis W. Shapiro gaben im Jahr 1977 insgesamt 14 Möglichkeiten an, Motzkin-Zahlen grafisch darzustellen.^[2]

• Die folgenden Zahlen sind die kleinsten Motzkin-Zahlen ${\displaystyle M_{n}}${\displaystyle M_{n}} für ${\displaystyle n=0,1,2,\dotsc }${\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, ... (Folge A001006 in OEIS)

• Eine Motzkin-Primzahl ist eine Motzkin-Zahl, die prim ist. Die folgenden Zahlen sind die kleinsten Motzkin-Primzahlen:

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

Mehr Motzkin-Primzahlen sind nicht bekannt (Stand: 23. März 2020).

• Die dazugehörigen Motzkin-Zahl-Indizes sind die folgenden:

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

Der nächste Index muss größer als ${\displaystyle 10^{5}}${\displaystyle 10^{5}} sein (Stand: 17. Oktober 2016).^[3]

• Die ${\displaystyle n}${\displaystyle n}-te Motzkin-Zahl kann man wie folgt rekursiv aus vorhergehenden Motzkin-Zahlen berechnen:^[4]

${\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}}${\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}}

• Die ${\displaystyle n}${\displaystyle n}-te Motzkin-Zahl kann man durch Binomialkoeffizienten darstellen:^[5]

${\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}}}${\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}}}

Dabei ist ${\displaystyle \textstyle \lfloor \cdot \rfloor }${\displaystyle \textstyle \lfloor \cdot \rfloor } die Abrundungsfunktion, also ${\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 \textstyle \lfloor n/2\rfloor ={\begin{cases}n/2,&{\text{für gerades }}n\\(n-1)/2&{\text{für ungerades }}n\end{cases}}} die größte ganze Zahl, die nicht größer als ${\displaystyle n/2}${\displaystyle n/2} ist, und ${\displaystyle \textstyle C_{k}={\frac {1}{k+1}}{\binom {2k}{k}}}${\displaystyle \textstyle C_{k}={\frac {1}{k+1}}{\binom {2k}{k}}} die ${\displaystyle k}${\displaystyle k}-te Catalan-Zahl.

• Die erzeugende Funktion ${\displaystyle \textstyle m(x)=\sum _{n=0}^{\infty }M_{n}x^{n}}${\displaystyle \textstyle m(x)=\sum _{n=0}^{\infty }M_{n}x^{n}} von Motzkin-Zahlen erfüllt die folgende Gleichung:^[4]

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

• Schröder-Zahlen

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

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

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. Band 54, Nr. 4, 1948, S. 352–360, doi:10.1090/S0002-9904-1948-09002-4 (Volltext als PDF auf ams.org). 
2. ↑ Robert Donaghey, Louis W. Shapiro: Motzkin numbers. In: Journal of Combinatorial Theory, Series A. Band 23, Nr. 3, November 1977, S. 291–301, doi:10.1016/0097-3165(77)90020-6 (sciencedirect.com). 
3. ↑ Comments zu OEIS A092831
4. ↑ ^{a b} Eric W. Weisstein: Motzkin Number. In: MathWorld (englisch).
5. ↑ Jiao-Lian Zhao, Feng Qi: Two explicit formulas for the generalized Motzkin numbers. In: Journal of Inequalities and Applications . Band 2017, 2017, 44, doi:10.1186/s13660-017-1313-3 (researchgate.net). 

• Ganzzahlmenge
• Zahlentheorie
• Kreisgeometrie