4. FORMULES CLASSIQUES DE D ´
ENOMBREMENT
29
Exemple. — Si on lance une pi` ece de monnaie et un d´ e ` a six faces,
l’ensemble Ω que l’on doit associer `
a cette exp´ erience suivant les principes
du chapitre 1 est le produit cart´ esien A × B, o` u A = {pile, face} et
B = {1, 2, 3, 4, 5, 6}. Il est de cardinal 2 × 6 = 12.
4. Formules classiques de d´ enombrement. — Dans ce paragraphe
figure une liste d’ensembles finis pour lesquels on connaˆ ıt des cardinaux
explicites.
4.1. Suites quelconques de longueur n. — Dans la formule (3.7), prenons
tous les ensembles B i (i = 1, 2, . . . , n) ´ egaux au mˆ eme ensemble B. On
obtient :
(4.1.1)
|B
n
| = |B|
n .
Ainsi l’ensemble de toutes les suites (b 1 , b 2 , . . . , b n ) de longueur n, o` u chaque
b i est pris dans B a pour cardinal |B|
n . Si |B| = p, de telles suites ´ etaient
appel´ ees dans le langage traditionnel arrangements avec r´ ep´ etitions de p
objets pris n ` a n , deux des ´ el´ ements b i et b j pouvant ˆ etre ´ egaux pour i = j.
Dans le langage fonctionnel, on peut encore dire que l’ensemble B
A de toutes
les applications d’un ensemble A, de cardinal n, dans un ensemble B, de
cardinal p, a pour cardinal p
n .
Exemple. — Le nombre de mots possibles (non n´ ecessairement pronon¸ cables) de cinq lettres est ´ egal ` a 26
5 = 11.881.376, et non pas 5
26 .
Exemple. — Supposons que l’on ait r boules num´ erot´ ees 1, 2, . . . , r que
l’on r´ epartit au hasard dans n urnes num´ erot´ ees 1, 2, . . . , n et que l’on
s’int´ eresse aux diff´ erentes r´ epartitions de ces r boules. Les urnes et boules
´ etant diff´ erenci´ ees (ou discernables), l’ensemble des r´ epartitions peut ˆ etre
assimil´ e ` a l’ensemble de toutes les suites (x 1 , x 2 , . . . , x r ), o` u x i est le num´ ero
de l’urne qu’occupe la boule i (1 ≤ i ≤ r). Il y a donc n
r telles r´ epartitions.
4.2. Ensembles des parties d’un ensemble. — Supposons que les p ´ el´ ements
d’un ensemble B de cardinal p soient num´ erot´ es b 1 , b 2 , . . . , b p . Toute partie A
de B est compl` etement caract´ eris´ ee par la donn´ ee d’une suite (x 1 , x 2 , . . . , x p )
o` u pour 1 ≤ i ≤ p chaque x i est ´ egal ` a 1 ou `
a 0, suivant que b i appartient ou
non `
a A.
L’application qui envoie toute partie A de B sur la suite associ´ ee
(x 1 , x 2 , . . . , x p ) est donc bijective. Par cons´ equent l’ensemble P(B) de toutes
les parties de B a mˆ eme cardinal que l’ensemble {0, 1}
p de toutes les suites
(x 1 , x 2 , . . . , x p ), de longueur p, o` u chaque x i est ´ egal ` a 0 ou `
a 1. De l` a :
(4.2.1)
|P(B)| = |{0, 1}|
p = 2
p = 2
|B| .
Exemple. — Soit B un groupe de sept individus. Le nombre de comit´ es
que l’on peut former `
a partir de ces sept personnes, y compris le comit´ e vide
et les comit´ es r´ eduits `
a une seule personne, est ´ egal ` a 2
7 = 128.
ENOMBREMENT
29
Exemple. — Si on lance une pi` ece de monnaie et un d´ e ` a six faces,
l’ensemble Ω que l’on doit associer `
a cette exp´ erience suivant les principes
du chapitre 1 est le produit cart´ esien A × B, o` u A = {pile, face} et
B = {1, 2, 3, 4, 5, 6}. Il est de cardinal 2 × 6 = 12.
4. Formules classiques de d´ enombrement. — Dans ce paragraphe
figure une liste d’ensembles finis pour lesquels on connaˆ ıt des cardinaux
explicites.
4.1. Suites quelconques de longueur n. — Dans la formule (3.7), prenons
tous les ensembles B i (i = 1, 2, . . . , n) ´ egaux au mˆ eme ensemble B. On
obtient :
(4.1.1)
|B
n
| = |B|
n .
Ainsi l’ensemble de toutes les suites (b 1 , b 2 , . . . , b n ) de longueur n, o` u chaque
b i est pris dans B a pour cardinal |B|
n . Si |B| = p, de telles suites ´ etaient
appel´ ees dans le langage traditionnel arrangements avec r´ ep´ etitions de p
objets pris n ` a n , deux des ´ el´ ements b i et b j pouvant ˆ etre ´ egaux pour i = j.
Dans le langage fonctionnel, on peut encore dire que l’ensemble B
A de toutes
les applications d’un ensemble A, de cardinal n, dans un ensemble B, de
cardinal p, a pour cardinal p
n .
Exemple. — Le nombre de mots possibles (non n´ ecessairement pronon¸ cables) de cinq lettres est ´ egal ` a 26
5 = 11.881.376, et non pas 5
26 .
Exemple. — Supposons que l’on ait r boules num´ erot´ ees 1, 2, . . . , r que
l’on r´ epartit au hasard dans n urnes num´ erot´ ees 1, 2, . . . , n et que l’on
s’int´ eresse aux diff´ erentes r´ epartitions de ces r boules. Les urnes et boules
´ etant diff´ erenci´ ees (ou discernables), l’ensemble des r´ epartitions peut ˆ etre
assimil´ e ` a l’ensemble de toutes les suites (x 1 , x 2 , . . . , x r ), o` u x i est le num´ ero
de l’urne qu’occupe la boule i (1 ≤ i ≤ r). Il y a donc n
r telles r´ epartitions.
4.2. Ensembles des parties d’un ensemble. — Supposons que les p ´ el´ ements
d’un ensemble B de cardinal p soient num´ erot´ es b 1 , b 2 , . . . , b p . Toute partie A
de B est compl` etement caract´ eris´ ee par la donn´ ee d’une suite (x 1 , x 2 , . . . , x p )
o` u pour 1 ≤ i ≤ p chaque x i est ´ egal ` a 1 ou `
a 0, suivant que b i appartient ou
non `
a A.
L’application qui envoie toute partie A de B sur la suite associ´ ee
(x 1 , x 2 , . . . , x p ) est donc bijective. Par cons´ equent l’ensemble P(B) de toutes
les parties de B a mˆ eme cardinal que l’ensemble {0, 1}
p de toutes les suites
(x 1 , x 2 , . . . , x p ), de longueur p, o` u chaque x i est ´ egal ` a 0 ou `
a 1. De l` a :
(4.2.1)
|P(B)| = |{0, 1}|
p = 2
p = 2
|B| .
Exemple. — Soit B un groupe de sept individus. Le nombre de comit´ es
que l’on peut former `
a partir de ces sept personnes, y compris le comit´ e vide
et les comit´ es r´ eduits `
a une seule personne, est ´ egal ` a 2
7 = 128.