Dénombrement
Chapitre 24
MPSI (1re année) — Chapitre 24. Cardinal d’un ensemble fini, cardinal de réunions et de produits cartésiens, listes, arrangements, permutations, combinaisons, coefficients binomiaux, formule du binôme.
Ce chapitre a été réalisé conformément au programme marocain de mathématiques de la filière MPSI.
Dénombrement
Dénombrer un ensemble fini, c’est déterminer son nombre d’éléments. Ce chapitre développe les outils fondamentaux du dénombrement : cardinaux, listes, arrangements, permutations et combinaisons.
1 Cardinal d’un ensemble fini
1.1 Notation et rappels
Définition 2.1 — (Ensemble fini)
On dit qu’un ensemble E est fini s’il peut être mis en bijection avec \{1,2,\ldots,n\} pour un certain n\in\mathbb{N}. On dit alors que E a n éléments. Sinon, E est dit infini.
Définition 2.2 — (Cardinal)
Soit E un ensemble fini. Le cardinal de E, noté \operatorname{Card}(E) ou \#E, est le nombre d’éléments de E. Si E=\varnothing, on pose \operatorname{Card}(E)=0.
1.2 Cardinal de la réunion de deux parties
Proposition 2.1
Soient A et B deux parties finies d’un ensemble. Alors : \operatorname{Card}(A\cup B)=\operatorname{Card}(A)+\operatorname{Card}(B)-\operatorname{Card}(A\cap B)
Preuve. On écrit A\cup B=A\cup(B\setminus A), réunion disjointe, donc \operatorname{Card}(A\cup B)=\operatorname{Card}(A)+\operatorname{Card}(B\setminus A). Or \operatorname{Card}(B)=\operatorname{Card}(B\setminus A)+\operatorname{Card}(A\cap B), d’où le résultat.
Proposition 2.2 — (Réunion disjointe)
Si A et B sont deux parties finies disjointes (A\cap B=\varnothing), alors : \operatorname{Card}(A\cup B)=\operatorname{Card}(A)+\operatorname{Card}(B)
1.3 Cardinal du complémentaire
Proposition 2.3
Soit A une partie finie d’un ensemble fini E. Alors : \operatorname{Card}(E\setminus A)=\operatorname{Card}(E)-\operatorname{Card}(A)
1.4 Cardinal du produit cartésien
Proposition 2.4
Soient A et B deux ensembles finis. Alors : \operatorname{Card}(A\times B)=\operatorname{Card}(A)\times\operatorname{Card}(B)
Exemple 2.1
\operatorname{Card}(\{0,1\}^3)=2^3=8.
1.5 Cardinal de l’ensemble des applications
Proposition 2.5
Soient E et F deux ensembles finis. Alors l’ensemble \mathcal{F}(E,F) des applications de E dans F a pour cardinal : \operatorname{Card}(\mathcal{F}(E,F))=\operatorname{Card}(F)^{\operatorname{Card}(E)}
Exemple 2.2
Le nombre d’applications de \{1,2,3\} dans \{0,1\} est 2^3=8.
2 Dénombrement
2.1 Listes sans répétition
Définition 3.1 — (Liste)
Soit E un ensemble fini. Une n-liste (ou liste de longueur n) d’éléments de E est un n-uplet (x_1,\ldots,x_n) d’éléments de E. Une n-liste est sans répétition si les x_i sont deux à deux distincts.
Proposition 3.1
Soit E un ensemble fini de cardinal p. Le nombre de n-listes d’éléments de E est p^n. Le nombre de n-listes sans répétition est p(p-1)(p-2)\cdots(p-n+1) (si n\leq p).
2.2 Permutations
Définition 3.2 — (Permutation)
Une permutation d’un ensemble fini E de cardinal n est une bijection de E dans E. L’ensemble des permutations de E est noté \mathfrak{S}(E) (ou \mathfrak{S}_n si E=\{1,\ldots,n\}).
Proposition 3.2
Le nombre de permutations d’un ensemble à n éléments est n!.
Exemple 3.1
Il y a 3!=6 permutations de \{1,2,3\}.
2.3 Arrangements
Définition 3.3 — (Arrangement)
Soit E un ensemble fini de cardinal p et n\leq p. Un n-arrangement de E est une n-liste sans répétition d’éléments de E.
Proposition 3.3
Le nombre de n-arrangements d’un ensemble à p éléments est : A_p^n=p(p-1)(p-2)\cdots(p-n+1)=\frac{p!}{(p-n)!}
Exemple 3.2
Le nombre de façons de choisir un président, un vice-président et un trésorier parmi 10 personnes est A_{10}^3=10\times 9\times 8=720.
2.4 Combinaisons
Définition 3.4 — (Combinaison)
Soit E un ensemble fini de cardinal p et n\leq p. Une n-combinaison de E est une partie de E à n éléments.
Proposition 3.4
Le nombre de n-combinaisons d’un ensemble à p éléments est : \binom{p}{n}=\frac{p!}{n!(p-n)!} \binom{p}{n} est appelé coefficient binomial.
Exemple 3.3
Le nombre de façons de choisir 3 personnes parmi 10 est \binom{10}{3}=\frac{10\times 9\times 8}{3\times 2\times 1}=120.
2.5 Propriétés des coefficients binomiaux
Proposition 3.5
Pour tous n\in\mathbb{N} et 0\leq k\leq n : 1. \binom{n}{k}=\binom{n}{n-k} (symétrie) ; 2. \binom{n}{0}=\binom{n}{n}=1 ; 3. Formule de Pascal : \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} (pour 1\leq k\leq n-1).
Proposition 3.6 — (Relation avec les arrangements)
A_p^n=n!\binom{p}{n}
2.6 Formule du binôme
Théorème 3.1 — (Formule du binôme de Newton)
Pour tous a,b\in\mathbb{K} et n\in\mathbb{N} : (a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^kb^{n-k}
Exemple 3.4
(a+b)^3=a^3+3a^2b+3ab^2+b^3.
Exercice 3.1
. Calculer \binom{8}{3}, \binom{10}{4}, \binom{6}{0}, \binom{5}{5}. 2. Calculer le nombre de façons de choisir 4 personnes parmi 12. 3. Calculer le nombre de mots de 5 lettres formés avec les lettres \{a,b,c\}. 4. Combien y a-t-il de mains de 5 cartes dans un jeu de 52 cartes ?
Solution. . \binom{8}{3}=56, \binom{10}{4}=210, \binom{6}{0}=1, \binom{5}{5}=1. 2. \binom{12}{4}=495. 3. 3^5=243. 4. \binom{52}{5}=2598960.