# Motzkin-Zahl

In der Mathematik ist die $n$-te Motzkin-Zahl die Anzahl der verschiedenen Möglichkeiten, sich nicht schneidende Sehnen zwischen $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 und haben vielfältige Anwendungen in der Geometrie, der Kombinatorik und der Zahlentheorie.

## Beispiele

* Wenn man auf einem Kreis $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 $M_{4}=9$.
* Wenn man auf einem Kreis $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 $M_{5}=21$.
* Eine andere Interpretation der Motzkin-Zahlen liefert die folgende Grafik anhand der vierten Motzkin-Zahl $M_{4}=9$. Man starte beim Punkt mit den Koordinaten $(0|0)$ (also links unten) und suche so viele Wege wie möglich, um zum Punkt mit den Koordinaten $(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 $M_{4}=9$ ist.
* Man starte nun bei $(0|0)$ (also links unten) und suche so viele Wege wie möglich, um zu $(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 $M_{5}=21$ ist.
    Generell erhält man die $n$-te Motzkin-Zahl, wenn man mit dieser Methode die Anzahl der Wege in einem Koordinatensystem von $(0|0)$ nach $(n|0)$ sucht.
    Robert Donaghey und Louis W. Shapiro gaben im Jahr 1977 insgesamt 14 Möglichkeiten an, Motzkin-Zahlen grafisch darzustellen.
* Die folgenden Zahlen sind die kleinsten Motzkin-Zahlen $M_{n}$ für $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)

## Motzkin-Primzahlen

* 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 $10^{5}$ sein (Stand: 17. Oktober 2016).

## Eigenschaften

* Die $n$-te Motzkin-Zahl kann man wie folgt rekursiv aus vorhergehenden Motzkin-Zahlen berechnen:
       $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 $n$-te Motzkin-Zahl kann man durch Binomialkoeffizienten darstellen:
       $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 $\textstyle \lfloor \cdot \rfloor$ die Abrundungsfunktion, also $\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 $n/2$ ist, und $\textstyle C_{k}={\frac {1}{k+1}}{\binom {2k}{k}}$ die $k$-te Catalan-Zahl.
* Die erzeugende Funktion $\textstyle m(x)=\sum _{n=0}^{\infty }M_{n}x^{n}$ von Motzkin-Zahlen erfüllt die folgende Gleichung:
       $x^{2}\cdot m(x)^{2}+(x-1)\cdot m(x)+1=0$