En mathématiques et en informatique, un tableau triangulaire de nombres, ou de polynômes est une suite doublement indexée présentée dans un tableau où chaque ligne a une longueur proportionnelle à son rang.
Définition et présentations
modifierLe tableau peut être défini mathématiquement par une suite double , les entiers vérifiant en général ; mais il peut y avoir des variantes, voir par exemple le triangle trinomial.
Présentation en escalier
modifierk n
|
0 | 1 | 2 |
|---|---|---|---|
| 0 | |||
| 1 | |||
| 2 |
La ligne d'indice n (qui est la -ième) est alors le -uplet , et la colonne d'indice k (qui est la -ième) est la suite .
Présentation pyramidale, ou "en quinconce"
modifierLes lignes sont alors présentées de façon symétrique par rapport à leur centre :
Les "colonnes" du cas précédent sont alors les rangées parallèles au bord gauche.
Exemples
modifierParmi 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, dont les entrées sont les entiers dans l'ordre[4].
- Le triangle harmonique de Leibniz.
- Le triangle de Hosoya, basé sur les nombres de Fibonacci[5].
- Le triangle des nombres hyperoctaédriques.
- Le triangle de Lah.
- Le triangle de Lozanić (en), utilisé dans les mathématiques des composés chimiques[6].
- Le triangle de Narayana[7].
- Le triangle des nombres 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 de nombres associé à la conjecture de Proth-Gilbreath
- Le triangle des nombres de surjections.
- Les triangles des nombres de Stirling (de première et deuxième espèce).
- Le triangle trinomial (où la longueur de chaque ligne est le double de son ordre moins 1).
Généralisations
modifierLes 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 à indices, représentée par un d-simplexe.
Applications
modifierOutre 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
modifierRéférences
modifier- (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, 1980, 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, 28 juillet 2013, 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, octobre 1995, 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., 1987, 567 p. (ISBN 978-0-534-08244-4)
- ↑ Haruo Hosoya, « Fibonacci triangle », The Fibonacci Quarterly, vol. 14, 1976, p. 173–178.
- ↑ S. M. Losanitsch, « Die Isomerie-Arten bei den Homologen der Paraffin-Reihe », Chemische Berichte, vol. 30, 1897, p. 1917–1926 (DOI 10.1002/cber.189703002144)
- ↑ Paul Barry, « On a generalization of the Narayana triangle », Journal of Integer Sequences, vol. 14, 2011, Article 11.4.5, 22 (MR 2792161).
- ↑ A. W. F. Edwards, Pascal's Arithmetical Triangle : The Story of a Mathematical Idea, JHU Press, 2002, 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, 2012, 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, 2010, 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, juillet 1964, 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, 1996, p. 44–54 (DOI 10.1006/jcta.1996.0087, arXiv math.CO/0205218)
