Tableau triangulaire

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.

Construction du triangle de Bell.

Présentation

Présentation matricielle

Dans de nombreux cas, il s'agit d'une suite $(T_{n,k})$ définie pour les entiers $n,k$ vérifiant $0\leqslant k\leqslant n$.

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

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

La suite $(T_{n,k})$ peut plus généralement être définie pour d'autres valeurs de $k$ que celles vérifiant $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.
• Le triangle de Bernoulli, donnant les sommes partielles des lignes du triangle de Pascal.
• Le triangle de Catalan.
• 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.
• Le triangle fibonomial.
• Le triangle de Floyd (en), dont les entrées sont les entiers dans l'ordre.
• Le triangle d'Hosoya (en), basé sur les nombres de Fibonacci.
• Le triangle harmonique de Leibniz.
• Le triangle de Lozanić (en), utilisé dans les mathématiques des composés chimiques.
• Le triangle de Narayana.
• Le triangle du nombre de partitions d'un entier en k parties
• Le triangle de Pascal, dont les entrées sont les coefficients binomiaux.
• 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.

Des tableaux triangulaires dans lesquels la longueur de chaque ligne augmente de manière linéaire par rapport au numéro de la ligne (au lieu d' y être égale) ont également été considérés.

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.

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.

La transformation du Boustrophédon utilise un tableau triangulaire pour transformer une suite d'entiers en une autre.

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