30
CHAPITRE 4 : PROBABILIT ´
ES DISCR `
ETES. D ´
ENOMBREMENTS
4.3. Suites de termes distincts. — Supposons toujours B de cardinal p ≥ 1.
Une suite (c 1 , c 2 , . . . , c n ) est dite (n, p)-injective, si elle est de longueur n, si
tous ses termes c i sont pris dans B (de cardinal p) et si tous les c i sont
distincts. (Traditionnellement, une telle suite est appel´ ee arrangement sans
r´ ep´ etition de p ´ el´ ements pris n ` a n .) Soit I(n, p) l’ensemble de toutes les
suites (n, p)-injectives et soit I(n, p) son cardinal. Naturellement, I(n, p) est
vide si p < n. Si n = p, les suites (p, p)-injectives sont les num´ erotations de
l’ensemble B. On dit encore les permutations de B.
Proposition 4.3.1. — Si 0 ≤ n ≤ p, le nombre I(n, p) de suites (n, p)injectives est donn´ e par :
(4.3.1)
I(n, p) =
p!
(p − n)!
= p(p − 1) · · · (p − n + 1).
En particulier, le nombre de permutations d’un ensemble de cardinal p est
´ egal `
a :
(4.3.2)
I(p, p) = p!
D´ emonstration. — Soit c = (c 1 , c 2 , . . . , c p ) une num´ erotation de B. La
suite initiale c
= (c 1 , c 2 , . . . , c n ) de cette suite c est une suite (n, p)-injective.
Notons I(c
) l’ensemble des num´ erotations (d 1 , d 2 , . . . , d p ) de B telles que
(d 1 , d 2 , . . . , d n ) = (c 1 , c 2 , . . . , c n ) = c
. L’ensemble I(p, p) est la r´ eunion de
tous les I(c
), o` u c
varie dans I(n, p).
Il est clair que les ensembles I(c
) sont deux `
a deux disjoints, d’o` u
(4.3.3)
I(p, p) =
c
I(c
)
(c
∈ I(n, p)).
D’autre part, pour construire tous les ´ el´ ements de I(c
), il suffit de se
donner toutes les suites c
= (d n+1 , d n+2 , . . . , d p ) de longueur (p − n),
d’´ el´ ements distincts appartenant `
a B
= B \ {c 1 , c 2 , . . . , c n } et les juxtaposer
` a (c 1 , c 2 , . . . , c n ). Or B
a pour cardinal (p − n). Par cons´ equent, |I(c
)| =
I(p−n, p−n). Les ensembles I(c
) ont donc mˆ eme cardinal. La formule (4.3.3)
donne alors :
I(p, p) = I(n, p)I(p − n, p − n).
Comme I(1, p) = p et I(0, p) = 1, il vient I(p, p) = pI(p − 1, p − 1). D’o` u
I(p, p) = p! et I(n, p) = p!/(p − n)!
Remarque. — Dans le langage fonctionnel, p(p − 1) · · · (p − n + 1) est le
cardinal de l’ensemble des injections d’un ensemble de cardinal n dans un
ensemble de cardinal p.
Exemple. — Vingt-cinq chevaux participent `
a la course du tierc´ e. Un
tierc´ e est une suite (n=3, p=25)-injective. Il y a donc 25 × 24 × 23 = 13.800
tierc´ es possibles.
Exemple. — Les anagrammes du mot TRAINE, dont les six lettres sont
distinctes, sont les permutations d’un ensemble de six ´ el´ ements. Le nombre
d’anagrammes est donc ´ egal ` a : 6! = 120.
CHAPITRE 4 : PROBABILIT ´
ES DISCR `
ETES. D ´
ENOMBREMENTS
4.3. Suites de termes distincts. — Supposons toujours B de cardinal p ≥ 1.
Une suite (c 1 , c 2 , . . . , c n ) est dite (n, p)-injective, si elle est de longueur n, si
tous ses termes c i sont pris dans B (de cardinal p) et si tous les c i sont
distincts. (Traditionnellement, une telle suite est appel´ ee arrangement sans
r´ ep´ etition de p ´ el´ ements pris n ` a n .) Soit I(n, p) l’ensemble de toutes les
suites (n, p)-injectives et soit I(n, p) son cardinal. Naturellement, I(n, p) est
vide si p < n. Si n = p, les suites (p, p)-injectives sont les num´ erotations de
l’ensemble B. On dit encore les permutations de B.
Proposition 4.3.1. — Si 0 ≤ n ≤ p, le nombre I(n, p) de suites (n, p)injectives est donn´ e par :
(4.3.1)
I(n, p) =
p!
(p − n)!
= p(p − 1) · · · (p − n + 1).
En particulier, le nombre de permutations d’un ensemble de cardinal p est
´ egal `
a :
(4.3.2)
I(p, p) = p!
D´ emonstration. — Soit c = (c 1 , c 2 , . . . , c p ) une num´ erotation de B. La
suite initiale c
= (c 1 , c 2 , . . . , c n ) de cette suite c est une suite (n, p)-injective.
Notons I(c
) l’ensemble des num´ erotations (d 1 , d 2 , . . . , d p ) de B telles que
(d 1 , d 2 , . . . , d n ) = (c 1 , c 2 , . . . , c n ) = c
. L’ensemble I(p, p) est la r´ eunion de
tous les I(c
), o` u c
varie dans I(n, p).
Il est clair que les ensembles I(c
) sont deux `
a deux disjoints, d’o` u
(4.3.3)
I(p, p) =
c
I(c
)
(c
∈ I(n, p)).
D’autre part, pour construire tous les ´ el´ ements de I(c
), il suffit de se
donner toutes les suites c
= (d n+1 , d n+2 , . . . , d p ) de longueur (p − n),
d’´ el´ ements distincts appartenant `
a B
= B \ {c 1 , c 2 , . . . , c n } et les juxtaposer
` a (c 1 , c 2 , . . . , c n ). Or B
a pour cardinal (p − n). Par cons´ equent, |I(c
)| =
I(p−n, p−n). Les ensembles I(c
) ont donc mˆ eme cardinal. La formule (4.3.3)
donne alors :
I(p, p) = I(n, p)I(p − n, p − n).
Comme I(1, p) = p et I(0, p) = 1, il vient I(p, p) = pI(p − 1, p − 1). D’o` u
I(p, p) = p! et I(n, p) = p!/(p − n)!
Remarque. — Dans le langage fonctionnel, p(p − 1) · · · (p − n + 1) est le
cardinal de l’ensemble des injections d’un ensemble de cardinal n dans un
ensemble de cardinal p.
Exemple. — Vingt-cinq chevaux participent `
a la course du tierc´ e. Un
tierc´ e est une suite (n=3, p=25)-injective. Il y a donc 25 × 24 × 23 = 13.800
tierc´ es possibles.
Exemple. — Les anagrammes du mot TRAINE, dont les six lettres sont
distinctes, sont les permutations d’un ensemble de six ´ el´ ements. Le nombre
d’anagrammes est donc ´ egal ` a : 6! = 120.