www.wikidata.de-de.nina.az

Motzkin Zahl In der Mathematik ist die n displaystyle n te die Anzahl der verschiedenen Möglichkeiten sich nicht schneid

Motzkin-Zahl

In der Mathematik ist die -te Motzkin-Zahl die Anzahl der verschiedenen Möglichkeiten, sich nicht schneidende Sehnen zwischen 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 Bearbeiten

  • Wenn man auf einem Kreis Punkte einzeichnet, gibt es insgesamt 9 Möglichkeiten, durch diese vier Punkte sich nicht schneidende Kreissehnen zu zeichnen:
Somit ist die vierte Motzkin-Zahl .
  • Wenn man auf einem Kreis 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 .
  • Eine andere Interpretation der Motzkin-Zahlen liefert die folgende Grafik anhand der vierten Motzkin-Zahl . Man starte beim Punkt mit den Koordinaten (also links unten) und suche so viele Wege wie möglich, um zum Punkt mit den Koordinaten (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 (also links unten) und suche so viele Wege wie möglich, um zu (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.
  • Die folgenden Zahlen sind die kleinsten Motzkin-Zahlen für :

Motzkin-Primzahlen Bearbeiten

  • 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).

Eigenschaften Bearbeiten

  • Die -te Motzkin-Zahl kann man wie folgt rekursiv aus vorhergehenden Motzkin-Zahlen berechnen:
Dabei ist die Abrundungsfunktion, also die größte ganze Zahl, die nicht größer als ist, und die -te Catalan-Zahl.

Siehe auch Bearbeiten

Literatur Bearbeiten

  • 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 Bearbeiten

Einzelnachweise Bearbeiten

  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. ↑ 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).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Mathematik ist die n displaystyle n te Motzkin Zahl die Anzahl der verschiedenen Moglichkeiten sich nicht schneidende Sehnen zwischen n displaystyle n Punkten eines Kreises zu zeichnen Dabei wird nicht notwendigerweise jeder Punkt durch eine Sehne beruhrt Die Motzkin Zahlen wurden nach dem US amerikanischen Mathematiker Theodore Motzkin benannt 1 und haben vielfaltige Anwendungen in der Geometrie der Kombinatorik und der Zahlentheorie Inhaltsverzeichnis 1 Beispiele 2 Motzkin Primzahlen 3 Eigenschaften 4 Siehe auch 5 Literatur 6 Weblinks 7 EinzelnachweiseBeispiele BearbeitenWenn man auf einem Kreis n 4 displaystyle n 4 nbsp Punkte einzeichnet gibt es insgesamt 9 Moglichkeiten durch diese vier Punkte sich nicht schneidende Kreissehnen zu zeichnen nbsp dd Somit ist die vierte Motzkin Zahl M 4 9 displaystyle M 4 9 nbsp Wenn man auf einem Kreis n 5 displaystyle n 5 nbsp Punkte einzeichnet gibt es insgesamt 21 Moglichkeiten durch diese funf Punkte nicht schneidende Kreissehnen zu zeichnen nbsp dd Somit ist die funfte Motzkin Zahl M 5 21 displaystyle M 5 21 nbsp Eine andere Interpretation der Motzkin Zahlen liefert die folgende Grafik anhand der vierten Motzkin Zahl M 4 9 displaystyle M 4 9 nbsp Man starte beim Punkt mit den Koordinaten 0 0 displaystyle 0 0 nbsp also links unten und suche so viele Wege wie moglich um zum Punkt mit den Koordinaten 4 0 displaystyle 4 0 nbsp 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 Moglichkeiten nbsp dd Es gibt somit insgesamt 9 Moglichkeiten um von links nach rechts zu gelangen womit die vierte Motzkin Zahl M 4 9 displaystyle M 4 9 nbsp ist Man starte nun bei 0 0 displaystyle 0 0 nbsp also links unten und suche so viele Wege wie moglich um zu 5 0 displaystyle 5 0 nbsp also rechts unten zu gelangen Dabei darf man nur wie im obigen Beispiel vorgehen Es gibt 21 Moglichkeiten nbsp dd Es gibt somit insgesamt 21 Moglichkeiten um von links nach rechts zu gelangen womit die funfte Motzkin Zahl M 5 21 displaystyle M 5 21 nbsp ist Generell erhalt man die n displaystyle n nbsp te Motzkin Zahl wenn man mit dieser Methode die Anzahl der Wege in einem Koordinatensystem von 0 0 displaystyle 0 0 nbsp nach n 0 displaystyle n 0 nbsp sucht Robert Donaghey und Louis W Shapiro gaben im Jahr 1977 insgesamt 14 Moglichkeiten an Motzkin Zahlen grafisch darzustellen 2 Die folgenden Zahlen sind die kleinsten Motzkin Zahlen M n displaystyle M n nbsp fur n 0 1 2 displaystyle n 0 1 2 dotsc nbsp 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 dd Motzkin Primzahlen BearbeitenEine 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 dd Mehr Motzkin Primzahlen sind nicht bekannt Stand 23 Marz 2020 Die dazugehorigen Motzkin Zahl Indizes sind die folgenden 2 7 12 36 Folge A092831 in OEIS dd Der nachste Index muss grosser als 10 5 displaystyle 10 5 nbsp sein Stand 17 Oktober 2016 3 Eigenschaften BearbeitenDie n displaystyle n nbsp te Motzkin Zahl kann man wie folgt rekursiv aus vorhergehenden Motzkin Zahlen berechnen 4 M n M n 1 i 0 n 2 M i M n 2 i 2 n 1 n 2 M n 1 3 n 3 n 2 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 nbsp dd Die n displaystyle n nbsp te Motzkin Zahl kann man durch Binomialkoeffizienten darstellen 5 M n k 0 n 2 n 2 k C k k 0 n 2 n 2 k 2 k 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 nbsp dd Dabei ist displaystyle textstyle lfloor cdot rfloor nbsp die Abrundungsfunktion also n 2 n 2 fur gerades n n 1 2 fur ungerades n displaystyle textstyle lfloor n 2 rfloor begin cases n 2 amp text fur gerades n n 1 2 amp text fur ungerades n end cases nbsp die grosste ganze Zahl die nicht grosser als n 2 displaystyle n 2 nbsp ist und C k 1 k 1 2 k k displaystyle textstyle C k frac 1 k 1 binom 2k k nbsp die k displaystyle k nbsp te Catalan Zahl Die erzeugende Funktion m x n 0 M n x n displaystyle textstyle m x sum n 0 infty M n x n nbsp von Motzkin Zahlen erfullt die folgende Gleichung 4 x 2 m x 2 x 1 m x 1 0 displaystyle x 2 cdot m x 2 x 1 cdot m x 1 0 nbsp dd Siehe auch BearbeitenSchroder ZahlenLiteratur BearbeitenFrank 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 BearbeitenEric W Weisstein Motzkin Number In MathWorld englisch Einzelnachweise Bearbeiten 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 Abgerufen von https de wikipedia org w index php title Motzkin Zahl amp oldid 210550649 Motzkin Primzahlen