Prépa, 1re année › Dénombrement › Principe additif, principe multiplicatif
Principe additif, principe multiplicatif : méthode (MPSI)
Méthode
Principe additif, principe multiplicatif
- Additif : si les objets à compter se répartissent en cas disjoints qui recouvrent tout, on compte chaque cas et on additionne.
- Multiplicatif : si un objet se construit par une suite de choix successifs et que le nombre d'options à chaque étape ne dépend pas des choix précédents (même si les options elles-mêmes en dépendent), on multiplie ces nombres.
La rédaction doit expliciter le découpage ou la suite de choix, puis vérifier que chaque objet est obtenu exactement une fois.
Exemple
Codes et mots
- Un code à $4$ chiffres est un élément de $\llbracket 0,9\rrbracket^4$ : il y en a $10^4=10\,000$.
- Un mot de passe formé de $2$ lettres majuscules suivies de $3$ chiffres : $26^2\times10^3=676\,000$.
- Codes à $4$ chiffres contenant au moins un $0$ : on passe au complémentaire. Il y a $9^4=6561$ codes sans $0$, donc $10\,000-6561=3439$ codes avec au moins un $0$.
S’entraîner
- Applications et injections entre deux petits ensembles
- Répartition en binômes
- Principe des tiroirs dans un intervalle d'entiers