34
CHAPITRE 4 : PROBABILIT ´
ES DISCR `
ETES. D ´
ENOMBREMENTS
4.6. Coefficients multinomiaux. — Supposons donn´ es deux entiers p et k
tels que 1 ≤ k ≤ p, ainsi qu’une suite d’entiers (n 1 , n 2 , . . . , n k ) satisfaisant `
a :
(4.6.1)
n 1 ≥ 0, n 2 ≥ 0, . . . , n k ≥ 0 et n 1 + n 2 + · · · + n k = p.
Un coefficient multinomial est un nombre de la forme :
p!
n 1 ! n 2 ! . . . n k !
. On
le note :
p
n 1 , n 2 , . . . , n k
. Lorsque k = 2, on a n 1 + n 2 = p et on retrouve
naturellement le coefficient binomial
p
n 1
=
p!
n 1 ! (p − n 1 )!
.
Proposition 4.6.1. — Le nombre de suites de longueur p, contenant n 1
fois 1, n 2 fois 2, . . . , n k fois k, les n i satisfaisant les relations (4.6.1), est
´ egal au coefficient multinomial
p
n 1 ,n 2 ,...,n k
.
D´ emonstration. — Notons C(n 1 , n 2 , . . . , n k ) l’ensemble des suites contenant exactement n 1 fois 1,. . . , n k fois k, puis consid´ erons la suite
a = (1 1 , 1 2 , . . . , 1 n 1 , 2 1 , 2 2 , . . . , 2 n 2 , . . . , k 1 , k 2 , . . . , k n k ),
de longueur n 1 + n 2 + · · · + n k = p et d´ esignons par A l’ensemble des p!
r´ earrangements (permutations) de a.
Prenons un r´ earrangement b de la suite a et lisons les termes de ce
r´ earrangement b de la gauche vers la droite en ´ ecrivant d’abord les indices des
lettres 1. On obtient une permutation σ 1 = (i 1 , i 2 , . . . , i n 1 ), de longueur n 1 .
De mˆ eme, la lecture des indices des lettres 2, de la gauche vers la droite,
fournit une permutation σ 2 = (j 1 , j 2 , . . . , j n 2 ), de longueur n 2 , et ainsi de
suite. . . Prenons note de ces k permutations σ 1 , σ 2 , . . . , σ k et effa¸ cons tous
les indices dans la suite b. On obtient une suite c de l’ensemble C(n 1 , . . . , n k ).
Il est clair que l’application qui envoie b sur (c; σ 1 , σ 2 , . . . , σ k ) est bijective.
En fait, (c; σ 1 , σ 2 , . . . , σ k ) est un simple codage de la suite b. Or le nombre
des suites (c; σ 1 , σ 2 , . . . , σ k ) est ´ egal ` a |C(n 1 , . . . , n k )| n 1 ! n 2 ! . . . n k ! Comme
|A| = p!, on obtient bien la formule annonc´ ee.
Exemple. — Le nombre d’anagrammes du mot VASSAL, mot qui contient
deux lettres A, deux lettres S, une lettre V et une lettre L, est ´ egal ` a
6
2,2,1,1
= 6!/(2! 2! 1! 1! ) = 180. Le nombre d’anagrammes du mot BERLIET
est ´ egal ` a 7!/2! = 2.520. Parmi eux, se trouve le mot LIBERT ´
E.
La formule binomiale admet une extension multinomiale exprim´ ee dans la
proposition suivante.
Proposition 4.6.2. — Soient z 1 , z 2 , . . . , z k des nombres complexes
(ou des ´ el´ ements pris dans un anneau commutatif ). On a l’identit´ e multinomiale :
(4.6.2)
(z 1 + z 2 + · · · + z k )
p =
p
n 1 , n 2 , . . . , n k
z 1
n 1 z 2
n 2 . . . z k
n k ,
o` u la sommation est ´ etendue ` a l’ensemble des suites (n 1 , n 2 , . . . , n k ) d’entiers
satisfaisant `
a :
(4.6.3) n 1 ≥ 0, n 2 ≥ 0, . . . , n k ≥ 0
et
n 1 + n 2 + · · · + n k = p.
CHAPITRE 4 : PROBABILIT ´
ES DISCR `
ETES. D ´
ENOMBREMENTS
4.6. Coefficients multinomiaux. — Supposons donn´ es deux entiers p et k
tels que 1 ≤ k ≤ p, ainsi qu’une suite d’entiers (n 1 , n 2 , . . . , n k ) satisfaisant `
a :
(4.6.1)
n 1 ≥ 0, n 2 ≥ 0, . . . , n k ≥ 0 et n 1 + n 2 + · · · + n k = p.
Un coefficient multinomial est un nombre de la forme :
p!
n 1 ! n 2 ! . . . n k !
. On
le note :
p
n 1 , n 2 , . . . , n k
. Lorsque k = 2, on a n 1 + n 2 = p et on retrouve
naturellement le coefficient binomial
p
n 1
=
p!
n 1 ! (p − n 1 )!
.
Proposition 4.6.1. — Le nombre de suites de longueur p, contenant n 1
fois 1, n 2 fois 2, . . . , n k fois k, les n i satisfaisant les relations (4.6.1), est
´ egal au coefficient multinomial
p
n 1 ,n 2 ,...,n k
.
D´ emonstration. — Notons C(n 1 , n 2 , . . . , n k ) l’ensemble des suites contenant exactement n 1 fois 1,. . . , n k fois k, puis consid´ erons la suite
a = (1 1 , 1 2 , . . . , 1 n 1 , 2 1 , 2 2 , . . . , 2 n 2 , . . . , k 1 , k 2 , . . . , k n k ),
de longueur n 1 + n 2 + · · · + n k = p et d´ esignons par A l’ensemble des p!
r´ earrangements (permutations) de a.
Prenons un r´ earrangement b de la suite a et lisons les termes de ce
r´ earrangement b de la gauche vers la droite en ´ ecrivant d’abord les indices des
lettres 1. On obtient une permutation σ 1 = (i 1 , i 2 , . . . , i n 1 ), de longueur n 1 .
De mˆ eme, la lecture des indices des lettres 2, de la gauche vers la droite,
fournit une permutation σ 2 = (j 1 , j 2 , . . . , j n 2 ), de longueur n 2 , et ainsi de
suite. . . Prenons note de ces k permutations σ 1 , σ 2 , . . . , σ k et effa¸ cons tous
les indices dans la suite b. On obtient une suite c de l’ensemble C(n 1 , . . . , n k ).
Il est clair que l’application qui envoie b sur (c; σ 1 , σ 2 , . . . , σ k ) est bijective.
En fait, (c; σ 1 , σ 2 , . . . , σ k ) est un simple codage de la suite b. Or le nombre
des suites (c; σ 1 , σ 2 , . . . , σ k ) est ´ egal ` a |C(n 1 , . . . , n k )| n 1 ! n 2 ! . . . n k ! Comme
|A| = p!, on obtient bien la formule annonc´ ee.
Exemple. — Le nombre d’anagrammes du mot VASSAL, mot qui contient
deux lettres A, deux lettres S, une lettre V et une lettre L, est ´ egal ` a
6
2,2,1,1
= 6!/(2! 2! 1! 1! ) = 180. Le nombre d’anagrammes du mot BERLIET
est ´ egal ` a 7!/2! = 2.520. Parmi eux, se trouve le mot LIBERT ´
E.
La formule binomiale admet une extension multinomiale exprim´ ee dans la
proposition suivante.
Proposition 4.6.2. — Soient z 1 , z 2 , . . . , z k des nombres complexes
(ou des ´ el´ ements pris dans un anneau commutatif ). On a l’identit´ e multinomiale :
(4.6.2)
(z 1 + z 2 + · · · + z k )
p =
p
n 1 , n 2 , . . . , n k
z 1
n 1 z 2
n 2 . . . z k
n k ,
o` u la sommation est ´ etendue ` a l’ensemble des suites (n 1 , n 2 , . . . , n k ) d’entiers
satisfaisant `
a :
(4.6.3) n 1 ≥ 0, n 2 ≥ 0, . . . , n k ≥ 0
et
n 1 + n 2 + · · · + n k = p.