Tableau triangulaire
![](http://upload.wikimedia.org/wikipedia/commons/0/02/Triangle_de_Bell.gif)
En mathématiques et en informatique, un tableau triangulaire de nombres, ou de polynômes est une suite doublement indexée dans laquelle chaque ligne a une longueur proportionnelle à son ordre.
Présentation
Présentation matricielle
Dans de nombreux cas, il s'agit d'une suite définie pour les entiers vérifiant .
La ligne d'indice n (d'ordre ) est alors le -uplet , et la colonne d'indice k (d'ordre ) est la suite .
k n | 0 | 1 | 2 |
---|---|---|---|
0 | |||
1 | |||
2 | etc. |
La suite peut plus généralement être définie pour d'autres valeurs de que celles vérifiant , voir par exemple le triangle trinomial.
Présentation pyramidale
Les lignes sont présentées de façon symétrique par rapport à leur centre, comme par exemple ci-dessous :
- Triangle de Pascal
- Triangle de Delannoy
- Triangle trinomial
Les "colonnes" sont alors parallèles au côté gauche.
Exemples
Parmi les exemples notables, on peut citer :
- Le triangle de Bell, dont les termes dénombrent certaines partitions d'un ensemble[1].
- Le triangle de Bernoulli, donnant les sommes partielles des lignes du triangle de Pascal.
- Le triangle du boustrophédon permettant d'obtenir les développements de fonctions tangente et sécante.
- Le triangle de Catalan[2].
- le triangle de Delannoy.
- Le triangle des dérangements partiels.
- Le triangle d'Euler, dont les termes dénombrent les permutations avec un certain nombre de montées[3].
- Le triangle fibonomial.
- Le triangle de Floyd (en), dont les entrées sont les entiers dans l'ordre[4].
- Le triangle harmonique de Leibniz.
- Le triangle d'Hosoya (en), basé sur les nombres de Fibonacci[5].
- Le triangle des nombres hyperoctaédriques.
- Le triangle de Lozanić (en), utilisé dans les mathématiques des composés chimiques[6].
- Le triangle de Narayana[7].
- Le triangle du nombre de partitions d'un entier en k parties
- Le triangle de Pascal, dont les entrées sont les coefficients binomiaux[8].
- Le triangle de Pascal (2,1).
- Le q-analogue du triangle de Pascal.
- Le triangle de Rascal
- Le triangle trinomial (où la longueur de chaque ligne est le double de son ordre moins 1)
- Les triangles des nombres de Stirling (de première et deuxième espèce).
Généralisations
Les tableaux triangulaires peuvent énumérer des objets mathématiques autres que des nombres ; par exemple, les polynômes de Bell forment un tableau triangulaire dans lequel chaque entrée est un polynôme[9].
Une suite triplement indexée peut être représentée en tétraèdre, comme par exemple le tétraèdre de Pascal, et une suite à d indices, représentée par un d-simplexe.
Applications
Outre la représentation des matrices triangulaires, les tableaux triangulaires sont utilisés dans plusieurs algorithmes. Un exemple est l'algorithme CYK pour l'analyse de grammaires non-contextuelles, un exemple de programmation dynamique[10].
La méthode de Romberg peut être utilisée pour estimer la valeur d'une intégrale définie en remplissant les valeurs dans un triangle de nombres[11].
La transformation du Boustrophédon utilise un tableau triangulaire pour transformer une suite d'entiers en une autre[12].
Articles connexes
Références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Triangular array » (voir la liste des auteurs).
- ↑ Jeffrey Shallit, A collection of manuscripts related to the Fibonacci sequence, Santa Clara, Calif., Fibonacci Association, , 69–71 p. (MR 624091, lire en ligne), « A triangle for the Bell numbers ».
- ↑ Sergey Kitaev et Jeffrey Liese, « Harmonic numbers, Catalan's triangle and mesh patterns », Discrete Mathematics, vol. 313, , p. 1515–1531 (DOI 10.1016/j.disc.2013.03.017, MR 3047390).
- ↑ Daniel J. Velleman et Gregory S. Call, « Permutations and combination locks », Mathematics Magazine, vol. 68, , p. 243–253 (DOI 10.2307/2690567, MR 1363707).
- ↑ Philip L. Miller, Lee W. Miller et Purvis M. Jackson, Programming by Design : A First Course in Structured Programming, Wadsworth Pub. Co., , 567 p. (ISBN 978-0-534-08244-4)
- ↑ Haruo Hosoya, « Fibonacci triangle », The Fibonacci Quarterly, vol. 14, , p. 173–178.
- ↑ S. M. Losanitsch, « Die Isomerie-Arten bei den Homologen der Paraffin-Reihe », Chemische Berichte, vol. 30, , p. 1917–1926 (DOI 10.1002/cber.189703002144)
- ↑ Paul Barry, « On a generalization of the Narayana triangle », Journal of Integer Sequences, vol. 14, , Article 11.4.5, 22 (MR 2792161).
- ↑ A. W. F. Edwards, Pascal's Arithmetical Triangle : The Story of a Mathematical Idea, JHU Press, , 202 p. (ISBN 978-0-8018-6946-4, lire en ligne).
- ↑ Samuel Rota Bulò, Edwin R. Hancock, Furqan Aziz et Marcello Pelillo, « Efficient computation of Ihara coefficients using the Bell polynomial recursion », Linear Algebra and its Applications, vol. 436, , p. 1436–1441 (DOI 10.1016/j.laa.2011.08.017, MR 2890929).
- ↑ Nitin Indurkhya (dir.) et Fred J. Damerau (dir.), Handbook of Natural Language Processing, Second Edition, CRC Press, , 704 p. (ISBN 978-1-4200-8593-8, lire en ligne), p. 65.
- ↑ Henry C. Thacher, Jr., « Remark on Algorithm 60 : Romberg integration », Communications of the ACM, vol. 7, , p. 420–421 (DOI 10.1145/364520.364542, lire en ligne).
- ↑ Jessica Millar, N. J. A. Sloane et Neal E. Young, « A new operation on sequences : the Boustrouphedon transform », Journal of Combinatorial Theory, vol. 76, , p. 44–54 (DOI 10.1006/jcta.1996.0087, arXiv math.CO/0205218)
Portail des mathématiques
Portail de l'informatique théorique