Triangle trinomial

En mathématiques, le triangle trinomial est un tableau triangulaire de nombres entiers, constituant une généralisation du triangle de Pascal, étudié en particulier par Euler en 1767^[1].

Le triangle trinomial sous la main d'Euler^[1].

Présenté comme ci-dessous, partant du 1 situé en haut, chaque terme est la somme de trois termes de la ligne précédente (au lieu de deux pour le triangle de Pascal) : celui situé juste au dessus, celui situé au dessus à gauche (considéré comme nul s'il n'existe pas), et celui situé au dessus à droite (considéré comme nul s'il n'existe pas).

${\displaystyle {\begin{matrix}&&&&1\\&&&1&1&1\\&&1&2&3&2&1\\&1&3&6&7&6&3&1\\1&4&10&16&19&16&10&4&1\end{matrix}}}$

Les coefficients lus ligne par ligne forment la suite A027907 de l'OEIS.

Définition formelle

Les termes de la ligne d'indice ${\displaystyle n}$ étant notés :

${\displaystyle {n \choose k}_{2}}$ pour ${\displaystyle k}$ entier quelconque,

les coefficients du triangle trinomial peuvent être générés à l'aide de la formule de récurrence suivante :

${\displaystyle {0 \choose 0}_{2}=1}$,${\displaystyle {n \choose k}_{2}=0}$ pour ${\displaystyle \ k<0}$ et ${\displaystyle \ k>2n}$,

${\displaystyle {n \choose k}_{2}={n-1 \choose k}_{2}+{n-1 \choose k-1}_{2}+{n-1 \choose k-2}_{2}}$ pour ${\displaystyle n\geqslant 1}$.

Les seuls coefficients non nuls de la ligne d'indice ${\displaystyle n}$ sont les ${\displaystyle 2n+1}$ ${\displaystyle {n \choose k}_{2}}$pour ${\displaystyle k}$ allant de ${\displaystyle 0}$ à ${\displaystyle 2n}$.

k n	0	1	2	3	4	5	6	7	8
0	1
1	1	1	1
2	1	2	3	2	1
3	1	3	6	7	6	3	1
4	1	4	10	16	19	16	10	4	1

Propriétés

• ${\displaystyle {\binom {n}{0}}_{2}={\binom {n}{2n}}_{2}=1}$, ${\displaystyle {\binom {n}{1}}_{2}={\binom {n}{2n-1}}_{2}=n}$.

• Symétrie d'une ligne par rapport à son centre :

${\displaystyle {n \choose k}_{2}={n \choose 2n-k}_{2}}$

• La ligne d'indice ${\displaystyle n}$ est formée des coefficients du trinôme ${\displaystyle 1+X+X^{2}}$ élevé à la puissance ${\displaystyle n}$ :

${\displaystyle \left(1+X+X^{2}\right)^{n}=\sum _{k=0}^{2n}{n \choose k}_{2}X^{k}}$

Le triangle trinomial peut se construire à partir de la pyramide de Pascal.${\displaystyle {\begin{matrix}&&&&1\\&&&1&1&1\\&&1&2&3&2&1\\&1&3&6&7&6&3&1\\1&4&10&16&19&16&10&4&1\end{matrix}}}$

• La relation de récurrence sur les ${\displaystyle {n \choose k}_{2}}$ peut se voir en écrivant que$${\displaystyle (1+X+X^{2})^{n}=(1+X+X^{2})^{n-1}+X(1+X+X^{2})^{n-1}+X^{2}(1+X+X^{2})^{n-1}}$$
• D'après la formule du trinôme : ${\displaystyle (1+X+Y)^{n}=\sum _{0\leqslant i,j\leqslant n}{\binom {n}{i,j,n-i-j}}X^{i}Y^{j}}$ où $${\displaystyle {\binom {n}{i,j,n-i-j}}={\frac {n!}{i!j!(n-i-j)!}}={\binom {n}{i}}{\binom {n-i}{j}}={\binom {n}{j}}{\binom {n-j}{i}},}$$

on obtient la relation :

${\displaystyle {n \choose k}_{2}=\sum _{\textstyle {0\leqslant i,j\leqslant n \atop i+2j=k}}{\binom {n}{i,j,n-i-j}}}$ (voir la traduction géométrique ci-contre), ou ${\displaystyle {n \choose k}_{2}=\sum _{\max(0,k-n)\leqslant j\leqslant k/2}{\binom {n}{k-2j}}{\binom {n-k+2j}{j}}=\sum _{\max(0,k-n)\leqslant j\leqslant k/2}{\binom {n}{j}}{\binom {n-j}{k-2j}}}$.

La relation de récurrence sur les ${\displaystyle {n \choose k}_{2}}$ peut se déduire de la relation de récurrence sur les coefficients de la pyramide de Pascal : $${\displaystyle {n \choose i,j,k}={n-1 \choose i-1,j,k}+{n-1 \choose i,j-1,k}+{n-1 \choose i,j,k-1}.}$$

• La somme des éléments de la ligne d'indice ${\displaystyle n}$ est égale à ${\displaystyle (1+1+1)^{n}=3^{n}}$.
• Les diagonales ont des propriétés intéressantes en relation avec les nombres triangulaires.

Coefficients trinomiaux centraux

Les coefficients trinomiaux centraux ${\displaystyle {n \choose n}_{2}}$ :

1, 1, 3, 7, 19, 51, 141, 393, 1107, 3139,… (suite A002426 de l'OEIS)

ont été étudiés par Euler^[1].

Ils s'expriment par les formules :

${\displaystyle {n \choose n}_{2}=\sum _{0\leqslant k\leqslant n/2}{\frac {n(n-1)\cdots (n-2k+1)}{(k!)^{2}}}=\sum _{0\leqslant k\leqslant n/2}{n \choose 2k}{2k \choose k}=\sum _{0\leqslant k\leqslant n/2}{n \choose k}{n-k \choose k}}$.

On a aussi : ${\displaystyle {n \choose n}_{2}=(\operatorname {i} {\sqrt {3}})^{n}L_{n}(-\operatorname {i} /{\sqrt {3}})}$ où ${\displaystyle L_{n}(x)={\frac {1}{2^{n}n!}}{\frac {\operatorname {d} ^{n}}{\operatorname {d} x^{n}}}((x^{2}-1)^{n})}$ est le polynôme de Legendre.

Leur fonction génératrice est donnée par la formule :

${\displaystyle 1+x+3x^{2}+7x^{3}+19x^{4}+\ldots ={\frac {1}{\sqrt {(1+x)(1-3x)}}}.}$

Euler a noté l'exemplum memorabile inductionis fallacis (« exemple notable d'induction fallacieuse ») :

${\displaystyle 3{n+1 \choose n+1}_{2}-{n+2 \choose n+2}_{2}=F_{n}(F_{n}+1)}$ pour ${\displaystyle 0\leqslant n\leqslant 7}$,

où ${\displaystyle F_{n}}$ est le nombre de Fibonacci d'indice ${\displaystyle n}$^[1]. Cette relation est fausse à partir de ${\displaystyle n=8}$.

George Andrews a expliqué cette erreur en montrant l'identité générale^[2] :

${\displaystyle 2\sum _{k\in \mathbb {Z} }\left({n+1 \choose n+1+10k}_{2}-{n+1 \choose n+1+10k+1}_{2}\right)=F_{n}(F_{n}+1).}$

Interprétations combinatoires

Le coefficient ${\displaystyle {n \choose k}_{2}}$ s'interprète comme le nombre de façons de choisir ${\displaystyle k}$ cartes dans deux jeux identiques de ${\displaystyle n}$ cartes chacun^[3].

Plus formellement ${\displaystyle {n \choose k}_{2}}$ est le nombre de combinaisons avec répétitions formées à partir de ${\displaystyle n}$ objets, chaque élément étant répété deux fois au maximum. C'est donc aussi le nombre de ${\displaystyle n}$-uplets de coordonnées égales à 0,1, ou 2 dont la somme vaut ${\displaystyle k}$.

Par exemple, à partir de deux jeux de ${\displaystyle n=3}$ cartes A, B, C, les différents choix sont :

Nombre ${\displaystyle k}$ de cartes sélectionnées	Nombre ${\displaystyle {3 \choose k-3}_{2}}$de sélections	Sélections	Triplets associés
0	1	${\displaystyle \varnothing }$	${\displaystyle (0,0,0)}$
1	3	A, B, C	${\displaystyle (1,0,0)}$,${\displaystyle (0,1,0)}$,${\displaystyle (0,0,1)}$
2	6	AA, AB, AC, BB, BC, CC	${\displaystyle (2,0,0)}$,${\displaystyle (1,1,0)}$,${\displaystyle (1,0,1)}$,${\displaystyle (0,2,0)}$,${\displaystyle (0,1,1)}$,${\displaystyle (0,0,2)}$
3	7	AAB, AAC, ABB, ABC, ACC, BBC, BCC	${\displaystyle (2,1,0)}$,${\displaystyle (2,0,1)}$,${\displaystyle (1,2,0)}$,${\displaystyle (1,1,1)}$,${\displaystyle (1,0,2)}$,${\displaystyle (0,2,1)}$,${\displaystyle (0,1,2)}$
4	6	AABB, AABC, AACC, ABBC, ABCC, BBCC	${\displaystyle (2,2,0)}$,${\displaystyle (2,1,1)}$,${\displaystyle (2,0,2)}$,${\displaystyle (1,2,1)}$,${\displaystyle (1,1,2)}$,${\displaystyle (0,2,2)}$
5	3	AABBC, AABCC, ABBCC	${\displaystyle (2,2,1)}$,${\displaystyle (2,1,2)}$,${\displaystyle (1,2,2)}$
6	1	AABBCC	${\displaystyle (2,2,2)}$

Notant ${\displaystyle T(n,k)}$ le nombre de ${\displaystyle n}$-uplets de coordonnées égales à 0,1, ou 2 dont la somme vaut ${\displaystyle k}$, on a bien

${\displaystyle T(0,0)=1}$,${\displaystyle T(n,k)=0}$ pour ${\displaystyle \ k<0}$ et ${\displaystyle \ k>2n}$, et

${\displaystyle T(n,k)=T(n-1,k)+T(n-1,k-1)+T(n-1,k-2)}$, car il y a ${\displaystyle T(n-1,k)}$ tels ${\displaystyle n}$-uplets dont la dernière coordonnée vaut 0, ${\displaystyle T(n-1,k-1)}$ tels ${\displaystyle n}$-uplets dont la dernière coordonnée vaut 1, et ${\displaystyle T(n-1,k-2)}$ tels ${\displaystyle n}$-uplets dont la dernière coordonnée vaut 2.

D'où ${\displaystyle T(n,k)={n \choose k}_{2}}$.

On obtient ${\displaystyle T(n,k)}$ en considérant d'abord le nombre de façons de choisir ${\displaystyle p}$ paires de cartes identiques dans les deux jeux, nombre égal au coefficient binomial ${\displaystyle {n \choose p}}$ puis en choisissant les ${\displaystyle k-2p}$ cartes restantes de ${\displaystyle {n-p \choose k-2p}}$ façons^[3]. On retrouve l'expression :

${\displaystyle {n \choose k}_{2}=\sum _{p=\max(0,k-n)}^{\min(n,[k/2])}{n \choose p}{n-p \choose k-2p}}$.

On obtient notamment la formule ${\displaystyle {24 \choose 12}_{2}=287\,134\,346}$ pour le nombre de mains différentes dans le jeu de cartes Doppelkopf .

Aux échecs

Les termes du triangle trinomial correspondent aux nombres de chemins minimaux possibles que peut emprunter le roi dans une partie d'échecs pour aller d'une case à une autre. Dans la figure ci-contre, le nombre inscrit dans une case représente le nombre de chemins différents (en utilisant un nombre minimum de mouvements) que le roi peut emprunter pour atteindre cette case.

Généralisation au triangle q-nomial

Les coefficients du triangle q-nomial sont définis par :

${\displaystyle {0 \choose 0}_{q-1}=1}$,${\displaystyle {n \choose k}_{q-1}=0}$ pour ${\displaystyle \ k<0}$ et ${\displaystyle \ k>(q-1)n}$,

${\displaystyle {n \choose k}_{q-1}={n-1 \choose k}_{q-1}+{n-1 \choose k-1}_{q-1}+\cdots +{n-1 \choose k-q+1}_{q-1}}$ pour ${\displaystyle n\geqslant 1}$.

La ligne d'indice ${\displaystyle n}$ est constituée des coefficients de ${\displaystyle (1+X+\cdots +X^{q-1})^{n}}$ ^[4].

Le triangle binomial (${\displaystyle q=2}$) n'est alors autre que le triangle de Pascal.

Le triangle quadrinomial (${\displaystyle q=4}$) est référencé comme suite A008287 de l'OEIS.