Tablica trójkątna
W matematyce i informatyce trójkątna tablica liczb, wielomianów itp. jest podwójnie indeksowaną sekwencją, w której każdy wiersz ma długość tylko taką, jak jego własny indeks. Oznacza to, że i- ty wiersz zawiera tylko i elementy.
Przykłady
Godne uwagi konkretne przykłady obejmują:
- Trójkąt Bella , którego liczby zliczają partycje zbioru , w którym dany element jest największym singletonem
- Trójkąt kataloński , który zlicza ciągi nawiasów, w których żaden zamykający nawias nie jest niedopasowany
- Trójkąt Eulera , który zlicza permutacje z określoną liczbą wzniesień
- Trójkąt Floyda , którego wpisy to wszystkie liczby całkowite w kolejności
- Trójkąt Hosoyi oparty na liczbach Fibonacciego
- Trójkąt Lozanića , używany w matematyce związków chemicznych
- Trójkąt Narayana , licząc ciągi zrównoważonych nawiasów z określoną liczbą różnych zagnieżdżeń
- Trójkąt Pascala , którego wpisami są współczynniki dwumianowe
Trójkątne tablice liczb całkowitych, w których każdy wiersz jest symetryczny oraz zaczyna się i kończy na 1, są czasami nazywane uogólnionymi trójkątami Pascala ; przykłady obejmują trójkąt Pascala, liczby Narayana i trójkąt liczb Eulera.
Uogólnienia
Tablice trójkątne mogą zawierać wartości matematyczne inne niż liczby; na przykład wielomiany Bella tworzą trójkątną tablicę, w której każdy element tablicy jest wielomianem.
Rozważono również tablice, w których długość każdego wiersza rośnie jako funkcja liniowa numeru wiersza (a nie równa numerowi wiersza).
Aplikacje
Oprócz reprezentacji macierzy trójkątnych , tablice trójkątne są wykorzystywane w kilku algorytmach . Jednym z przykładów jest algorytm CYK do analizowania gramatyk bezkontekstowych , przykład programowania dynamicznego .
Metodę Romberga można wykorzystać do oszacowania wartości całki oznaczonej poprzez uzupełnienie wartości w trójkącie liczb.
Transformacja Boustrophedona wykorzystuje trójkątną tablicę do przekształcenia jednej sekwencji liczb całkowitych w inną.
Zobacz też
- Liczba trójkątna , liczba wpisów w takiej tablicy do pewnego określonego wiersza