Catalan-Zahl

Zahlenfolge in der Mathematik

Die Catalan-Zahlen oder catalanschen Zahlen bilden eine Folge natürlicher Zahlen, die in vielen Problemen der Kombinatorik auftritt und eine ähnlich wichtige Rolle wie die Binomialkoeffizienten oder die Fibonacci-Zahlen spielt. Sie sind nach dem belgischen Mathematiker Eugène Charles Catalan benannt.

Die Catalan-Zahlen zählen beispielsweise die nicht überkreuzenden Partitionen einer Menge mit Elementen, hier (oberer Bildteil), während die Zahl aller Partitionen durch die Bellschen Zahlen angegeben wird, hier

Die Folge der Catalan-Zahlen beginnt mit

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, … (Folge A000108 in OEIS)

Die Catalan-Zahlen sind für gegeben durch

wobei der mittlere Binomialkoeffizient ist. Mit erhält man, dass die Formel äquivalent zu

ist und somit tatsächlich nur ganze Zahlen liefert.

Historisches

Bearbeiten

Als Erster fand der Chinese Minggatu Catalan-Zahlen in seiner Arbeit zu unendlichen Reihen für trigonometrische Funktionen (1730er Jahre als Manuskript zirkulierend, aber erst 1839 als Buch veröffentlicht).

Die Zahlen dieser Folge wurden bereits 1751 von Leonhard Euler in einem Brief an Christian Goldbach beschrieben.[1] Johann Andreas von Segner fand 1758 eine Rekursionsformel,[2] zu der Euler in der Zusammenfassung zu Segners Artikel die Lösung angab.[3] Eine von Johann Friedrich Pfaff gestellte allgemeinere Abzählungsaufgabe löste 1795 Nikolaus Fuss.[4] In den Jahren 1838 und 1839 griffen Gabriel Lamé,[5] Olinde Rodrigues,[6] Jacques Binet[7][8] und Eugène Catalan[9][10] die Fragestellung erneut auf. Eugen Netto führte in seinem 1901 veröffentlichten Lehrbuch der Combinatorik die Zahlen auf Catalan zurück.[11]

Eigenschaften

Bearbeiten

Euler suchte die Anzahl der Möglichkeiten, ein konvexes  -Eck durch Diagonalen in Dreiecke zu zerteilen (Triangulation). Diese Anzahl ist  . Zum Beispiel gibt es für ein Fünfeck fünf mögliche Triangulationen:

 
Für ein Fünfeck gibt es fünf mögliche Triangulationen

Euler gab in seinem Brief an Goldbach 1751 (siehe Historisches) die explizite Formel

 

und die Formel

 

für die erzeugende Funktion an, insbesondere

 

auch als Beschreibung des Wachstumsverhaltens.[1]

Mit der Gammafunktion   gilt:

 

Direkt aus der Formel folgt

 

Es gilt außerdem die Rekursionsformel (Segner 1758)[2]

 

zum Beispiel ist  .

Eine weitere Rekursionsformel ist

 

sowie mit den Motzkin-Zahlen M (Folge A001006 in OEIS)

 

Da alle Primfaktoren von  , siehe Formel, kleiner als   sind und   für   gilt, sind   und   als einzige Catalan-Zahlen auch Primzahlen. Die Formel zeigt auch, dass   durch jede Primzahl zwischen   und   genau einmal teilbar ist und genau dann ungerade ist, wenn   eine Potenz von 2 ist.

Aus dem Satz von Wolstenholme folgt die Kongruenz

 

für jede Primzahl  , für Wolstenholme-Primzahlen gilt die Kongruenz  , für die Primzahlen 2 und 3 gilt sie  .

Insbesondere ist   und   für jede Primzahl   und ganze Zahl  .

Durch Einsetzen der Stirling-Formel erhält man für das asymptotische Verhalten der Catalan-Zahlen

 

Die Summe der Kehrwerte konvergiert:[12]

 

Zudem gilt (Folge A013709 in OEIS 2016):

  sowie
 
  (Wallis-Lambert-Reihe) mit  

Über die Cauchy-Produktformel mit dem Basler Problem ergibt sich daraus (Folge A281070 in OEIS 2017):

 

Interpretationen und Zusammenhänge

Bearbeiten

Die Catalan-Zahlen treten bei zahlreichen Abzählungsaufgaben auf, die graphentheoretisch Abzählungen von Bäumen sind. So ist   die Anzahl der

Zum Beispiel muss man für   eine Zeichenfolge wie   in Klammern setzen, was auf 5 verschiedene Arten möglich ist:
 
Ein explizites Beispiel für die Subtraktion ist
 
Daher ist  . Das Hinzufügen redundanter Klammern um einen bereits in Klammern gesetzten Ausdruck oder um den vollständigen Ausdruck herum ist nicht zulässig. Es gibt einen Binärbaum mit 0 Knoten und jeder andere Binärbaum ist durch die Kombination aus seinem linken und seinem rechten Teilbaum gekennzeichnet. Wenn diese Teilbäume   bzw.   Knoten haben, hat der gesamte Baum   Knoten. Daher hat die Anzahl   von Binärbäumen mit   Knoten die folgende rekursive Beschreibung   und   für jede positive ganze Zahl  . Daraus folgt, dass   die Catalan-Zahl mit Index   ist. Diese ist beispielsweise ein Maß für die Anzahl der möglichen Berechnungsreihenfolgen bei der nichtkommutativen Matrix-Kettenmultiplikation, wo durch geschickt optimierte Klammerung der Rechenaufwand minimiert werden kann.
  • eindimensionalen Irrfahrten von 0 nach   mit Anfangs- und Endpunkt in 0, sodass sich der Pfad nie unterhalb der  -Achse befindet (sogenannte Dyck-Pfade nach Walther von Dyck). Zum Beispiel ist  , denn alle möglichen Pfade sind:
 
  • monotonen Pfade entlang der Ränder eines Quadratgitters mit   quadratischen Zellen, die keinen Punkt oberhalb der Diagonale enthalten. Ein monotoner Pfad beginnt in der unteren linken Ecke, endet in der oberen rechten Ecke und besteht vollständig aus Kanten, die nach rechts oder oben zeigen. Die 14 monotonen Pfade für   sind:[13]
 
  • Möglichkeiten, eine Stufenform der Breite   und Höhe   mit   Rechtecken zu kacheln. Die 14 Möglichkeiten für   sind:[13]
 
  • möglichen Verläufe der Auszählung bei einer Wahl, bei denen Kandidat A nach jeder gezählten Stimme nie hinter Kandidat B liegt, wenn beide Kandidaten je   Stimmen erhalten und die Stimmzettel nacheinander aus der Urne geholt und gezählt werden. Beispielsweise für   wären die möglichen Ziehungsfolgen, die die Voraussetzung erfüllen, ABAB und AABB.[14]
  • Möglichkeiten, wie sich   Personen, die an einem runden Tisch sitzen, paarweise über den Tisch die Hand geben, ohne dass sich Arme überkreuzen.[14]

Literatur

Bearbeiten
Bearbeiten
Commons: Catalan-Zahlen – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

Bearbeiten
  1. a b Brief (PDF; 137 kB) von Euler an Goldbach vom 4. September 1751, abgedruckt in Paul Heinrich Fuss (Hrsg.): Correspondance mathématique et physique de quelques célèbres géomètres du XVIIIème siècle. (Band 1), St.-Pétersbourg 1843, S. 549–552.
  2. a b Ioh. Andr. de Segner: Enumeratio modorum quibus figurae planae rectilineae per diagonales dividuntur in triangula. Novi commentarii academiae scientiarum imperialis petropolitanae 7 pro annis 1758 et 1759, 1761, S. 203–210 (lateinisch).
  3. Leonhard Euler: Summarium dissertationum. Novi commentarii academiae scientiarum imperialis petropolitanae 7 pro annis 1758 et 1759, 1761, S. 13–15 (lateinisch).
  4. Nicolao Fuss: Solutio quaestionis, quot modis polygonum n laterum in polygona m laterum, per diagonales resolvi queat. Nova acta academiae scientiarum imperialis petropolitanae 9, 1795, S. 243–251 (lateinisch).
  5. Gabriel Lamé: Extrait d’une lettre de M. Lamé à M. Liouville sur cette question: Un polygone convexe étant donné, de combien de manières peut-on le partager en triangles au moyen de diagonales? Journal de mathématiques pures et appliquées 3, 1838, S. 505–507 (französisch).
  6. Olinde Rodrigues: Sur le nombre de manières de décomposer un polygone en triangles au moyen de diagonales und Sur le nombre de manières d’effectuer un produit de n facteurs. Journal de mathématiques pures et appliquées 3, 1838, S. 547–549 (französisch).
  7. J. Binet: Problèmes sur les polygones. Société philomathique de Paris – Séances de 1838 – Extraits des procès-verbaux, S. 127–129 (französisch).
  8. J. Binet: Réflexions sur le problème de déterminer le nombre de manières dont une figure rectiligne peut être partagée en triangles au moyen de ses diagonales. Journal de mathématiques pures et appliquées 4, 1839, S. 79–90 (französisch).
  9. a b E. Catalan: Note sur une équation aux différences finies. Journal de mathématiques pures et appliquées 3, 1838, S. 508–516, und 4, 1838, S. 95–99 (französisch).
  10. E. Catalan: Solution nouvelle de cette question: Un polygone étant donné, de combien de manières peut-on le partager en triangles au moyen de diagonales? Journal de mathématiques pures et appliquées 4, 1839, S. 91–94 (französisch).
  11. Eugen Netto: Lehrbuch der Combinatorik. B. G. Teubner, Leipzig 1901 (Zurückführung der Zahlen auf Catalan in § 122, S. 192–194 und § 124, S. 195).
  12. whole sum of the reciprocal Catalan numbers. Bei: juanmarqz.wordpress.com. 29. Juli 2009, abgerufen am 11. Januar 2021.
  13. a b Matej Crepinsek, Luka Mernik: An efficient representation for solving Catalan number related problems. (PDF; 253 kB). In: ijpam.eu. International Journal of Pure and Applied Mathematics, abgerufen am 11. Januar 2021.
  14. a b Doina Logofătu: Algorithmen und Problemlösungen mit C++. Kapitel 8 Catalan-Zahlen. Vieweg-Verlag, 1. Auflage 2006, ISBN 978-3-8348-0126-5, S. 189–206.