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 est aussi longue que son ordre.

Construction du triangle de Bell.

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 de rang $n$ est alors le $n$ + 1-uplet $(T_{n,0},...,T_{n,n})$ , et la colonne de rang $k$ est la suite $(T_{n,k})_{n\geqslant 0}$ .

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 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 d'Hosoya (en), basé sur les nombres de Fibonacci[5].
Le triangle harmonique de Leibniz.
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.
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].

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[10].

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[11].

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[12].

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

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

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).
(en) Daniel C. Fielder et Cecil O. Alford, « Pascal's triangle: Top gun or just one of the gang? », dans Applications of Fibonacci Numbers, vol. 4 : (Proceedings of The Fourth International Conference on Fibonacci Numbers and Their Applications, Wake Forest University, N.C., U.S.A., July 30–August 3, 1990), Kluwer Academics Publisher, 313 p. (ISBN 978-0-7923-1309-0, lire en ligne), p. 77-90.
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)

Portail des mathématiques
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons – Attribution – Partage à l’identique. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.

[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] (en) Daniel C. Fielder et Cecil O. Alford, « Pascal's triangle: Top gun or just one of the gang? », dans Applications of Fibonacci Numbers, vol. 4 : (Proceedings of The Fourth International Conference on Fibonacci Numbers and Their Applications, Wake Forest University, N.C., U.S.A., July 30–August 3, 1990), Kluwer Academics Publisher, 313 p. (ISBN 978-0-7923-1309-0, lire en ligne), p. 77-90.

[11] 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.

[12] 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).

[13] 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)