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,\dots$:

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, … (Vorlage: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 (Vorlage: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 (Vorlage: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 }(\genfrac{}{}{0ex}{}{n}{2k})\cdot C_k=\sum _{k=0}^{\lfloor n/2\rfloor }\frac{(\genfrac{}{}{0ex}{}{n}{2k})(\genfrac{}{}{0ex}{}{2k}{k})}{k+1}$

Dabei ist $\lfloor \cdot \rfloor$ die Abrundungsfunktion, also $\lfloor n/2\rfloor =\{\begin{array}{cc}n/2,& \text{für gerades }n\\ (n-1)/2& \text{für ungerades }n\end{array}$ die größte ganze Zahl, die nicht größer als $n/2$ ist, und $C_k=\frac{1}{k+1}(\genfrac{}{}{0ex}{}{2k}{k})$ die $k$-te Catalan-Zahl.

• Die erzeugende Funktion $m(x)={\sum }_{n=0}^{\mathrm{\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$

Siehe auch

• Schröder-Zahlen

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur

Weblinks

• Vorlage:MathWorld