Tableau triangulaire

Construction du triangle de Bell.

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 ${\displaystyle (T_{n,k})}$ définie pour les entiers ${\displaystyle n,k}$ vérifiant ${\displaystyle 0\leqslant k\leqslant n}$.

La ligne d'indice n (d'ordre ${\displaystyle n+1}$) est alors le ${\displaystyle n+1}$-uplet ${\displaystyle (T_{n,0},...,T_{n,n})}$, et la colonne d'indice k (d'ordre ${\displaystyle k+1}$) est la suite ${\displaystyle (T_{n,k})_{n\geqslant 0}}$.

k n	0	1	2
0	${\displaystyle T_{0,0}}$
1	${\displaystyle T_{1,0}}$	${\displaystyle T_{1,1}}$
2	etc.

La suite ${\displaystyle (T_{n,k})}$ peut plus généralement être définie pour d'autres valeurs de ${\displaystyle k}$ que celles vérifiant ${\displaystyle 0\leqslant k\leqslant n}$, 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 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 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

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

• Nombre triangulaire

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).

1. 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 ».
2. 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).
3. 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).
4. 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)
5. Haruo Hosoya, « Fibonacci triangle », The Fibonacci Quarterly, vol. 14,‎ 1976, p. 173–178.
6. 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)
7. Paul Barry, « On a generalization of the Narayana triangle », Journal of Integer Sequences, vol. 14,‎ 2011, Article 11.4.5, 22 (MR 2792161).
8. 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).
9. 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).
10. 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.
11. 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).
12. 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)