Dreieckige Anordnung - Triangular array
In Mathematik und Informatik ist eine dreieckige Anordnung von Zahlen, Polynomen oder dergleichen eine doppelt indizierte Folge, in der jede Zeile nur so lang ist wie der eigene Index der Zeile. Das heißt, die i- te Zeile enthält nur i- Elemente.
Beispiele
Bemerkenswerte besondere Beispiele umfassen diese:
- Das Bell-Dreieck , dessen Zahlen die Partitionen einer Menge zählen, in der ein bestimmtes Element der größte Singleton ist
- Katalanisches Dreieck , das Klammerfolgen zählt, in denen keine enge Klammer unübertroffen ist
- Eulers Dreieck , das Permutationen mit einer bestimmten Anzahl von Aufstiegen zählt
- Floyds Dreieck , dessen Einträge alle ganzen Zahlen der Reihe nach sind
- Hosoyas Dreieck , basierend auf den Fibonacci-Zahlen
- Lozanićs Dreieck , das in der Mathematik chemischer Verbindungen verwendet wird
- Narayana-Dreieck , das Zeichenfolgen in ausgeglichenen Klammern mit einer bestimmten Anzahl unterschiedlicher Verschachtelungen zählt
- Pascals Dreieck , dessen Einträge die Binomialkoeffizienten sind
Dreieckige Anordnungen von ganzen Zahlen, in denen jede Zeile symmetrisch ist und mit 1 beginnt und endet, werden manchmal als verallgemeinerte Pascal-Dreiecke bezeichnet . Beispiele hierfür sind das Pascalsche Dreieck, die Narayana-Zahlen und das Dreieck der Eulerschen Zahlen.
Verallgemeinerungen
Dreieckige Arrays können andere mathematische Werte als Zahlen auflisten. Beispielsweise bilden die Bell-Polynome ein dreieckiges Array, in dem jeder Array-Eintrag ein Polynom ist.
Arrays, bei denen die Länge jeder Zeile als lineare Funktion der Zeilennummer wächst (anstatt gleich der Zeilennummer zu sein), wurden ebenfalls berücksichtigt.
Anwendungen
Neben der Darstellung dreieckiger Matrizen werden dreieckige Arrays in mehreren Algorithmen verwendet . Ein Beispiel ist der CYK-Algorithmus zum Parsen kontextfreier Grammatiken , ein Beispiel für dynamische Programmierung .
Rombergs Methode kann verwendet werden, um den Wert eines bestimmten Integrals zu schätzen, indem die Werte in einem Dreieck von Zahlen vervollständigt werden.
Die Boustrophedon-Transformation verwendet ein dreieckiges Array, um eine ganzzahlige Sequenz in eine andere zu transformieren .
Siehe auch
- Dreieckszahl , die Anzahl der Einträge in einem solchen Array bis zu einer bestimmten Zeile