Triangle de Floyd

Le triangle de Floyd est un tableau triangulaire d'entiers naturels utilisé en enseignement de l'informatique, portant le nom du chercheur en informatique Robert Floyd. Il présente les entiers strictement positifs dans l'ordre, chaque ligne comportant un terme de plus que la précédente.

Présenté en escalier :

Présenté en pyramide :

Le problème de l'écriture d'un programme informatique pour produire ce triangle a été fréquemment utilisé comme exercice ou exemple pour les programmeurs informatiques débutants, couvrant les concepts de formatage de texte et de constructions de boucles simples^[1].

Le triangle de Floyd peut être défini par la suite double ${\displaystyle (F_{n,k})}$ définie par ${\displaystyle F_{n,k}=1+2+\cdots +(n-1)+k={\frac {n(n-1)}{2}}+k=T_{n-1}+k}$, pour ${\displaystyle 1\leqslant k\leqslant n}$ ; les ${\displaystyle T_{n}}$ sont les nombres triangulaires.

• La ligne ${\displaystyle n}$ est obtenue en ajoutant ${\displaystyle n-1}$ à la ligne précédente (${\displaystyle F_{n,k}=F_{n-1,k}+n-1}$) et en complétant par le successeur du dernier terme.
• Les nombres situés sur le bord gauche forment la suite du traiteur paresseux (nombres triangulaires augmentés de 1) : ${\displaystyle F_{n,1}=T_{n-1}+1}$ ; ceux du bord droit forment la suite des nombres triangulaires : ${\displaystyle F_{n,n}=T_{n}}$.
• Les termes centraux des lignes impaires sont les nombres carrés centrés, sommes de deux carrés consécutifs : ${\displaystyle F_{2n-1,n}=T_{2n-2}+n=2n^{2}-2n+1=(n-1)^{2}+n^{2}}$, en rouge dans la figure ci-contre.
• La somme des termes de la ligne ${\displaystyle n}$ est égale à ${\displaystyle nT_{n-1}+T_{n}={\frac {n(n^{2}+1)}{2}}}$, constante du carré magique normal n × n (suite A006003 de l'OEIS).

• La somme des termes des ${\displaystyle n}$ premières lignes est égale à ${\displaystyle 1+2+\cdots +T_{n}=T_{T_{n}}=n(n+1)(n^{2}+n+2)/8}$, nombre doublement triangulaire : suite A002817 de l'OEIS.

Même construction que le précédent, mais le triangle ne présente que les entiers impairs. Il a été par exemple considéré par Charles Wheatstone en 1856^[2].

Présenté en escalier :

Présenté en pyramide :

Ce triangle peut être défini par la suite double ${\displaystyle (W_{n,k})}$ définie par ${\displaystyle W_{n,k}=n^{2}-n+2k-1=2T_{n-1}+2k-1=2F_{n,k}-1}$, pour ${\displaystyle 1\leqslant k\leqslant n}$.

Il est répertorié comme suite A176271 de l'OEIS.

• La ligne ${\displaystyle n}$ est obtenue en ajoutant ${\displaystyle 2(n-1)}$ à la ligne précédente (${\displaystyle W_{n,k}=W_{n-1,k}+2(n-1)}$) et en complétant par le dernier terme augmenté de 2.
• Les nombres situés sur le bord gauche sont les nombres polygonaux centraux : ${\displaystyle W_{n,1}=n^{2}-(n-1)}$, suite A002061 de l'OEIS ; ceux du bord droit : ${\displaystyle W_{n,n}=n^{2}+n-1}$, suite A028387 de l'OEIS.
• Les termes centraux des lignes impaires sont les nombres carrés impairs : ${\displaystyle W_{2n-1,n}=(2n-1)^{2}}$.
• La somme des termes de la ligne ${\displaystyle n}$ est égale à ${\displaystyle n{\frac {n^{2}-(n-1)+n^{2}+n-1)}{2}}=n^{3}}$

• La somme des termes des ${\displaystyle n}$ premières lignes est égale à ${\displaystyle 1+3+5+\cdots +(n^{2}+n-1)=\left({\frac {n^{2}+n}{2}}\right)^{2}}$ (somme d'impairs consécutifs), mais aussi, d'après ce qui précède, égale à ${\displaystyle 1^{3}+2^{3}+3^{3}+\cdots +n^{3}}$ ; ceci constitue la démonstration de Wheatstone de la formule de Nicomaque.

Ce triangle présente tous les entiers à partir de 1, avec deux termes de plus à chaque ligne.

Présenté en escalier :

Présenté en pyramide :

Ce triangle peut être défini par la suite double ${\displaystyle (V_{n,k})}$ définie par ${\displaystyle V_{n,k}=(n-1)^{2}+k}$, pour ${\displaystyle 1\leqslant k\leqslant 2n-1}$.

• La ligne ${\displaystyle n}$ est obtenue en ajoutant ${\displaystyle 2n-3}$ à la ligne précédente (${\displaystyle V_{n,k}=V_{n-1,k}+2n-3}$) et en complétant par les deux successeurs du dernier terme.
• Les nombres situés sur le bord gauche sont les carrés augmenté de 1 : ${\displaystyle V_{n,1}=(n-1)^{2}+1}$ ; ceux du bord droit les carrés : ${\displaystyle V_{n,n}=n^{2}}$.
• Les termes centraux sont les nombres polygonaux centraux : ${\displaystyle V_{n,n}=(n-1)^{2}+n=n^{2}-n+1}$, suite A002061 de l'OEIS.
• La somme des termes de la ligne ${\displaystyle n}$ est égale à ${\displaystyle (2n-1)(n^{2}-n+1)=n^{3}+(n-1)^{3}}$, nombre cubique centré (suite A005898 de l'OEIS).

• La somme des termes des ${\displaystyle n}$ premières lignes est égale à ${\displaystyle 1+2+\cdots +n^{2}=T_{n^{2}}=n^{2}(n^{2}+1)/2}$ : suite A037270 de l'OEIS ; elle est aussi égale d'après ce qui précède à ${\displaystyle 2\sum _{k=1}^{n}k^{3}-n^{3}}$, ce qui donne ${\displaystyle \sum _{k=1}^{n}k^{3}=(T_{n^{2}}+n^{3})/2=n^{2}(n+1)^{2}/4.}$

• Tableau triangulaire

• [vidéo] Foxxpy - Mathématiques et algorithmie, « Triangle de Floyd », sur YouTube, 2022

• Portail des mathématiques
• Portail de l’informatique