„Motzkin-Zahl“ – Versionsunterschied
Zur Navigation springen
Zur Suche springen
[gesichtete Version] | [gesichtete Version] |
Inhalt gelöscht Inhalt hinzugefügt
Form: Artikel in wiss. Fachzeitschriften in neuen Abschnitt "Literatur", mit geeigneter Vorlage und DOI |
K Quellenformatierung: Printquellen mit dafür vorgesehener Vorlage Literatur; wo möglich, DOI angegeben |
||
Zeile 1: | Zeile 1: | ||
In der [[Mathematik]] ist die <math>n</math>-te '''Motzkin-Zahl''' die Anzahl der verschiedenen Möglichkeiten, sich nicht schneidende [[Sehne (Geometrie)|Sehnen]] zwischen <math>n</math> Punkten eines Kreises zu zeichnen, wobei nicht notwendigerweise jeder Punkt durch eine Sehne berührt werden muss. |
In der [[Mathematik]] ist die <math>n</math>-te '''Motzkin-Zahl''' die Anzahl der verschiedenen Möglichkeiten, sich nicht schneidende [[Sehne (Geometrie)|Sehnen]] zwischen <math>n</math> Punkten eines Kreises zu zeichnen, wobei nicht notwendigerweise jeder Punkt durch eine Sehne berührt werden muss. |
||
Die Motzkin-Zahlen wurden nach dem US-amerikanischen Mathematiker [[Theodore Motzkin]] benannt<ref name="Motzkin">{{ |
Die Motzkin-Zahlen wurden nach dem US-amerikanischen Mathematiker [[Theodore Motzkin]] benannt<ref name="Motzkin">{{Literatur |
||
| |
|Sammelwerk=[[Bulletin of the American Mathematical Society|Bull. Amer. Math. Soc.]] |
||
|Band=54 |
|||
⚫ | |||
|Nummer=4 |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
| datum = 1948 |
|||
⚫ | |||
| zugriff = 2020-03-23 |
|||
|Datum=1948 |
|||
|DOI=10.1090/S0002-9904-1948-09002-4 |
|||
}}</ref> und haben vielfältige Anwendungen in der [[Geometrie]], der [[Kombinatorik]] und der [[Zahlentheorie]]. |
}}</ref> und haben vielfältige Anwendungen in der [[Geometrie]], der [[Kombinatorik]] und der [[Zahlentheorie]]. |
||
Zeile 25: | Zeile 27: | ||
: Es gibt somit insgesamt 21 Möglichkeiten, um von links nach rechts zu gelangen, womit die fünfte Motzkin-Zahl <math>M_5=21</math> ist. |
: Es gibt somit insgesamt 21 Möglichkeiten, um von links nach rechts zu gelangen, womit die fünfte Motzkin-Zahl <math>M_5=21</math> ist. |
||
: Generell erhält man die <math>n</math>-te Motzkin-Zahl, wenn man mit dieser Methode die Anzahl der Wege in einem Koordinatensystem von <math>(0/0)</math> nach <math>(n/0)</math> sucht. |
: Generell erhält man die <math>n</math>-te Motzkin-Zahl, wenn man mit dieser Methode die Anzahl der Wege in einem Koordinatensystem von <math>(0/0)</math> nach <math>(n/0)</math> sucht. |
||
: Robert Donaghey und Louis W. Shapiro gaben im Jahr 1977 insgesamt 14 Möglichkeiten an, Motzkin-Zahlen grafisch darzustellen.<ref name="Donaghey">{{ |
: Robert Donaghey und Louis W. Shapiro gaben im Jahr 1977 insgesamt 14 Möglichkeiten an, Motzkin-Zahlen grafisch darzustellen.<ref name="Donaghey">{{Literatur |
||
| |
|Sammelwerk= [[Journal of Combinatorial Theory]], Series A |
||
|Band=23 |
|||
⚫ | |||
|Nummer=3 |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
| datum = November 1977 |
|||
⚫ | |||
| zugriff = 2020-03-23 |
|||
|Datum=1977-11 |
|||
|DOI=10.1016/0097-3165(77)90020-6 |
|||
}}</ref> |
}}</ref> |
||
* Die folgenden Zahlen sind die kleinsten Motzkin-Zahlen <math>M_n</math> für <math>n=0,1,2,\ldots</math>: |
* Die folgenden Zahlen sind die kleinsten Motzkin-Zahlen <math>M_n</math> für <math>n=0,1,2,\ldots</math>: |
||
Zeile 48: | Zeile 52: | ||
* Die <math>n</math>-te Motzkin-Zahl kann man wie folgt [[rekursiv]] aus vorhergehenden Motzkin-Zahlen berechnen:<ref name="Mathworld">{{MathWorld |id=MotzkinNumber |title=Motzkin Number}}</ref> |
* Die <math>n</math>-te Motzkin-Zahl kann man wie folgt [[rekursiv]] aus vorhergehenden Motzkin-Zahlen berechnen:<ref name="Mathworld">{{MathWorld |id=MotzkinNumber |title=Motzkin Number}}</ref> |
||
:: <math>M_{n}=M_{n-1}+\sum_{i=0}^{n-2}M_iM_{n-2-i}=\frac{2n+1}{n+2} \cdot M_{n-1}+\frac{3n-3}{n+2} \cdot M_{n-2}</math> |
:: <math>M_{n}=M_{n-1}+\sum_{i=0}^{n-2}M_iM_{n-2-i}=\frac{2n+1}{n+2} \cdot M_{n-1}+\frac{3n-3}{n+2} \cdot M_{n-2}</math> |
||
* Die <math>n</math>-te Motzkin-Zahl kann man durch [[Binomialkoeffizient]]en und [[Catalan-Zahl]]en <math>C_k</math> darstellen:<ref name="Zhao">{{ |
* Die <math>n</math>-te Motzkin-Zahl kann man durch [[Binomialkoeffizient]]en und [[Catalan-Zahl]]en <math>C_k</math> darstellen:<ref name="Zhao">{{Literatur |
||
| |
|Sammelwerk=[[Journal of Inequalities and Applications]] |
||
|Band=2017 |
|||
⚫ | |||
|ArtikelNr=44 |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
| datum = 2017 |
|||
⚫ | |||
| zugriff = 2020-03-23 |
|||
|Datum=2017 |
|||
|DOI=10.1186/s13660-017-1313-3 |
|||
}}</ref> |
}}</ref> |
||
:: <math>M_n=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k} \cdot C_k</math> |
:: <math>M_n=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k} \cdot C_k</math> |
Version vom 1. April 2020, 11:38 Uhr
In der Mathematik ist die -te Motzkin-Zahl die Anzahl der verschiedenen Möglichkeiten, sich nicht schneidende Sehnen zwischen Punkten eines Kreises zu zeichnen, wobei nicht notwendigerweise jeder Punkt durch eine Sehne berührt werden muss.
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.
Beispiele
- Wenn man auf einem Kreis Punkte einzeichnet, gibt es insgesamt 9 Möglichkeiten, durch diese vier Punkte sich nicht schneidende Kreissehnen zu zeichnen:
- Wenn man auf einem Kreis Punkte einzeichnet, gibt es insgesamt 21 Möglichkeiten, durch diese fünf Punkte nicht schneidende Kreissehnen zu zeichnen:
- Eine andere Interpretation der Motzkin-Zahlen liefert die folgende Grafik anhand der vierten Motzkin-Zahl . Man starte bei der Koordinate (also links unten) und suche so viele Wege wie möglich, um zur Koordinate (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 ist.
- Man starte nun bei der Koordinate (also links unten) und suche so viele Wege wie möglich, um zur Koordinate (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 ist.
- Generell erhält man die -te Motzkin-Zahl, wenn man mit dieser Methode die Anzahl der Wege in einem Koordinatensystem von nach 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 für :
Motzkin-Primzahlen
- Eine Motzkin-Primzahl ist eine Motzkin-Zahl, die prim ist. Die folgenden Zahlen sind die kleinsten Motzkin-Primzahlen:
Mehr Motzkin-Primzahlen sind nicht bekannt (Stand: 23. März 2020).
- Die dazugehörigen Motzkin-Zahl-Indizes sind die folgenden:
- Der nächste Index muss größer als sein. (Stand: 17. Oktober 2016)[3]
Eigenschaften
- Die -te Motzkin-Zahl kann man durch Binomialkoeffizienten und Catalan-Zahlen darstellen:[5]
- Dabei ist die Abrundungsfunktion, also die größte ganze Zahl , und .
- Die erzeugende Funktion von Motzkin-Zahlen erfüllt die folgende Gleichung:[4]
Siehe auch
Literatur
- 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).
Weblinks
- Eric W. Weisstein: Motzkin Number. In: MathWorld (englisch).
Einzelnachweise
- ↑ 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).
- ↑ 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).
- ↑ Comments zu OEIS A092831
- ↑ a b Eric W. Weisstein: Motzkin Number. In: MathWorld (englisch).
- ↑ 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).