Triangle trinomial

Le triangle trinomial sous la main d'Euler.

En mathématiques, le triangle trinomial est un tableau triangulaire de nombres entiers, constituant une variante du triangle de Pascal, étudié en particulier par Euler.

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

${\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 coefficient lus ligne par ligne forment la suite A027907 de l'OEIS.

Définition formelle

Les termes de la ligne d'indice $n$ étant notés :

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

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

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

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

Les seuls coefficients non nuls sont les $2n+1$ ${n \choose k}_{2}$pour $k$ allant de $-n$ à $n$.

Propriétés

• ${\binom {n}{-n}}_{2}={\binom {n}{n}}_{2}=1$, ${\binom {n}{-n+1}}_{2}={\binom {n}{n-1}}_{2}=n$ pour $n\geqslant 1$.

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

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

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

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

ou, de façon symétrique,

Le triangle trinomial peut se construire à partir de la pyramide de Pascal.${\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}}$

$\left(1+X+1/X\right)^{n}=\sum _{k=-n}^{n}{n \choose k}_{2}X^{k}$ .

La relation de récurrence sur les ${n \choose k}_{2}$ peut se voir en écrivant que $\left(1+X+1/X\right)^{n}=\left(1+X+1/X\right)^{n-1}+X\left(1+X+1/X\right)^{n-1}+{\frac {1}{X}}\left(1+X+1/X\right)^{n-1}$.

• D'après la formule du trinôme : $(1+X+Y)^{n}=\sum _{0\leqslant i,j\leqslant n}{\binom {n}{i,j,n-i-j}}X^{i}Y^{j}$ où ${\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}}$,

d'où la relation :

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

La relation de récurrence sur les ${n \choose k}_{2}$ peut se déduire de la relation de récurrence sur les coefficients de la pyramide de Pascal : ${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 $n$ est égale à $(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 ${n \choose 0}_{2}$ :

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

ont été étudiés par Euler.

Ils sont donnés par les formules :

${n \choose 0}_{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}.$

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

$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 ») :

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

où $F_{n}$ est le nombre de Fibonacci d'indice $n$. Cette relation est fausse à partir de $n=8$.

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

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

Applications

Aux échecs

Le triangle trinomial correspond au nombre de chemins possibles que peut emprunter le roi dans une partie d'échecs. 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.

---

En combinatoire

Le coefficient de $X^{k}$ dans le développement de $\left(1+X+X^{2}\right)^{n}$ donne le nombre de façons différentes de choisir $k$ cartes de deux jeux identiques de $n$ cartes chacun. Par exemple, à partir de deux jeux de trois cartes A, B, C, les différents choix sont :

Nombre de cartes sélectionnées	Nombre de choix	Choix
0	1
1	3	A, B, C
2	6	AA, AB, AC, BB, BC, CC
3	7	AAB, AAC, ABB, ABC, ACC, BBC, BCC
4	6	AABB, AABC, AACC, ABBC, ABCC, BBCC
5	3	AABBC, AABCC, ABBCC
6	1	AABBCC

Par exemple,

$6={3 \choose 2-3}_{2}={3 \choose 0}{3 \choose 2}+{3 \choose 1}{2 \choose 0}=1\cdot 3+3\cdot 1$ .

Cela donne notamment la formule ${24 \choose 12-24}_{2}={24 \choose -12}_{2}={24 \choose 12}_{2}$ pour le nombre de mains différentes dans le jeu de cartes Doppelkopf .

Il est également possible d'arriver à cette expression en considérant le nombre de façons de choisir $p$ paires de cartes identiques des deux jeux, qui est le coefficient binomial ${n \choose p}$ . Les $k-2p$ cartes restantes peuvent ensuite être choisies dans ${n-p \choose k-2p}$ façons, qui peut être écrit en termes de coefficients binomiaux sous la forme

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

L'exemple ci-dessus correspond aux trois manières de sélectionner deux cartes sans paires de cartes identiques (AB, AC, BC) et aux trois manières de sélectionner une paire de cartes identiques (AA, BB, CC).

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Trinomial triangle » (voir la liste des auteurs).

• (en) Eric W. Weisstein, « Trinomial triangle », sur MathWorld
• (en) Eric W. Weisstein, « Central Trinomial Coefficient », sur MathWorld