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.

Le triangle trinomial sous la main d'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<0$ et $\ k>2n$,

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

Les seuls coefficients non nuls de la ligne d'indice $n$ sont les $2n+1$ ${n \choose k}_{2}$pour $k$ allant de $0$ à $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

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

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

${n \choose k}_{2}={n \choose 2n-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}_{2}X^{k}$

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}}$

• La relation de récurrence sur les ${n \choose k}_{2}$ peut se voir en écrivant que
  $$(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 : $(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}},$$

on obtient la relation :

${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 ${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 ${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 n}_{2}$ :

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

ont été étudiés par Euler.

Ils s'expriment par les formules :

${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 : ${n \choose n}_{2}=(\operatorname {i} {\sqrt {3}})^{n}L_{n}(-\operatorname {i} /{\sqrt {3}})$ où $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 :

$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 n+1}_{2}-{n+2 \choose n+2}_{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 n+1+10k}_{2}-{n+1 \choose n+1+10k+1}_{2}\right)=F_{n}(F_{n}+1).$

Interprétations combinatoires

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

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

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

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

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

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

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

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

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

${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 ${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 :

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

${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 $n\geqslant 1$.

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

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

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

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

Voir aussi

• Tableau triangulaire
• q-analogue du triangle de Pascal