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

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 coefficients lus ligne par ligne forment la Modèle:OEIS.

Définition formelle

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

{(\binom{n}{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 :

{(\binom{0}{0})}_{2} = 1

,

{(\binom{n}{k})}_{2} = 0

pour

k < 0

et

k > 2 n

,

{(\binom{n}{k})}_{2} = {(\binom{n - 1}{k})}_{2} + {(\binom{n - 1}{k - 1})}_{2} + {(\binom{n - 1}{k - 2})}_{2}

pour

n ⩾ 1

.

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

Modèle:Séparateur diagonal	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}{2 n})}_{2} = 1$ , ${(\binom{n}{1})}_{2} = {(\binom{n}{2 n - 1})}_{2} = n$ .

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

{(\binom{n}{k})}_{2} = {(\binom{n}{2 n - k})}_{2}

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

{(1 + X + X^{2})}^{n} = \sum_{k = 0}^{2 n} {(\binom{n}{k})}_{2} X^{k}

La relation de récurrence sur les ${(\binom{n}{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 ⩽ i, j ⩽ 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 :

{(\binom{n}{k})}_{2} = \sum_{\binom{0 ⩽ i, j ⩽ n}{i + 2 j = k}} (\binom{n}{i, j, n - i - j})

(voir la traduction géométrique ci-contre), ou

{(\binom{n}{k})}_{2} = \sum_{\max (0, k - n) ⩽ j ⩽ k / 2} (\binom{n}{k - 2 j}) (\binom{n - k + 2 j}{j}) = \sum_{\max (0, k - n) ⩽ j ⩽ k / 2} (\binom{n}{j}) (\binom{n - j}{k - 2 j})

.

La relation de récurrence sur les ${(\binom{n}{k})}_{2}$ peut se déduire de la relation de récurrence sur les coefficients de la pyramide de Pascal : $(\binom{n}{i, j, k}) = (\binom{n - 1}{i - 1, j, k}) + (\binom{n - 1}{i, j - 1, k}) + (\binom{n - 1}{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 ${(\binom{n}{n})}_{2}$ :

1, 1, 3, 7, 19, 51, 141, 393, 1107, 3139,… (Modèle:OEIS)

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

Ils s'expriment par les formules :

{(\binom{n}{n})}_{2} = \sum_{0 ⩽ k ⩽ n / 2} \frac{n (n - 1) \dots (n - 2 k + 1)}{(k!)^{2}} = \sum_{0 ⩽ k ⩽ n / 2} (\binom{n}{2 k}) (\binom{2 k}{k}) = \sum_{0 ⩽ k ⩽ n / 2} (\binom{n}{k}) (\binom{n - k}{k})

.

On a aussi : ${(\binom{n}{n})}_{2} = (i \sqrt{3})^{n} L_{n} (- i / \sqrt{3})$ où $L_{n} (x) = \frac{1}{2^{n} n!} \frac{d^{n}}{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 + 3 x^{2} + 7 x^{3} + 19 x^{4} + \dots = \frac{1}{\sqrt{(1 + x) (1 - 3 x)}} .

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

3 {(\binom{n + 1}{n + 1})}_{2} - {(\binom{n + 2}{n + 2})}_{2} = F_{n} (F_{n} + 1)

pour

0 ⩽ n ⩽ 7

,

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

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

2 \sum_{k \in ℤ} ({(\binom{n + 1}{n + 1 + 10 k})}_{2} - {(\binom{n + 1}{n + 1 + 10 k + 1})}_{2}) = F_{n} (F_{n} + 1) .

Interprétations combinatoires

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

Plus formellement ${(\binom{n}{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 ${(\binom{3}{k - 3})}_{2}$ de sélections	Sélections	Triplets associés
0	1	$\emptyset$	$(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 > 2 n$ , 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) = {(\binom{n}{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 $(\binom{n}{p})$ puis en choisissant les $k - 2 p$ cartes restantes de $(\binom{n - p}{k - 2 p})$ façons^[3]. On retrouve l'expression :

{(\binom{n}{k})}_{2} = \sum_{p = \max (0, k - n)}^{\min (n, [k / 2])} (\binom{n}{p}) (\binom{n - p}{k - 2 p})

.

On obtient notamment la formule

{(\binom{24}{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 :

{(\binom{0}{0})}_{q - 1} = 1

,

{(\binom{n}{k})}_{q - 1} = 0

pour

k < 0

et

k > (q - 1) n

,

{(\binom{n}{k})}_{q - 1} = {(\binom{n - 1}{k})}_{q - 1} + {(\binom{n - 1}{k - 1})}_{q - 1} + \dots + {(\binom{n - 1}{k - q + 1})}_{q - 1}

pour

n ⩾ 1

.

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

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

Le triangle quadrinomial ( $q = 4$ ) est référencé comme Modèle:OEIS.

Références

Modèle:Traduction/Référence Modèle:Références

Voir aussi

Modèle:Portail

[:1-1] 1,0 ^1,1 ^1,2 et ^1,3 Modèle:Article

[2] Modèle:Article

[:0-3] 3,0 et ^3,1 Modèle:Article

[4] Modèle:Chapitre.

[1]

[2]

[3]

[4]

Triangle trinomial

Sommaire

Définition formelle

Propriétés

Coefficients trinomiaux centraux

Interprétations combinatoires

Aux échecs

Généralisation au triangle q-nomial

Références

Voir aussi

Menu de navigation

Triangle trinomial

Définition formelle

Propriétés

Coefficients trinomiaux centraux

Interprétations combinatoires

Aux échecs

Généralisation au triangle q-nomial

Références

Voir aussi

Menu de navigation

Rechercher