In der kombinatorischen Mathematik bilden die Zahlen von Catalan eine Folge von natürlichen Zahlen, die in verschiedenen zählenden Problemen vorkommen, häufig rekursiv definierte Gegenstände einschließend. Sie werden nach dem belgischen Mathematiker Eugène Charles Catalan (1814-1894) genannt.

Die n katalanische Zahl wird direkt in Bezug auf binomische Koeffizienten durch gegeben

:

Die ersten katalanischen Zahlen für n = 0, 1, 2, 3, … sind

:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

Eigenschaften

Ein alternativer Ausdruck für C ist

:

der zum Ausdruck gleichwertig ist, der oben weil gegeben ist. Das zeigt, dass C eine Zahl der ganzen Zahl ist, die von der ersten gegebenen Formel nicht sofort offensichtlich ist. Dieser Ausdruck bildet die Basis für einen Beweis der Genauigkeit der Formel.

Die katalanischen Zahlen befriedigen die Wiederauftreten-Beziehung

:

außerdem,

:

Das ist auf Grund dessen, dass seit der Auswahl n Zahlen von 2n der Satz von Zahlen in 2 Teile einzigartig geteilt werden kann: Auswahl von i Zahlen aus den ersten n Zahlen und dann der Auswahl n-i Zahlen von den restlichen n Zahlen.

Sie befriedigen auch:

:

der eine effizientere Weise sein kann, sie zu berechnen.

Asymptotisch wachsen die katalanischen Zahlen als

:

im Sinn, dass der Quotient der n-ten katalanischen Zahl und des Ausdrucks rechts zu 1 als n  +  neigt. (Das kann durch das Verwenden der Annäherung von Stirling für n bewiesen werden.)

Die einzigen katalanischen Zahlen C, die seltsam sind, sind diejenigen für der n = 2  1. Alles sind andere gleich.

Katalanische Zahlen haben integrierte Darstellung

:

wo Es bedeutet, dass katalanische Zahlen Lösung des verallgemeinerten Moment-Problems von Hausdorff sind. Orthogonale Polynome mit dem Gewicht darauf haben eine Form

:

Anwendungen in combinatorics

Es gibt viele Zählen-Probleme in combinatorics, dessen Lösung durch die katalanischen Zahlen gegeben wird. Das Buch Enumerative Combinatorics: Der Band 2 durch combinatorialist Richard P. Stanley enthält eine Reihe von Übungen, die 66 verschiedene Interpretationen der katalanischen Zahlen beschreiben. Folgender ist einige Beispiele, mit Illustrationen der Fälle C = 5 und C = 14.

• C ist die Zahl von Wörtern von Dyck der Länge 2n. Ein Dyck Wort ist eine Schnur, die aus und n solchem Y von n X besteht, dass kein anfängliches Segment der Schnur mehr Y hat als X (sieh auch Sprache von Dyck). Zum Beispiel, der folgende sind die Wörter von Dyck der Länge 6:
• Das Symbol X als eine offene Parenthese und Y als eine nahe Parenthese wiederinterpretierend, zählt C die Zahl von Ausdrücken auf, die n Paare von Parenthesen enthalten, die richtig verglichen werden:
• C ist die Zahl von verschiedenen Wegen n + 1 Faktoren können völlig parenthesized (oder die Zahl von Weisen sein, n Anwendungen eines binären Maschinenbedieners zu vereinigen). Für n = 3, zum Beispiel, haben wir die folgenden fünf verschiedenen parenthesizations von vier Faktoren:
• Aufeinander folgende Anwendungen eines binären Maschinenbedieners können in Bezug auf einen vollen binären Baum vertreten werden. (Ein eingewurzelter binärer Baum ist voll, wenn jeder Scheitelpunkt entweder zwei Kinder oder keine Kinder hat.), Hieraus folgt dass C die Zahl von vollen binären Bäumen mit n + 1 Blätter ist:

Wenn die Blätter etikettiert werden, haben wir die vierfachen factorial Zahlen.

• C ist die Zahl von nichtisomorphen geordneten Bäumen mit n+1 Scheitelpunkten. (Ein geordneter Baum ist ein eingewurzelter Baum, in dem den Kindern jedes Scheitelpunkts eine feste zum Recht nach links Ordnung gegeben wird.)
• C ist die Zahl von monotonischen Pfaden entlang den Rändern eines Bratrostes mit n × n Quadratzellen, die über der Diagonale nicht gehen. Ein monotonischer Pfad ist derjenige, der an der niedrigeren linken Ecke anfängt, an der oberen richtigen Ecke fertig ist, und völlig aus Rändern besteht, die nach rechts oder aufwärts hinweisen. Das Aufzählen solcher Pfade ist zum Zählen von Wörtern von Dyck gleichwertig: X tritt "für Bewegungsrecht" ein, und Y tritt ein "steigen". Die folgenden Diagramme zeigen den Fall n = 4:
• C ist die Zahl von verschiedenen Wegen ein konvexes Vieleck mit n + 2 Seiten können in Dreiecke durch das Anschließen von Scheitelpunkten mit Geraden geschnitten werden. Die folgenden Sechsecke illustrieren den Fall n = 4:
• C ist die Zahl von mit dem Stapel sortierbaren Versetzungen {1..., n}. Eine Versetzung w wird mit dem Stapel sortierbar genannt, wenn S (w) = (1..., n), wo S (w) rekursiv wie folgt definiert wird: Schreiben Sie w = unv, wo n das größte Element in w und u ist und v kürzere Folgen und Satz S (w) = S (u) S (v) n mit S sind die Identität für Ein-Element-Folgen zu sein. Das sind die Versetzungen, die das Muster 231 vermeiden.
• C ist die Zahl von Versetzungen {1..., n}, die das Muster 123 (oder einige der anderen Muster der Länge 3) vermeiden; d. h. die Zahl von Versetzungen ohne zunehmende Drei-Begriffe-Subfolge. Für n = 3 sind diese Versetzungen 132, 213, 231, 312 und 321. Für n = 4 sind sie 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312 und 4321.
• C ist die Zahl von sich nichttreffenden Teilungen des Satzes {1..., n}. Ein fortiori, C überschreitet nie die n-te Zahl von Bell. C ist auch die Zahl von sich nichttreffenden Teilungen des Satzes {1..., 2n}, in dem jeder Block der Größe 2 ist. Die Verbindung dieser zwei Tatsachen kann in einem Beweis durch die mathematische Induktion verwendet werden, dass alle freien cumulants des Grads mehr als 2 des Halbkreis-Gesetzes von Wigner Null sind. Dieses Gesetz ist in der freien Wahrscheinlichkeitstheorie und der Theorie von zufälligem matrices wichtig.
• C ist die Zahl von Weisen, eine stairstep Gestalt der Höhe n mit n Rechtecken mit Ziegeln zu decken. Die folgende Zahl illustriert den Fall n = 4:
• C ist die Zahl des Standards Gemälde von Young, deren Diagramm 2 durch das n Rechteck ist. Mit anderen Worten ist es die Zahl auf Weisen die Nummern 1, 2..., 2n können in 2 durch das n Rechteck eingeordnet werden, so dass jede Reihe und jede Säule zunehmen. Als solcher kann die Formel als ein spezieller Fall der Formel der Haken-Länge abgeleitet werden.
• C ist die Zahl von Weisen, wie die Scheitelpunkte eines konvexen 2n-gon paarweise angeordnet werden können, so dass sich die Liniensegmente, die sich paarweise angeordneten Scheitelpunkten anschließen, nicht schneiden.
• C ist die Zahl von Halbordnungen auf n unetikettierte Sachen.

Beweis der Formel

Es gibt mehrere Weisen, warum die Formel zu erklären

:

behebt die kombinatorischen Probleme, die oben verzeichnet sind. Der erste Beweis verwendet unten eine Erzeugen-Funktion. Die anderen Beweise sind Beispiele von bijektiven Beweisen; sie schließen wörtlich das Zählen einer Sammlung einer Art Gegenstands ein, die richtige Formel zu erreichen.

Der erste Beweis

Wir bemerken zuerst, dass alle kombinatorischen Probleme, die oben verzeichnet sind, die Wiederauftreten-Beziehung von Segner befriedigen

:

Zum Beispiel kann jedes Wort von Dyck w der Länge  2 auf eine einzigartige Weise in der Form geschrieben werden

:w = XwYw

mit (vielleicht leer) Wörter von Dyck w und w.

Die Erzeugen-Funktion für die katalanischen Zahlen wird durch definiert

:

Die zwei Wiederauftreten-Beziehungen können dann zusammen im Erzeugen der Funktionsform durch die Beziehung zusammengefasst werden

:

mit anderen Worten folgt diese Gleichung aus den Wiederauftreten-Beziehungen durch die Erweiterung beider Seiten in die Macht-Reihe. Einerseits bestimmen die Wiederauftreten-Beziehungen einzigartig die katalanischen Zahlen; andererseits, die Erzeugen-Funktionslösung

:

hat eine Macht-Reihe an 0, und seine Koeffizienten müssen deshalb die katalanischen Zahlen sein. (Da die andere Lösung einen Pol an 0 hat, gilt dieses Denken dafür nicht.)

Der Quadratwurzel-Begriff kann als eine Macht-Reihe mit der Identität ausgebreitet werden

:

Das ist ein spezieller Fall des verallgemeinerten binomischen Lehrsatzes von Newton; als mit dem allgemeinen Lehrsatz, wie man beweisen kann, erzeugt es durch Rechenableitungen seine Reihe von Taylor. Wenn sie y = −4x untergeht und diese Macht-Reihe in den Ausdruck für c (x) einsetzt und den Summierungsindex n durch 1 auswechselt, vereinfacht die Vergrößerung zu

:

Die Koeffizienten sind jetzt die gewünschte Formel für C.

Eine andere Weise, c (x) zu bekommen, soll für xc (x) lösen und bemerken, dass das in jedem Begriff der Macht-Reihe erscheint.

Der zweite Beweis

Dieser Beweis hängt von einem als die Nachdenken-Methode von André bekannten Trick ab (um mit dem Nachdenken-Grundsatz von Schwarz in der komplizierten Analyse nicht verwirrt zu sein), der im Zusammenhang mit dem Stimmzettel-Lehrsatz von Bertrand ursprünglich verwendet wurde. Der Nachdenken-Grundsatz ist Désiré André weit zugeschrieben worden, aber seine Methode hat Nachdenken nicht wirklich verwendet; und die Nachdenken-Methode ist eine Schwankung wegen Aeblys und Mirimanoffs. Es wird in Bezug auf die "monotonischen Pfade am leichtesten ausgedrückt, die das diagonale" Problem nicht durchqueren (sieh oben).

Nehmen Sie an, dass uns ein monotonischer Pfad in einem n × n Bratrost gegeben wird, der wirklich die Diagonale durchquert. Finden Sie den ersten Rand im Pfad, der über der Diagonale liegt, und schnipsen Sie den Teil des Pfads, der nach diesem Rand entlang einer Linienparallele zur Diagonale vorkommt. (In Bezug auf Dyck Wörter fangen wir mit einer Folge von und n Y von n X an, der nicht ein Wort von Dyck ist, und den ganzen X mit Y nach dem ersten Y austauschend, der die Bedingung von Dyck verletzt.) Der resultierende Pfad ist ein monotonischer Pfad in (n  1) × (n + 1) Bratrost. Abbildung 1 illustriert dieses Verfahren; der grüne Teil des Pfads ist der Teil, der wird schnipst.

Da jeder monotonische Pfad in (n  1) × (n + 1) Bratrost die Diagonale an einem Punkt durchqueren muss, kann jeder solcher Pfad auf diese Mode auf genau eine Weise erhalten werden. Die Zahl dieser Pfade ist gleich

:

Deshalb, um die Zahl des Monostärkungsmittels n × n Pfade zu berechnen, die die Diagonale nicht durchqueren, müssen wir das von der Gesamtzahl des Monostärkungsmittels n × n Pfade abziehen, so erhalten wir schließlich

:

der die n-te katalanische Nummer C ist.

Der dritte Beweis

Der folgende bijektive Beweis, während er mehr beteiligt wird als der vorherige, stellt eine natürlichere Erklärung für den Begriff n + das 1 Erscheinen im Nenner der Formel für C zur Verfügung.

Nehmen Sie an, dass uns ein monotonischer Pfad gegeben wird, der zufällig die Diagonale durchqueren kann. Der exceedance des Pfads wird definiert, um die Zahl von vertikalen Rändern zu sein, die über der Diagonale liegen. Zum Beispiel, in der Abbildung 2, werden die Ränder, die über der Diagonale liegen, im Rot gekennzeichnet, so ist der exceedance des Pfads 5.

Jetzt, wenn uns ein monotonischer Pfad gegeben wird, dessen exceedance nicht Null ist, dann können wir den folgenden Algorithmus anwenden, um einen neuen Pfad zu bauen, dessen exceedance derjenige weniger ist als derjenige, mit dem wir angefangen haben.

Wenn Sie

• von unten links anfangen, folgen Sie dem Pfad, bis er zuerst über der Diagonale reist.
• Setzen Sie fort, dem Pfad zu folgen, bis er die Diagonale wieder berührt. Zeigen Sie durch X der erste derartige Rand an, der erreicht wird.
• Tauschen Sie den Teil des Pfads, der vorher X mit dem Teil vorkommt, der danach X vorkommt.

Das folgende Beispiel sollte das klarer machen. In der Abbildung 3 zeigt der schwarze Punkt den Punkt an, wo der Pfad zuerst die Diagonale durchquert. Der schwarze Rand ist X, und wir tauschen den roten Teil mit dem grünen Teil, um einen neuen Pfad zu machen, der im zweiten Diagramm gezeigt ist.

Bemerken Sie, dass der exceedance von drei bis zwei gefallen ist. Tatsächlich wird der Algorithmus den exceedance veranlassen, durch einen für jeden Pfad abzunehmen, dass wir es füttern, weil der erste vertikale Schritt, der auf der Diagonale (am Punkt anfängt, der mit einem schwarzen Punkt gekennzeichnet ist), der einzigartige vertikale Rand ist, der unter der Operation von über der Diagonale zu darunter geht; alle anderen vertikalen Ränder bleiben dieselbe Seite der Diagonale länger.

Es ist auch nicht schwierig zu sehen, dass dieser Prozess umkehrbar ist: In Anbetracht jedes Pfads P, dessen exceedance weniger ist als n, gibt es genau einen Pfad, der P nachgibt, wenn der Algorithmus darauf angewandt wird. Tatsächlich ist der (schwarze) Rand X, der ursprünglich der erste horizontale Schritt war, der auf der Diagonale endet, der letzte horizontale Schritt geworden, der auf der Diagonale anfängt.

Das deutet an, dass die Zahl von Pfaden von exceedance n der Zahl von Pfaden von exceedance n  1 gleich ist, der der Zahl von Pfaden von exceedance n  2, und so weiter unten zur Null gleich ist. Mit anderen Worten haben wir den Satz aller monotonischen Pfade in n + 1 ebenso nach Größen geordnete Klassen, entsprechend dem möglichen exceedances zwischen 0 und n aufgeteilt. Da es gibt

:

monotonische Pfade, wir erhalten die gewünschte Formel

:

Abbildung 4 illustriert die Situation für n = 3. Jeder der 20 möglichen monotonischen Pfade erscheint irgendwo im Tisch. Die erste Säule zeigt alle Pfade von exceedance drei, die völlig über der Diagonale liegen. Die Säulen zum Recht zeigen das Ergebnis von aufeinander folgenden Anwendungen des Algorithmus, mit dem exceedance das Verringern einer Einheit auf einmal. Es gibt fünf Reihen, d. h. C = 5.

Der vierte Beweis

Dieser Beweis verwendet die Triangulationsdefinition von katalanischen Zahlen, um eine Beziehung zwischen C und C zu gründen. In Anbetracht eines Vielecks P mit n + 2 Seiten, das erste ein Zeichen seiner Seiten als die Basis. Wenn P dann trianguliert wird, können wir weiter wählen und einen von seinem 2n+1 Ränder orientieren. Es gibt (4n+2) C solche geschmückten Triangulationen. Jetzt in Anbetracht eines Vielecks Q mit n+3 Seiten, wieder ein Zeichen seiner Seiten als die Basis. Wenn Q trianguliert wird, können wir weiteres ein Zeichen der Seiten außer der Grundseite. Es gibt (n+2) C solche geschmückten Triangulationen. Dann gibt es eine einfache Bijektion zwischen diesen zwei Arten von geschmückten Triangulationen: Wir können entweder das Dreieck in Q ohnmächtig werden, dessen Seite gekennzeichnet wird, oder breiten Sie rückwärts den orientierten Rand in P zu einem Dreieck aus und kennzeichnen Sie seine neue Seite. So

:

Die binomische Formel für C folgt sofort von dieser Beziehung und der anfänglichen Bedingung C = 1.

Der fünfte Beweis

Dieser Beweis basiert auf der Wortinterpretation von Dyck der katalanischen Zahlen, so ist C die Zahl von Weisen, n Paare von Klammern richtig zu vergleichen. Wir zeigen (vielleicht leer) richtige Schnur mit c und seinem Gegenteil an (wo" [" und"]" ausgetauscht werden) mit c. Da jeder c in c = [c] c einzigartig zersetzt werden kann, gibt das Resümieren über die möglichen Punkte, um die Schlussklammer zu legen, sofort die rekursive Definition

:

Lassen Sie jetzt b für eine erwogene Schnur der Länge 2n eintreten, eine gleiche Anzahl" [" und"]" und mit einem Faktor d  1 enthaltend. Als oben kann jede erwogene Schnur entweder in [c] b oder in] c [b, so einzigartig zersetzt werden

:

Außerdem fängt jede falsche erwogene Schnur mit c], so an

:Wenn er

die obengenannten Gleichungen und mit B = d abzieht, gibt C

:

Das Vergleichen von Koeffizienten mit der ursprünglichen recursion Formel für C gibt d = ich + 1, so

:

Matrix von Hankel

Die n×n Matrix von Hankel, deren (ich j) Zugang die katalanische Nummer C ist, hat Determinante 1, unabhängig vom Wert von n. Zum Beispiel für n = 4 haben wir

:

Bemerken Sie, dass, wenn die Einträge, nämlich die katalanischen Zahlen C "ausgewechselt" werden, die Determinante noch 1 unabhängig von der Größe von n ist.

Zum Beispiel für n = 4 haben wir

:

Die katalanischen Zahlen bilden die einzigartige Folge mit diesem Eigentum.

Vierfacher factorial

Durch den vierfachen factorial wird gegeben, oder. Das ist die Lösung von etikettierten Varianten des obengenannten combinatorics Probleme. Es ist vom multifactorials völlig verschieden.

Geschichte

Die Folge von Catalan wurde zuerst im 18. Jahrhundert von Leonhard Euler beschrieben, der sich für die Zahl von verschiedenen Weisen interessiert hat, ein Vieleck in Dreiecke zu teilen. Die Folge wird nach Eugène Charles Catalan genannt, der die Verbindung zu parenthesized Ausdrücken während seiner Erforschung der Türme des Hanoier Rätsels entdeckt hat. Der Zählen-Trick für Wörter von Dyck wurde von D. André 1887 gefunden.

1988 ist es in einer Inneren Universität von Mongolei der Technologieveröffentlichung ans Licht gekommen, dass die katalanische Zahl-Folge in China vom mongolischen Mathematiker Minggantu vor 1730 verwendet worden war. Das ist, als er angefangen hat, seinem Buch Ge Yuan Mi Lu Jie Fa zu schreiben, der von seinem Studenten Chen Jixin 1774 vollendet wurde, aber sechzig Jahre später veröffentlicht hat. P.J. Larcombe (1999) hat einige der Eigenschaften der Arbeit von Minggantu einschließlich des Stimulus von Pierre Jartoux skizziert, der drei unendliche Reihen nach China am Anfang der 1700er Jahre gebracht hat.

Zum Beispiel hat Ming die katalanische Folge verwendet, um Reihenentwicklungen der Sünde (2α) und Sünde (4α) in Bezug auf die Sünde (α) auszudrücken.

Siehe auch

• Associahedron
• Der Stimmzettel-Lehrsatz von Bertrand
• Binom gestaltet um
• Das Problem des Katalanen
• Katalanische-Mersenne Zahl
• Liste von factorial und binomischen Themen
• Zahlen von Lobb
• Zahl von Narayana
• Gitter von Tamari

Zeichen

• Conway und Guy (1996) Das Buch von Zahlen. New York: Copernicus, Seiten 96-106.
• Koshy, Thomas & Zhenguang Gao (2011) "Einige Teilbarkeitseigenschaften von katalanischen Zahlen", Mathematical Gazette 95:96-102.
• Larcombe, P.J. (1999) "Die chinesische Entdeckung des 18. Jahrhunderts der katalanischen Zahlen", Mathematisches Spektrum 32:5-7.

Links

• Dickau, Robert M.: Katalanische Zahlen Weitere Beispiele.
• Davis, Tom: Katalanische Zahlen. Noch mehr Beispiele.
• Schmidthammer, Jürgen: Katalanischer-Zahlen Zulassungsarbeit zum Staatsexamen (PDF-Datei; 7,05 Mb)
• "Gleichwertigkeit von drei katalanischen Zahl-Interpretationen" aus dem Wolfram-Demonstrationsprojekt

http://demonstrations.wolfram.com/EquivalenceOfThreeCatalanNumberInterpretations/