TD — Dénombrement
Chapitre 24
MPSI (1re année) — TD du Chapitre 24. Cardinal, listes, arrangements, combinaisons.
Exercice 1
Déterminer le cardinal des ensembles suivants :
- L’ensemble des listes de longueur p à valeurs dans un ensemble de cardinal n.
- L’ensemble des arrangements de p éléments parmi n (avec p \leq n).
- L’ensemble des combinaisons de p éléments parmi n.
Exercice 2
Combien y a-t-il de :
- Nombres de 4 chiffres distincts ?
- Nombres de 4 chiffres (non nécessairement distincts) ?
- Nombres pairs de 4 chiffres distincts ?
Exercice 3
Un code est formé de 3 lettres distinctes suivies de 2 chiffres distincts. Combien de codes peut-on former avec 26 lettres et 10 chiffres ?
Exercice 4
Soit n \geq 2. Montrer que :
- \displaystyle\sum_{k=0}^n \binom{n}{k} = 2^n
- \displaystyle\sum_{k=0}^n (-1)^k \binom{n}{k} = 0
- \displaystyle\sum_{k=0}^n k\binom{n}{k} = n \cdot 2^{n-1}
Indication : Utiliser le binôme de Newton avec (1+1)^n, (1-1)^n et la dérivée de (1+x)^n.
Exercice 5
De combien de façons peut-on choisir un comité de 3 personnes parmi 10 ? De combien de façons si l’une des personnes est présidente ?
Exercice 6
On dispose de 5 boules rouges et 7 boules bleues. De combien de façons peut-on en choisir 4 ?
Indication : \binom{12}{4} si les boules sont distinguables. Sinon, décomposer selon le nombre de rouges.
Exercice 7
Montrer la formule du binôme de Newton par récurrence : (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}
Exercice 8
Un sac contient 3 boules rouges et 5 boules noires. On tire simultanément 3 boules.
- Combien de tirages possibles ?
- Combien de tirages avec exactement 2 boules rouges ?
- Combien de tirages avec au moins une boule rouge ?
Exercice 9
Soit E un ensemble fini de cardinal n. Déterminer le nombre :
- De parties de E.
- De couples (A, B) \in \mathcal{P}(E)^2 avec A \subset B.
- De triplets (A, B, C) \in \mathcal{P}(E)^3 avec A \cap B \cap C = \varnothing.
Indications : - (2) Chaque élément de E a 3 choix : dans A \cap B, dans B \setminus A, dans E \setminus B. Résultat : 3^n. - (3) Chaque élément a 7 choix (tout sauf être dans les trois). Résultat : 7^n.
Exercice 10
Montrer l’identité de Vandermonde : \sum_{k=0}^r \binom{n}{k}\binom{m}{r-k} = \binom{n+m}{r}
Indication : Compter les façons de choisir r éléments parmi n+m en séparant selon le nombre choisi parmi les n.