Cours – Dénombrement
Chapitre 08
ECS (1re année) — Chapitre 08. Cardinaux, arrangements, combinaisons, formules de Pascal et du binôme.
Ce chapitre a été réalisé conformément au programme marocain de mathématiques de la filière ECS.
1 Cardinaux
1.1 Définition
Définition 1.1 — (Cardinal)
Le cardinal d’un ensemble fini E, noté \mathrm{card}(E) ou |E|, est le nombre d’éléments de E.
Proposition 1.1 — (Propriétés)
- \mathrm{card}(A \cup B) = \mathrm{card}(A) + \mathrm{card}(B) - \mathrm{card}(A \cap B).
- \mathrm{card}(A \times B) = \mathrm{card}(A) \cdot \mathrm{card}(B).
- \mathrm{card}(\mathcal{P}(E)) = 2^{\mathrm{card}(E)}.
2 Listes et arrangements
2.1 p-listes
Définition 2.1 — (\boldsymbol{p}-liste)
Une p-liste d’éléments de E est un p-uplet (x_1, \ldots, x_p) \in E^p. Le nombre de p-listes est n^p si |E| = n.
2.2 Arrangements
Définition 2.2 — (Arrangement)
Un arrangement de p éléments parmi n est une p-liste d’éléments distincts. Le nombre d’arrangements est : A_n^p = \frac{n!}{(n-p)!} = n(n-1)(n-2)\cdots(n-p+1)
2.3 Permutations
Définition 2.3 — (Permutation)
Une permutation de n éléments est un arrangement de n éléments parmi n. Le nombre de permutations est n!.
3 Combinaisons
Définition 3.1 — (Combinaison)
Une combinaison de p éléments parmi n est un sous-ensemble à p éléments. Le nombre de combinaisons est : \binom{n}{p} = \frac{n!}{p!(n-p)!}
Proposition 3.1 — (Lien entre arrangements et combinaisons)
A_n^p = p! \cdot \binom{n}{p}.
4 Formules de Pascal et du binôme
Proposition 4.1 — (Formule de Pascal)
\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}
Théorème 4.1 — (Binôme de Newton)
(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}
Proposition 4.2
\sum_{k=0}^n \binom{n}{k} = 2^n.
5 Exercices
Exercice 5.1
Combien y a-t-il de nombres à 4 chiffres distincts ?
Exercice 5.2
De combien de façons peut-on choisir un comité de 3 personnes parmi 10 ?
Exercice 5.3
Un code est formé de 3 lettres distinctes suivies de 2 chiffres distincts. Combien de codes avec 26 lettres et 10 chiffres ?
Exercice 5.4
Un sac contient 3 boules rouges et 5 noires. On tire 3 boules. Combien de tirages avec exactement 2 rouges ?
Exercice 5.5
Montrer que \binom{n}{k} = \binom{n}{n-k}.
Exercice 5.6
Soit E fini de cardinal n. Déterminer le nombre de couples (A,B) \in \mathcal{P}(E)^2 avec A \subset B.
Indication : Chaque élément a 3 choix. Résultat : 3^n.
Exercice 5.7
Montrer l’identité de Vandermonde : \sum_{k=0}^r \binom{n}{k}\binom{m}{r-k} = \binom{n+m}{r}.
Exercice 5.8
Calculer \sum_{k=0}^n \binom{n}{k}^2.