www.wikidata.de-de.nina.az

Schröder Zahlen Die sind eine Folge natürlicher Zahlen mit einer Reihe unterschiedlicher Bedeutungen in der Kombinatorik

Schröder-Zahlen

Die Schröder-Zahlen sind eine Folge natürlicher Zahlen mit einer Reihe unterschiedlicher Bedeutungen in der Kombinatorik. Sie tauchen unter anderem bei der Aufzählung bestimmter Gitterpfade, Polygonzerlegungen, Bäume oder Permutationen auf. Man unterscheidet große Schröder-Zahlen und kleine Schröder-Zahlen, die im Wesentlichen nur um einen Faktor zwei voneinander abweichen.

Die großen Schröder-Zahlen geben die Anzahl der horizontal, vertikal oder diagonal verlaufenden Pfade in einem quadratischen Gitter an, die von der linken unteren zur rechten oberen Ecke verlaufen und dabei die Diagonale nicht überschreiten

Die Schröder-Zahlen sind nach dem deutschen Mathematiker Ernst Schröder benannt, der im Jahr 1870 das Problem untersuchte, auf wie viele Weisen Klammern in eine Summe geschrieben werden können. Sie sollen jedoch bereits dem griechischen Astronom Hipparchos von Nicäa bekannt gewesen sein.

Definitionen Bearbeiten

Große Schröder-Zahlen Bearbeiten

Die großen Schröder-Zahlen sind für rekursiv durch und

für definiert. Sie bilden die Folge

Kleine Schröder-Zahlen Bearbeiten

Die kleinen Schröder-Zahlen werden entsprechend durch und

für definiert. Sie bilden die Folge

Nach Plutarch soll diese Zahlenfolge bereits dem griechischen Astronom Hipparchos von Nicäa bekannt gewesen sein, weshalb sie auch Hipparchus-Zahlen oder Schröder-Hipparchus-Zahlen genannt werden. Sie sind eng mit den Catalan-Zahlen verwandt und werden daher auch als Super-Catalan-Zahlen bezeichnet.

Bedeutungen Bearbeiten

Klammerungen Bearbeiten

Ernst Schröder betrachtete 1870 das Problem, auf wie viele Weisen es möglich ist, Klammern in eine Summe bestehend aus Termen zu setzen. Die Klammern sollen dabei korrekt geschachtelt sein und jeweils mindestens zwei Terme umfassen. Beispielsweise gibt es die folgenden elf solcher Klammerungen von vier Termen:

Die Anzahl der auf diese Weise möglichen Klammerungen wird gerade durch die kleinen Schröder-Zahlen angegeben. Wenn man Klammern um die ganze Summe herum ebenfalls zulässt, erhält man als Lösung des Problems die großen Schröder-Zahlen. Im Vergleich dazu geben die Catalan-Zahlen die Anzahl der möglichen Klammerungen durch genau Klammerpaare an, die jeweils genau zwei Terme umfassen. Diese Klammerungen entsprechen der zweiten Zeile im obigen Beispiel.

Gitterpfade Bearbeiten

Die sechs möglichen Pfade in einem (2 × 2)-Gitternetz

Die großen Schröder-Zahlen geben auch die Anzahl der möglichen Pfade in einem quadratischen Gitternetz der Kantenlänge unter den folgenden Bedingungen an:

  • Jeder Pfad verläuft von der linken unteren Ecke zur rechten oberen Ecke .
  • Ein Schritt darf nur nach rechts , nach oben oder schräg nach rechts oben erfolgen.
  • Die Diagonale von links unten nach rechts oben darf nicht überschritten werden.

Solche Pfade werden auch Schröder-Pfade oder Königspfade genannt, da sie den Zugmöglichkeiten des Königs im Schach entsprechen. Die kleinen Schröder-Zahlen entsprechen der Anzahl derjenigen Pfade, bei denen kein Teilstück auf der Diagonale verläuft.

Die entsprechenden sechs Pfade in einem (4 × 2)-Gitternetz

Äquivalent dazu geben die großen Schröder-Zahlen die Anzahl der Pfade in einem Gitternetz der Größe an, die folgenden Bedingungen genügen:

  • Jeder Pfad verläuft von der linken unteren Ecke zur rechten unteren Ecke .
  • Ein Schritt darf nur schräg nach rechts oben , schräg nach rechts unten oder als Doppelschritt nach rechts erfolgen.
  • Die Null-Linie darf nicht unterschritten werden.

Diese Pfade entstehen durch Drehung, Streckung und Spiegelung der jeweiligen Pfade in dem quadratischen Gitternetz. Ein Doppelschritt entspricht so im quadratischen Gitter einem Diagonalschritt und die beiden schrägen Schritte entsprechen dort den Schritten jeweils nach rechts und nach oben. Die kleinen Schröder-Zahlen charakterisieren auch diejenigen Pfade, die keinen Scheitelpunkt bei aufweisen.

Zerlegungen Bearbeiten

Die sechs möglichen Unterteilungen eines regelmäßigen Fünfecks

Die großen Schröder-Zahlen zählen auch die Anzahl der Möglichkeiten, ein regelmäßiges Polygon mit Ecken unter den folgenden Bedingungen zu zerlegen:

  • Jeder Schnitt verläuft durch zwei nicht benachbarte Ecken.
  • Die Schnittlinien dürfen sich an den Ecken berühren aber im Inneren nicht schneiden.
  • Eine vorher ausgewählte Ecke darf nicht Endpunkt eines Schnitts sein.

Die kleinen Schröder-Zahlen entsprechen der Anzahl möglicher Zerlegungen eines regelmäßigen -Ecks, bei denen keine Ecke ausgespart wird.

Die sechs möglichen Zerlegungen eines Quadrats in Rechtecke mit zwei Schnitten

Äquivalent dazu zählen die großen Schröder-Zahlen auch die Anzahl der Möglichkeiten, ein Quadrat der Seitenlänge mit Schnitten in Rechtecke unter den folgenden Bedingungen zu zerlegen:

  • Innerhalb des Quadrats befinden sich die Punkte .
  • Jeder Schnitt verläuft horizontal oder vertikal durch genau einen dieser Punkte.
  • Jeder Schnitt unterteilt nur ein einzelnes Rechteck.

Permutationen Bearbeiten

Die sechs möglichen mit + und − bezeichneten Binärbäume mit drei Blättern

Die großen Schröder-Zahlen zählen auch die Anzahl der geordneten Binärbäume mit Blättern, die die folgenden Bedingungen erfüllen:

Jedem solchen Binärbaum entspricht eine separable Permutation der Länge . Separable Permutationen sind diejenigen Permutationen, die sich durch direkte oder schiefe Summen von trivialen Permutationen darstellen lassen. Sie sind auch diejenigen Permutationen, die die beiden Permutationsmuster und vermeiden. Die kleinen Schröder-Zahlen geben die Anzahl der Bäume an, bei denen der Wurzelknoten positiv ist.

Kombinatorische Äquivalenz Bearbeiten

Zur Äquivalenz von Zerlegungen, Bäumen und Klammerungen

All diese Konstruktionen sind kombinatorisch äquivalent, das heißt, es gibt eine bijektive Abbildung zwischen jeweils einander entsprechenden Objekten. Jeder Polygonzerlegung kann ein geordneter Baum zugeordnet werden, der dem dualen Graphen der Zerlegung entspricht. Die Flächen der Zerlegung entsprechen den inneren Knoten des Baums und die Seiten des Polygons seinen Blättern. Eine vorher ausgewählte Seite wird dabei der Wurzel des Baums zugeordnet.

Jede Polygonzerlegung entspricht auch einer zulässigen Klammerung einer Summe von Termen. Hierzu werden die Seiten des Polygons der Reihe nach den einzelnen Termen zugeordnet, wobei eine vorher ausgewählte Seite wiederum ausgelassen wird. Jede Ecke des Polygons entspricht dann einer Stelle, an der eine Klammer gesetzt werden kann und jede Schnittlinie genau einem Klammerpaar.

Alle Konstruktionen, die durch die großen Schröder-Zahlen aufgezählt werden, weisen eine grundlegende Symmetrie auf. Ihre Objekte fallen in zwei disjunkte Klassen, die gleich mächtig sind und jeweils durch die kleinen Schröder-Zahlen aufgezählt werden.

Eigenschaften Bearbeiten

Rekurrenzen Bearbeiten

Dreieck der Zahlen Sn,k
0 1 2 3 4 5 Summe
0 1 1
1 1 2 3
2 1 4 6 11
3 1 6 16 22 45
4 1 8 30 68 90 197
5 1 10 48 146 304 394 903

Eine lineare Differenzengleichung zweiter Ordnung ist für die großen Schröder-Zahlen durch

gegeben. Betrachtet man die Zahlen , die der linearen Rekurrenz

genügen, wobei und für gesetzt werden, dann ergeben sich die großen Schröder-Zahlen auf der Diagonalen, also

Die kleinen Schröder-Zahlen erfüllen entsprechend die lineare Differenzengleichung

Sie ergeben sich für als Summe

Explizite Formeln Bearbeiten

Die großen Schröder-Zahlen besitzen die expliziten Darstellungen

wobei die gaußsche hypergeometrische Funktion ist,

wobei und ein Gegenbauer-Polynom vom Grad ist, und

wobei das Legendre-Polynom vom Grad ist.

Erzeugende Funktionen Bearbeiten

Die erzeugende Funktion der großen Schröder-Zahlen ist

und die der kleinen Schröder-Zahlen entsprechend

Die erzeugenden Funktionen erfüllen die Identitäten

sowie

Siehe auch Bearbeiten

Literatur Bearbeiten

  • Ralph Grimaldi: Fibonacci and Catalan Numbers: An Introduction. John Wiley & Sons, 2012, ISBN 978-1-118-15976-7, Chapter 34.
  • Richard P. Stanley: Enumerative Combinatorics. Band 1. Cambridge University Press, 2002, ISBN 0-521-66351-2.
  • Richard P. Stanley: Enumerative Combinatorics. Band 2. Cambridge University Press, 2001, ISBN 0-521-78987-7.

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. R. P. Stanley: Enumerative Combinatorics. Band 1. Cambridge University Press, 2002, S. 51.
  2. R. P. Stanley: Hipparchus, Plutarch, Schröder, and Hough. In: American Mathematical Monthly. Band 104, Nr. 4, 1997, S. 344–350.
  3. ↑ Folge A001003 in OEIS
  4. E. Schröder: Vier combinatorische Probleme. In: Zeitschrift für Mathematik und Physik. Band 15, 1870, S. 361–376 (uni-goettingen.de).
  5. R. P. Stanley: Enumerative Combinatorics. Band 2. Cambridge University Press, 2001, S. 177 f.
  6. ↑ Folge A006318 in OEIS
  7. R. Grimaldi: Fibonacci and Catalan Numbers: An Introduction. John Wiley & Sons, 2012, S. 34.4.
  8. ↑ L. Shapiro, R. Sulanke: Bijections for the Schröder numbers. In: Mathematics Magazine. Band 73, Nr. 5, 2000, S. 369–376.
  9. R. P. Stanley: Catalan addendum to Enumerative Combinatorics. Band 2, 2013 (mit.edu [PDF]).
  10. L. Shapiro, A. B. Stephens: Bootstrap percolation, the Schröder numbers, and the N-kings problem. In: SIAM Journal on Discrete Mathematics. Band 4, 1991, S. 275–280.
  11. D. Foata, D. Zeilberger: A classic proof of a recurrence for a very classical sequence. In: Journal of Combinatorial Theory. A 80, Nr. 2, 1997, S. 380–384.
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:
Die Schroder Zahlen sind eine Folge naturlicher Zahlen mit einer Reihe unterschiedlicher Bedeutungen in der Kombinatorik Sie tauchen unter anderem bei der Aufzahlung bestimmter Gitterpfade Polygonzerlegungen Baume oder Permutationen auf Man unterscheidet grosse Schroder Zahlen und kleine Schroder Zahlen die im Wesentlichen nur um einen Faktor zwei voneinander abweichen Die grossen Schroder Zahlen geben die Anzahl der horizontal vertikal oder diagonal verlaufenden Pfade in einem quadratischen Gitter an die von der linken unteren zur rechten oberen Ecke verlaufen und dabei die Diagonale nicht uberschreitenDie Schroder Zahlen sind nach dem deutschen Mathematiker Ernst Schroder benannt der im Jahr 1870 das Problem untersuchte auf wie viele Weisen Klammern in eine Summe geschrieben werden konnen Sie sollen jedoch bereits dem griechischen Astronom Hipparchos von Nicaa bekannt gewesen sein Inhaltsverzeichnis 1 Definitionen 1 1 Grosse Schroder Zahlen 1 2 Kleine Schroder Zahlen 2 Bedeutungen 2 1 Klammerungen 2 2 Gitterpfade 2 3 Zerlegungen 2 4 Permutationen 2 5 Kombinatorische Aquivalenz 3 Eigenschaften 3 1 Rekurrenzen 3 2 Explizite Formeln 3 3 Erzeugende Funktionen 4 Siehe auch 5 Literatur 6 Weblinks 7 EinzelnachweiseDefinitionen BearbeitenGrosse Schroder Zahlen Bearbeiten Die grossen Schroder Zahlen S n displaystyle S n nbsp sind fur n N 0 displaystyle n in mathbb N 0 nbsp rekursiv durch S 0 1 displaystyle S 0 1 nbsp und S n S n 1 k 0 n 1 S k S n k 1 displaystyle S n S n 1 sum k 0 n 1 S k cdot S n k 1 nbsp fur n 1 displaystyle n geq 1 nbsp definiert Sie bilden die Folge 1 2 6 22 90 394 1806 8558 displaystyle 1 2 6 22 90 394 1806 8558 ldots nbsp Folge A006318 in OEIS Kleine Schroder Zahlen Bearbeiten Die kleinen Schroder Zahlen s n displaystyle s n nbsp werden entsprechend durch s 0 1 displaystyle s 0 1 nbsp und s n S n 2 s n 1 2 k 0 n 1 s k s n k 1 displaystyle s n frac S n 2 s n 1 2 sum k 0 n 1 s k cdot s n k 1 nbsp fur n 1 displaystyle n geq 1 nbsp definiert Sie bilden die Folge 1 1 3 11 45 197 903 4279 displaystyle 1 1 3 11 45 197 903 4279 ldots nbsp Folge A001003 in OEIS Nach Plutarch soll diese Zahlenfolge bereits dem griechischen Astronom Hipparchos von Nicaa bekannt gewesen sein weshalb sie auch Hipparchus Zahlen oder Schroder Hipparchus Zahlen genannt werden 1 2 Sie sind eng mit den Catalan Zahlen verwandt und werden daher auch als Super Catalan Zahlen bezeichnet 3 Bedeutungen BearbeitenKlammerungen Bearbeiten Ernst Schroder betrachtete 1870 das Problem auf wie viele Weisen es moglich ist Klammern in eine Summe bestehend aus n 1 displaystyle n 1 nbsp Termen zu setzen 4 Die Klammern sollen dabei korrekt geschachtelt sein und jeweils mindestens zwei Terme umfassen Beispielsweise gibt es die folgenden elf solcher Klammerungen von vier Termen a b c d a b c d a b c d a b c d a b c d a b c d a b c d a b c d a b c d a b c d a b c d displaystyle begin array llllll a b c d quad amp a b c d quad amp a b c d quad amp a b c d quad amp a b c d quad amp a b c d a b c d quad amp a b c d quad amp a b c d quad amp a b c d quad amp a b c d end array nbsp Die Anzahl der auf diese Weise moglichen Klammerungen wird gerade durch die kleinen Schroder Zahlen angegeben Wenn man Klammern um die ganze Summe herum ebenfalls zulasst erhalt man als Losung des Problems die grossen Schroder Zahlen Im Vergleich dazu geben die Catalan Zahlen die Anzahl der moglichen Klammerungen durch genau n 1 displaystyle n 1 nbsp Klammerpaare an die jeweils genau zwei Terme umfassen 5 Diese Klammerungen entsprechen der zweiten Zeile im obigen Beispiel Gitterpfade Bearbeiten nbsp Die sechs moglichen Pfade in einem 2 2 GitternetzDie grossen Schroder Zahlen geben auch die Anzahl der moglichen Pfade in einem quadratischen Gitternetz der Kantenlange n displaystyle n nbsp unter den folgenden Bedingungen an 6 Jeder Pfad verlauft von der linken unteren Ecke 0 0 displaystyle 0 0 nbsp zur rechten oberen Ecke n n displaystyle n n nbsp Ein Schritt darf nur nach rechts 1 0 displaystyle 1 0 nbsp nach oben 0 1 displaystyle 0 1 nbsp oder schrag nach rechts oben 1 1 displaystyle 1 1 nbsp erfolgen Die Diagonale von links unten nach rechts oben darf nicht uberschritten werden Solche Pfade werden auch Schroder Pfade oder Konigspfade genannt da sie den Zugmoglichkeiten des Konigs im Schach entsprechen 6 Die kleinen Schroder Zahlen entsprechen der Anzahl derjenigen Pfade bei denen kein Teilstuck auf der Diagonale verlauft 3 nbsp Die entsprechenden sechs Pfade in einem 4 2 GitternetzAquivalent dazu geben die grossen Schroder Zahlen die Anzahl der Pfade in einem Gitternetz der Grosse 2 n n displaystyle 2n times n nbsp an die folgenden Bedingungen genugen 7 Jeder Pfad verlauft von der linken unteren Ecke 0 0 displaystyle 0 0 nbsp zur rechten unteren Ecke 2 n 0 displaystyle 2n 0 nbsp Ein Schritt darf nur schrag nach rechts oben 1 1 displaystyle 1 1 nbsp schrag nach rechts unten 1 1 displaystyle 1 1 nbsp oder als Doppelschritt nach rechts 2 0 displaystyle 2 0 nbsp erfolgen Die Null Linie darf nicht unterschritten werden Diese Pfade entstehen durch Drehung Streckung und Spiegelung der jeweiligen Pfade in dem quadratischen Gitternetz Ein Doppelschritt entspricht so im quadratischen Gitter einem Diagonalschritt und die beiden schragen Schritte entsprechen dort den Schritten jeweils nach rechts und nach oben Die kleinen Schroder Zahlen charakterisieren auch diejenigen Pfade die keinen Scheitelpunkt bei y 1 displaystyle y 1 nbsp aufweisen 3 Zerlegungen Bearbeiten nbsp Die sechs moglichen Unterteilungen eines regelmassigen FunfecksDie grossen Schroder Zahlen zahlen auch die Anzahl der Moglichkeiten ein regelmassiges Polygon mit n 3 displaystyle n 3 nbsp Ecken unter den folgenden Bedingungen zu zerlegen 6 Jeder Schnitt verlauft durch zwei nicht benachbarte Ecken Die Schnittlinien durfen sich an den Ecken beruhren aber im Inneren nicht schneiden Eine vorher ausgewahlte Ecke darf nicht Endpunkt eines Schnitts sein Die kleinen Schroder Zahlen entsprechen der Anzahl moglicher Zerlegungen eines regelmassigen n 2 displaystyle n 2 nbsp Ecks bei denen keine Ecke ausgespart wird 8 nbsp Die sechs moglichen Zerlegungen eines Quadrats in Rechtecke mit zwei SchnittenAquivalent dazu zahlen die grossen Schroder Zahlen auch die Anzahl der Moglichkeiten ein Quadrat der Seitenlange n 1 displaystyle n 1 nbsp mit n displaystyle n nbsp Schnitten in n 1 displaystyle n 1 nbsp Rechtecke unter den folgenden Bedingungen zu zerlegen 9 Innerhalb des Quadrats befinden sich die n displaystyle n nbsp Punkte 1 1 n n displaystyle 1 1 ldots n n nbsp Jeder Schnitt verlauft horizontal oder vertikal durch genau einen dieser Punkte Jeder Schnitt unterteilt nur ein einzelnes Rechteck Permutationen Bearbeiten nbsp Die sechs moglichen mit und bezeichneten Binarbaume mit drei BlatternDie grossen Schroder Zahlen zahlen auch die Anzahl der geordneten Binarbaume mit n 1 displaystyle n 1 nbsp Blattern die die folgenden Bedingungen erfullen 10 Die inneren Knoten sind mit displaystyle nbsp oder displaystyle nbsp bezeichnet Die Blatter bleiben unbezeichnet Der rechte Teilbaum jedes inneren Knotens besitzt ein anderes Vorzeichen als der Knoten selbst Jedem solchen Binarbaum entspricht eine separable Permutation der Lange n 1 displaystyle n 1 nbsp Separable Permutationen sind diejenigen Permutationen die sich durch direkte oder schiefe Summen von trivialen Permutationen darstellen lassen Sie sind auch diejenigen Permutationen die die beiden Permutationsmuster 2 4 1 3 displaystyle 2 4 1 3 nbsp und 3 1 4 2 displaystyle 3 1 4 2 nbsp vermeiden Die kleinen Schroder Zahlen geben die Anzahl der Baume an bei denen der Wurzelknoten positiv ist Kombinatorische Aquivalenz Bearbeiten nbsp Zur Aquivalenz von Zerlegungen Baumen und KlammerungenAll diese Konstruktionen sind kombinatorisch aquivalent das heisst es gibt eine bijektive Abbildung zwischen jeweils einander entsprechenden Objekten Jeder Polygonzerlegung kann ein geordneter Baum zugeordnet werden der dem dualen Graphen der Zerlegung entspricht Die Flachen der Zerlegung entsprechen den inneren Knoten des Baums und die Seiten des Polygons seinen Blattern Eine vorher ausgewahlte Seite wird dabei der Wurzel des Baums zugeordnet 8 Jede Polygonzerlegung entspricht auch einer zulassigen Klammerung einer Summe von Termen Hierzu werden die Seiten des Polygons der Reihe nach den einzelnen Termen zugeordnet wobei eine vorher ausgewahlte Seite wiederum ausgelassen wird Jede Ecke des Polygons entspricht dann einer Stelle an der eine Klammer gesetzt werden kann und jede Schnittlinie genau einem Klammerpaar 8 Alle Konstruktionen die durch die grossen Schroder Zahlen aufgezahlt werden weisen eine grundlegende Symmetrie auf Ihre Objekte fallen in zwei disjunkte Klassen die gleich machtig sind und jeweils durch die kleinen Schroder Zahlen aufgezahlt werden Eigenschaften BearbeitenRekurrenzen Bearbeiten Dreieck der Zahlen Sn k n k displaystyle n diagdown k nbsp 0 1 2 3 4 5 Summe0 1 11 1 2 32 1 4 6 113 1 6 16 22 454 1 8 30 68 90 1975 1 10 48 146 304 394 903Eine lineare Differenzengleichung zweiter Ordnung ist fur die grossen Schroder Zahlen durch 6 n 1 S n 6 n 3 S n 1 n 2 S n 2 displaystyle n 1 S n 6n 3 S n 1 n 2 S n 2 nbsp gegeben Betrachtet man die Zahlen S n k displaystyle S n k nbsp die der linearen Rekurrenz S n k S n k 1 S n 1 k S n 1 k 1 displaystyle S n k S n k 1 S n 1 k S n 1 k 1 nbsp Folge A033877 in OEIS genugen wobei S n 0 1 displaystyle S n 0 1 nbsp und S n k 0 displaystyle S n k 0 nbsp fur k gt n displaystyle k gt n nbsp gesetzt werden dann ergeben sich die grossen Schroder Zahlen auf der Diagonalen also S n S n n displaystyle S n S n n nbsp Die kleinen Schroder Zahlen erfullen entsprechend die lineare Differenzengleichung 11 n s n 6 n 9 s n 1 n 3 s n 2 displaystyle ns n 6n 9 s n 1 n 3 s n 2 nbsp Sie ergeben sich fur n gt 0 displaystyle n gt 0 nbsp als Summe s n k 1 n 1 S n 1 k displaystyle s n sum k 1 n 1 S n 1 k nbsp Explizite Formeln Bearbeiten Die grossen Schroder Zahlen besitzen die expliziten Darstellungen S n 2 2 F 1 n 1 n 2 2 1 displaystyle S n 2 2 F 1 n 1 n 2 2 1 nbsp wobei 2 F 1 displaystyle 2 F 1 nbsp die gausssche hypergeometrische Funktion ist S n 1 2 C n 1 1 2 3 displaystyle S n frac 1 2 C n 1 1 2 3 nbsp wobei n gt 1 displaystyle n gt 1 nbsp und C n k displaystyle C n k nbsp ein Gegenbauer Polynom vom Grad n displaystyle n nbsp ist und S n 1 2 P n 1 3 6 P n 3 P n 1 3 displaystyle S n frac 1 2 left P n 1 3 6P n 3 P n 1 3 right nbsp wobei P n displaystyle P n nbsp das Legendre Polynom vom Grad n displaystyle n nbsp ist Erzeugende Funktionen Bearbeiten Die erzeugende Funktion der grossen Schroder Zahlen ist 6 G x n 0 S n x n 1 x 1 6 x x 2 2 x displaystyle G x sum n 0 infty S n x n frac 1 x sqrt 1 6x x 2 2x nbsp und die der kleinen Schroder Zahlen entsprechend 3 g x n 0 s n x n 1 x 1 6 x x 2 4 x displaystyle g x sum n 0 infty s n x n frac 1 x sqrt 1 6x x 2 4x nbsp Die erzeugenden Funktionen erfullen die Identitaten 1 x G x x G x 2 1 displaystyle 1 x G x xG x 2 1 nbsp sowie 1 x g x 2 g x 2 x displaystyle 1 x g x 2g x 2 x nbsp Siehe auch BearbeitenMotzkin ZahlLiteratur BearbeitenRalph Grimaldi Fibonacci and Catalan Numbers An Introduction John Wiley amp Sons 2012 ISBN 978 1 118 15976 7 Chapter 34 Richard P Stanley Enumerative Combinatorics Band 1 Cambridge University Press 2002 ISBN 0 521 66351 2 Richard P Stanley Enumerative Combinatorics Band 2 Cambridge University Press 2001 ISBN 0 521 78987 7 Weblinks BearbeitenEric W Weisstein Schroder Number In MathWorld englisch Eric W Weisstein Super Catalan Number In MathWorld englisch Einzelnachweise Bearbeiten R P Stanley Enumerative Combinatorics Band 1 Cambridge University Press 2002 S 51 R P Stanley Hipparchus Plutarch Schroder and Hough In American Mathematical Monthly Band 104 Nr 4 1997 S 344 350 a b c d Folge A001003 in OEIS E Schroder Vier combinatorische Probleme In Zeitschrift fur Mathematik und Physik Band 15 1870 S 361 376 uni goettingen de R P Stanley Enumerative Combinatorics Band 2 Cambridge University Press 2001 S 177 f a b c d e Folge A006318 in OEIS R Grimaldi Fibonacci and Catalan Numbers An Introduction John Wiley amp Sons 2012 S 34 4 a b c L Shapiro R Sulanke Bijections for the Schroder numbers In Mathematics Magazine Band 73 Nr 5 2000 S 369 376 R P Stanley Catalan addendum to Enumerative Combinatorics Band 2 2013 mit edu PDF L Shapiro A B Stephens Bootstrap percolation the Schroder numbers and the N kings problem In SIAM Journal on Discrete Mathematics Band 4 1991 S 275 280 D Foata D Zeilberger A classic proof of a recurrence for a very classical sequence In Journal of Combinatorial Theory A 80 Nr 2 1997 S 380 384 Abgerufen von https de wikipedia org w index php title Schroder Zahlen amp oldid 238344342