Driehoekige reeks - Triangular array
In wiskunde en computers is een driehoekige reeks getallen, polynomen en dergelijke een dubbel geïndexeerde reeks waarin elke rij slechts zo lang is als de eigen index van de rij. Dat wil zeggen, de i de rij bevat alleen i elementen.
Voorbeelden
Bekende specifieke voorbeelden zijn deze:
- De Bell-driehoek , waarvan de getallen de partities tellen van een set waarin een bepaald element de grootste singleton is
- Catalaanse driehoek , die reeksen haakjes telt waarin geen gesloten haakje ongeëvenaard is
- Euler's driehoek , die permutaties telt met een bepaald aantal stijgingen
- Floyd's driehoek , waarvan de ingangen alle gehele getallen in volgorde zijn
- Hosoya's driehoek , gebaseerd op de Fibonacci-getallen
- Lozanić's driehoek , gebruikt in de wiskunde van chemische verbindingen
- Narayana-driehoek , het tellen van reeksen uitgebalanceerde haakjes met een bepaald aantal verschillende nestings
- De driehoek van Pascal , waarvan de invoer de binominale coëfficiënten zijn
Driehoekige arrays van gehele getallen waarin elke rij symmetrisch is en begint en eindigt met 1, worden soms gegeneraliseerde Pascal-driehoeken genoemd ; voorbeelden zijn de driehoek van Pascal, de Narayana-getallen en de driehoek van Euleriaanse getallen.
Generalisaties
Driehoekige arrays kunnen andere wiskundige waarden bevatten dan getallen; de Bell-polynomen vormen bijvoorbeeld een driehoekige array waarin elke array-invoer een polynoom is.
Er is ook rekening gehouden met arrays waarin de lengte van elke rij toeneemt als een lineaire functie van het rijnummer (in plaats van gelijk te zijn aan het rijnummer).
Toepassingen
Naast de weergave van driehoekige matrices , worden driehoekige arrays in verschillende algoritmen gebruikt . Een voorbeeld is het CYK-algoritme voor het ontleden van contextvrije grammatica's , een voorbeeld van dynamisch programmeren .
De methode van Romberg kan worden gebruikt om de waarde van een bepaalde integraal te schatten door de waarden in een driehoek van getallen in te vullen.
De Boustrophedon-transformatie gebruikt een driehoekige array om de ene gehele reeks in een andere om te zetten.
Zie ook
- Driehoeksgetal , het aantal items in zo'n array tot een bepaalde rij
