Schröder-Zahlen – Wikipedia
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/72/Schr%C3%B6der_numbers_qtl3.svg/330px-Schr%C3%B6der_numbers_qtl3.svg.png)
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 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 | Quelltext bearbeiten]Große Schröder-Zahlen
[Bearbeiten | Quelltext 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 | Quelltext 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.[1][2] Sie sind eng mit den Catalan-Zahlen verwandt und werden daher auch als Super-Catalan-Zahlen bezeichnet.[3]
Bedeutungen
[Bearbeiten | Quelltext bearbeiten]Klammerungen
[Bearbeiten | Quelltext 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.[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:
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.[5] Diese Klammerungen entsprechen der zweiten Zeile im obigen Beispiel.
Gitterpfade
[Bearbeiten | Quelltext bearbeiten]![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Schroeder_number_2x2.svg/360px-Schroeder_number_2x2.svg.png)
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:[6]
- 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.[6] Die kleinen Schröder-Zahlen entsprechen der Anzahl derjenigen Pfade, bei denen kein Teilstück auf der Diagonale verläuft.[3]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Schroeder_paths.svg/520px-Schroeder_paths.svg.png)
Ä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:[7]
- 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.[3]
Zerlegungen
[Bearbeiten | Quelltext bearbeiten]![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0d/Schr%C3%B6der_numbers_qtl2.svg/440px-Schr%C3%B6der_numbers_qtl2.svg.png)
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:[6]
- 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.[8]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Schroeder_rectangulation_3.svg/440px-Schroeder_rectangulation_3.svg.png)
Ä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:[9]
- 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 | Quelltext bearbeiten]![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Schr%C3%B6der_numbers_qtl1.svg/440px-Schr%C3%B6der_numbers_qtl1.svg.png)
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:[10]
- Die inneren Knoten sind mit oder bezeichnet.
- Die Blätter bleiben unbezeichnet.
- Der rechte Teilbaum jedes inneren Knotens besitzt ein anderes Vorzeichen als der Knoten selbst.
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 | Quelltext bearbeiten]![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/32/Tree-polygon-paren_equivalence.svg/220px-Tree-polygon-paren_equivalence.svg.png)
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.[8]
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.[8]
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 | Quelltext bearbeiten]Rekurrenzen
[Bearbeiten | Quelltext bearbeiten]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[6]
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[11]
- .
Sie ergeben sich für als Summe
- .
Explizite Formeln
[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]Die erzeugende Funktion der großen Schröder-Zahlen ist[6]
und die der kleinen Schröder-Zahlen entsprechend[3]
Die erzeugenden Funktionen erfüllen die Identitäten
sowie
- .
Siehe auch
[Bearbeiten | Quelltext bearbeiten]Literatur
[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]- Eric W. Weisstein: Schröder Number. In: MathWorld (englisch).
- Eric W. Weisstein: Super Catalan Number. In: MathWorld (englisch).
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ R. P. Stanley: Enumerative Combinatorics. Band 1. Cambridge University Press, 2002, S. 51.
- ↑ R. P. Stanley: Hipparchus, Plutarch, Schröder, and Hough. In: American Mathematical Monthly. Band 104, Nr. 4, 1997, S. 344–350.
- ↑ a b c d Folge A001003 in OEIS
- ↑ E. Schröder: Vier combinatorische Probleme. In: Zeitschrift für 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 & Sons, 2012, S. 34.4.
- ↑ a b c L. Shapiro, R. Sulanke: Bijections for the Schröder 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 Schröder 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.