TD — Dénombrement
Chapitre 17
TSI (1re année) — TD du Chapitre 17. Cardinaux, parties, p-listes, arrangements, permutations, combinaisons, formules de Pascal et du binôme.
Exercice 1
Déterminer le cardinal :
- Des listes de longueur p à valeurs dans un ensemble de cardinal n.
- Des arrangements de p éléments parmi n.
- Des combinaisons de p éléments parmi n.
Exercice 2
Combien de nombres de 4 chiffres distincts peut-on former ?
Exercice 3
De combien de façons peut-on choisir un comité de 3 personnes parmi 10 ?
Exercice 4
Montrer que :
- \sum_{k=0}^n \binom{n}{k} = 2^n
- \sum_{k=0}^n (-1)^k \binom{n}{k} = 0 pour n \geq 1
- \sum_{k=0}^n k\binom{n}{k} = n \cdot 2^{n-1}
Exercice 5
Montrer la formule de Pascal : \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}.
Exercice 6
Un sac contient 3 boules rouges et 5 boules noires. On tire 3 boules.
- Combien de tirages possibles ?
- Combien avec exactement 2 rouges ?
Exercice 7
Montrer l’identité de Vandermonde : \sum_{k=0}^r \binom{n}{k}\binom{m}{r-k} = \binom{n+m}{r}.
Exercice 8
Soit E fini de cardinal n. Déterminer le nombre de couples (A,B) avec A \subset B \subset E.
Indication : Chaque élément a 3 choix. Résultat : 3^n.
Exercice 9
Un code est formé de 3 lettres distinctes suivies de 2 chiffres distincts. Combien de codes avec 26 lettres et 10 chiffres ?
Exercice 10
Calculer \sum_{k=0}^n \binom{n}{k}^2.
Indication : Vandermonde avec m = n et r = n.