Le triangle trinomial sous la main d'Euler[ 1] 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).
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
{\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 coefficient lus ligne par ligne forment la suite A027907 de l'OEIS .
Les termes de la ligne d'indice
n
{\displaystyle n}
(
n
k
)
2
{\displaystyle {n \choose k}_{2}}
k
{\displaystyle k}
les coefficients du triangle trinomial peuvent être générés à l'aide de la formule de récurrence suivante :
(
0
0
)
2
=
1
{\displaystyle {0 \choose 0}_{2}=1}
(
n
k
)
2
=
0
{\displaystyle {n \choose k}_{2}=0}
k
<
0
{\displaystyle \ k<0}
k
>
2
n
{\displaystyle \ k>2n}
(
n
k
)
2
=
(
n
−
1
k
)
2
+
(
n
−
1
k
−
1
)
2
+
(
n
−
1
k
−
2
)
2
{\displaystyle {n \choose k}_{2}={n-1 \choose k}_{2}+{n-1 \choose k-1}_{2}+{n-1 \choose k-2}_{2}}
n
⩾
1
{\displaystyle n\geqslant 1}
Les seuls coefficients non nuls de la ligne d'indice
n
{\displaystyle n}
2
n
+
1
{\displaystyle 2n+1}
(
n
k
)
2
{\displaystyle {n \choose k}_{2}}
k
{\displaystyle k}
0
{\displaystyle 0}
2
n
{\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
(
n
0
)
2
=
(
n
2
n
)
2
=
1
{\displaystyle {\binom {n}{0}}_{2}={\binom {n}{2n}}_{2}=1}
(
n
1
)
2
=
(
n
2
n
−
1
)
2
=
n
{\displaystyle {\binom {n}{1}}_{2}={\binom {n}{2n-1}}_{2}=n}
Symétrie d'une ligne par rapport à son centre :
(
n
k
)
2
=
(
n
2
n
−
k
)
2
{\displaystyle {n \choose k}_{2}={n \choose 2n-k}_{2}}
La ligne d'indice
n
{\displaystyle n}
1
+
X
+
X
2
{\displaystyle 1+X+X^{2}}
n
{\displaystyle n}
(
1
+
X
+
X
2
)
n
=
∑
k
=
0
2
n
(
n
k
)
2
X
k
{\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 .
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
{\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
(
n
k
)
2
{\displaystyle {n \choose k}_{2}}
(
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
{\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 :
(
1
+
X
+
Y
)
n
=
∑
0
⩽
i
,
j
⩽
n
(
n
i
,
j
,
n
−
i
−
j
)
X
i
Y
j
{\displaystyle (1+X+Y)^{n}=\sum _{0\leqslant i,j\leqslant n}{\binom {n}{i,j,n-i-j}}X^{i}Y^{j}}
(
n
i
,
j
,
n
−
i
−
j
)
=
n
!
i
!
j
!
(
n
−
i
−
j
)
!
=
(
n
i
)
(
n
−
i
j
)
=
(
n
j
)
(
n
−
j
i
)
,
{\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 :
(
n
k
)
2
=
∑
0
⩽
i
,
j
⩽
n
i
+
2
j
=
k
(
n
i
,
j
,
n
−
i
−
j
)
{\displaystyle {n \choose k}_{2}=\sum _{\textstyle {0\leqslant i,j\leqslant n \atop i+2j=k}}{\binom {n}{i,j,n-i-j}}}
(
n
k
)
2
=
∑
max
(
0
,
k
−
n
)
⩽
j
⩽
k
/
2
(
n
k
−
2
j
)
(
n
−
k
+
2
j
j
)
=
∑
max
(
0
,
k
−
n
)
⩽
j
⩽
k
/
2
(
n
j
)
(
n
−
j
k
−
2
j
)
{\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
(
n
k
)
2
{\displaystyle {n \choose k}_{2}}
pyramide de Pascal :
(
n
i
,
j
,
k
)
=
(
n
−
1
i
−
1
,
j
,
k
)
+
(
n
−
1
i
,
j
−
1
,
k
)
+
(
n
−
1
i
,
j
,
k
−
1
)
.
{\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
n
{\displaystyle n}
(
1
+
1
+
1
)
n
=
3
n
{\displaystyle (1+1+1)^{n}=3^{n}}
Les diagonales ont des propriétés intéressantes en relation avec les nombres triangulaires . Les coefficients trinomiaux centraux
(
n
n
)
2
{\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 :
(
n
n
)
2
=
∑
0
⩽
k
⩽
n
/
2
n
(
n
−
1
)
⋯
(
n
−
2
k
+
1
)
(
k
!
)
2
=
∑
0
⩽
k
⩽
n
/
2
(
n
2
k
)
(
2
k
k
)
=
∑
0
⩽
k
⩽
n
/
2
(
n
k
)
(
n
−
k
k
)
{\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 :
(
n
n
)
2
=
(
i
3
)
n
L
n
(
−
i
/
3
)
{\displaystyle {n \choose n}_{2}=(\operatorname {i} {\sqrt {3}})^{n}L_{n}(-\operatorname {i} /{\sqrt {3}})}
L
n
(
x
)
=
1
2
n
n
!
d
n
d
x
n
(
(
x
2
−
1
)
n
)
{\displaystyle L_{n}(x)={\frac {1}{2^{n}n!}}{\frac {\operatorname {d} ^{n}}{\operatorname {d} x^{n}}}((x^{2}-1)^{n})}
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
+
…
=
1
(
1
+
x
)
(
1
−
3
x
)
.
{\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 ») :
3
(
n
+
1
n
+
1
)
2
−
(
n
+
2
n
+
2
)
2
=
F
n
(
F
n
+
1
)
{\displaystyle 3{n+1 \choose n+1}_{2}-{n+2 \choose n+2}_{2}=F_{n}(F_{n}+1)}
0
⩽
n
⩽
7
{\displaystyle 0\leqslant n\leqslant 7}
où
F
n
{\displaystyle F_{n}}
nombre de Fibonacci d'indice
n
{\displaystyle n}
[ 1]
n
=
8
{\displaystyle n=8}
George Andrews a expliqué cette erreur en montrant l'identité générale[ 2]
2
∑
k
∈
Z
(
(
n
+
1
n
+
1
+
10
k
)
2
−
(
n
+
1
n
+
1
+
10
k
+
1
)
2
)
=
F
n
(
F
n
+
1
)
.
{\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).}
Le coefficient
(
n
k
)
2
{\displaystyle {n \choose k}_{2}}
k
{\displaystyle k}
n
{\displaystyle n}
[ 3]
Plus formellement
(
n
k
)
2
{\displaystyle {n \choose k}_{2}}
combinaisons avec répétitions formées à partir de
n
{\displaystyle n}
n
{\displaystyle n}
uplets de coordonnées égales à 0,1, ou 2 dont la somme vaut
k
{\displaystyle k}
Par exemple, à partir de deux jeux de
n
=
3
{\displaystyle n=3}
Nombre
k
{\displaystyle k}
sélectionnées
Nombre
(
3
k
−
3
)
2
{\displaystyle {3 \choose k-3}_{2}}
Sélections
Triplets associés
0
1
∅
{\displaystyle \varnothing }
(
0
,
0
,
0
)
{\displaystyle (0,0,0)}
1
3
A, B, C
(
1
,
0
,
0
)
{\displaystyle (1,0,0)}
(
0
,
1
,
0
)
{\displaystyle (0,1,0)}
(
0
,
0
,
1
)
{\displaystyle (0,0,1)}
2
6
AA, AB, AC, BB, BC, CC
(
2
,
0
,
0
)
{\displaystyle (2,0,0)}
(
1
,
1
,
0
)
{\displaystyle (1,1,0)}
(
1
,
0
,
1
)
{\displaystyle (1,0,1)}
(
0
,
2
,
0
)
{\displaystyle (0,2,0)}
(
0
,
1
,
1
)
{\displaystyle (0,1,1)}
(
0
,
0
,
2
)
{\displaystyle (0,0,2)}
3
7
AAB, AAC, ABB, ABC, ACC, BBC, BCC
(
2
,
1
,
0
)
{\displaystyle (2,1,0)}
(
2
,
0
,
1
)
{\displaystyle (2,0,1)}
(
1
,
2
,
0
)
{\displaystyle (1,2,0)}
(
1
,
1
,
1
)
{\displaystyle (1,1,1)}
(
1
,
0
,
2
)
{\displaystyle (1,0,2)}
(
0
,
2
,
1
)
{\displaystyle (0,2,1)}
(
0
,
1
,
2
)
{\displaystyle (0,1,2)}
4
6
AABB, AABC, AACC, ABBC, ABCC, BBCC
(
2
,
2
,
0
)
{\displaystyle (2,2,0)}
(
2
,
1
,
1
)
{\displaystyle (2,1,1)}
(
2
,
0
,
2
)
{\displaystyle (2,0,2)}
(
1
,
2
,
1
)
{\displaystyle (1,2,1)}
(
1
,
1
,
2
)
{\displaystyle (1,1,2)}
(
0
,
2
,
2
)
{\displaystyle (0,2,2)}
5
3
AABBC, AABCC, ABBCC
(
2
,
2
,
1
)
{\displaystyle (2,2,1)}
(
2
,
1
,
2
)
{\displaystyle (2,1,2)}
(
1
,
2
,
2
)
{\displaystyle (1,2,2)}
6
1
AABBCC
(
2
,
2
,
2
)
{\displaystyle (2,2,2)}
Notant
T
(
n
,
k
)
{\displaystyle T(n,k)}
n
{\displaystyle n}
uplets de coordonnées égales à 0,1, ou 2 dont la somme vaut
k
{\displaystyle k}
T
(
0
,
0
)
=
1
{\displaystyle T(0,0)=1}
T
(
n
,
k
)
=
0
{\displaystyle T(n,k)=0}
k
<
0
{\displaystyle \ k<0}
k
>
2
n
{\displaystyle \ k>2n}
T
(
n
,
k
)
=
T
(
n
−
1
,
k
)
+
T
(
n
−
1
,
k
−
1
)
+
T
(
n
−
1
,
k
−
2
)
{\displaystyle T(n,k)=T(n-1,k)+T(n-1,k-1)+T(n-1,k-2)}
T
(
n
−
1
,
k
)
{\displaystyle T(n-1,k)}
n
{\displaystyle n}
uplets dont la dernière coordonnée vaut 0,
T
(
n
−
1
,
k
−
1
)
{\displaystyle T(n-1,k-1)}
n
{\displaystyle n}
uplets dont la dernière coordonnée vaut 1, et
T
(
n
−
1
,
k
−
2
)
{\displaystyle T(n-1,k-2)}
n
{\displaystyle n}
uplets dont la dernière coordonnée vaut 2.
D'où
T
(
n
,
k
)
=
(
n
k
)
2
{\displaystyle T(n,k)={n \choose k}_{2}}
On obtient
T
(
n
,
k
)
{\displaystyle T(n,k)}
p
{\displaystyle p}
coefficient binomial
(
n
p
)
{\displaystyle {n \choose p}}
k
−
2
p
{\displaystyle k-2p}
(
n
−
p
k
−
2
p
)
{\displaystyle {n-p \choose k-2p}}
[ 3]
(
n
k
)
2
=
∑
p
=
max
(
0
,
k
−
n
)
min
(
n
,
[
k
/
2
]
)
(
n
p
)
(
n
−
p
k
−
2
p
)
{\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
(
24
12
)
2
=
287
134
346
{\displaystyle {24 \choose 12}_{2}=287\,134\,346}
Doppelkopf
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.
Les coefficients du triangle q -nomial sont définis par :
(
0
0
)
q
−
1
=
1
{\displaystyle {0 \choose 0}_{q-1}=1}
(
n
k
)
q
−
1
=
0
{\displaystyle {n \choose k}_{q-1}=0}
k
<
0
{\displaystyle \ k<0}
k
>
(
q
−
1
)
n
{\displaystyle \ k>(q-1)n}
(
n
k
)
q
−
1
=
(
n
−
1
k
)
q
−
1
+
(
n
−
1
k
−
1
)
q
−
1
+
⋯
+
(
n
−
1
k
−
q
+
1
)
q
−
1
{\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}}
n
⩾
1
{\displaystyle n\geqslant 1}
La ligne d'indice
n
{\displaystyle n}
(
1
+
X
+
⋯
+
X
q
−
1
)
n
{\displaystyle (1+X+\cdots +X^{q-1})^{n}}
[ 4]
Le triangle binomial (
q
=
2
{\displaystyle q=2}
triangle de Pascal .
Le triangle quadrinomial (
q
=
4
{\displaystyle q=4}
A008287 de l'OEIS .
↑ a b c et d (la) Leonhard Euler, « Observationes analyticae », Novi Commentarii Academiae Scientiarum Petropolitanae vol. 11, 1767 , p. 124–143 (lire en ligne ) ↑ (en) George Andrews, « Three Aspects for Partitions », Séminaire Lotharingien de Combinatoire vol. B25f, 1990 (lire en ligne ) ↑ a et b (de) Andreas Stiller, « Pärchenmathematik. Trinomiale und Doppelkopf.. Issue 10/2005, p. 181 », C't vol. 10, 2005 , p. 181↑ (en) Daniel C. Fielder et Cecil O. Alford, « Pascal's triangle: Top gun or just one of the gang? » , dans Applications of Fibonacci Numbers , vol. 4 : (Proceedings of The Fourth International Conference on Fibonacci Numbers and Their Applications, Wake Forest University, N.C., U.S.A., July 30–August 3, 1990) , Kluwer Academics Publisher, 313 p. (ISBN 978-0-7923-1309-0 lire en ligne ) , p. 77-90 
![{\displaystyle {n \choose k}_{2}=\sum _{p=\max(0,k-n)}^{\min(n,[k/2])}{n \choose p}{n-p \choose k-2p}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f789c0a6d2b3fa2c320a77e9a0a20c172c46801)
