L'essentiel à connaître
Avant toute formule, pose-toi deux questions : l'ordre compte-t-il, et un même élément peut-il revenir ? Un code de 4 chiffres est ordonné (« 1234 » et « 4321 » diffèrent) et accepte les répétitions : il y en a $10^4 = 10\,000$. Avec $n$ éléments disponibles et $p$ choix, les quatre cas tiennent dans ce tableau, où une $p$-liste est une suite ordonnée de $p$ éléments.
| Situation | Ordre | Répétition | Nombre |
|---|---|---|---|
| $p$-listes (code) | oui | oui | $n^p$ |
| $p$-listes d'éléments distincts, ou arrangements (podium) | oui | non | $\frac{n!}{(n-p)!}$ |
| Parties à $p$ éléments (comité) | non | non | $\binom{n}{p} = \frac{n!}{p!\,(n-p)!}$ |
| Combinaisons avec répétition (objets identiques à répartir) | non | oui | $\binom{n+p-1}{p}$ |
La première ligne compte aussi les applications de $E$ dans $F$ : chaque élément de $E$ choisit son image, d'où $|F|^{|E|}$. Des étapes qui s'enchaînent se multiplient ; des cas qui s'excluent s'additionnent. Un mot de $n$ lettres où les lettres distinctes reviennent $n_1, \dots, n_k$ fois a $\frac{n!}{n_1!\,n_2!\cdots n_k!}$ anagrammes, et un chemin sur un quadrillage s'écrit comme un mot de pas « droite » et « haut ». Si la composition du mot n'est pas fixée, sépare les cas puis additionne.
La dernière ligne du tableau compte les solutions en entiers naturels de $x_1 + \dots + x_n = p$ : aligne $p$ étoiles, sépare-les en $n$ paquets par $n-1$ barres, puis choisis la place des barres parmi les $n+p-1$ symboles. Si chaque $x_i$ doit valoir au moins $m$, pose $y_i = x_i - m$ : la somme des $y_i$ vaut alors $p - nm$.
Formule : le contraire se compte par $|\overline{A}| = |E| - |A|$, où $\overline{A}$ est le complémentaire de $A$ dans $E$.
Inclusion-exclusion, qui retire ce qui a été compté deux fois : $|A \cup B| = |A| + |B| - |A \cap B|$ et $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$.
Une surjection de $E$ sur $F$ atteint chaque élément de $F$ : pour les compter, pars des $|F|^{|E|}$ applications et retire par inclusion-exclusion celles qui oublient une valeur. Le programme de MPSI et MP2I (2021) cite le cardinal d'une union quelconque, mais met hors programme la formule du crible, cette formule écrite pour un nombre quelconque d'ensembles.
Piège classique : pour un « au moins un », fixer d'abord un élément puis compléter librement compte plusieurs fois les mêmes cas. Passe par le contraire : le total, moins les cas où il n'y en a aucun.
Quiz : teste tes connaissances
Les questions montent en difficulté, et les trois dernières sont les plus piégeuses.
Question 1 : Un code compte 4 chiffres de 0 à 9, et un chiffre peut revenir. Combien de codes existe-t-il ?
Réponse : B. Chaque position offre 10 choix : $10 \times 10 \times 10 \times 10 = 10^4$. Le piège $4^{10}$ inverse les rôles : la base est le nombre de choix, l'exposant le nombre de positions.
Question 2 : On forme un comité de 3 personnes, sans rôle particulier, parmi 10. Combien de comités sont possibles ?
Réponse : D. L'ordre ne compte pas et personne ne siège deux fois : $\binom{10}{3} = \frac{10 \times 9 \times 8}{3!} = 120$. Le piège $720 = 10 \times 9 \times 8$ compte chaque comité $3! = 6$ fois, une fois par ordre de ses membres.
Question 3 : Une association de 20 membres élit un président, un trésorier et un secrétaire, sans cumul de postes. Combien de bureaux sont possibles ?
Réponse : A. Les postes sont distincts, donc l'ordre compte, et personne ne cumule : $20 \times 19 \times 18 = 6\,840$. Le piège $1\,140 = \binom{20}{3}$ choisit les trois élus sans leur attribuer de poste.
Question 4 : Combien y a-t-il d'applications de $E = \{1, 2, 3\}$ dans $F = \{a, b, c, d\}$ ?
Réponse : C. Chacun des 3 éléments de $E$ choisit son image parmi les 4 de $F$ : $4^3 = 64$. Le piège $3^4 = 81$ inverse départ et arrivée : l'exposant compte les éléments qui choisissent, ceux de $E$.
Question 5 : Un groupe compte 6 hommes et 5 femmes. Combien de comités de 4 personnes ont exactement 2 hommes et 2 femmes ?
Réponse : B. Choisir 2 hommes puis 2 femmes, ce sont deux étapes qui s'enchaînent : $\binom{6}{2} \times \binom{5}{2} = 15 \times 10 = 150$. Le piège $25 = 15 + 10$ additionne, alors qu'on n'additionne que des cas qui s'excluent.
Question 6 : Combien de mots différents, ayant un sens ou non, peut-on écrire avec exactement les 6 lettres de ANANAS ?
Réponse : A. ANANAS compte 3 A, 2 N et 1 S, et échanger deux lettres identiques ne change pas le mot : $\frac{6!}{3!\,2!\,1!} = \frac{720}{12} = 60$. Le piège $120 = \frac{6!}{3!}$ oublie que les deux N sont, eux aussi, interchangeables.
Question 7 : Sur un quadrillage, on va de $(0\,;\,0)$ à $(5\,;\,3)$ par pas d'une unité, vers la droite ou vers le haut. Combien de chemins existe-t-il ?
Réponse : D. Un chemin est un mot de 8 pas, 5 vers la droite (D) et 3 vers le haut (H), comme DDHDHDDH : $\frac{8!}{5!\,3!} = \binom{8}{3} = 56$. Le piège $256 = 2^8$ laisse chaque pas libre, alors qu'il faut exactement 3 pas vers le haut.
Question 8 : Parmi les codes de 4 chiffres de 0 à 9, répétitions permises, combien contiennent au moins un 7 ?
Réponse : C. Par le contraire : $9^4 = 6\,561$ codes n'ont aucun 7, donc $10^4 - 9^4 = 3\,439$ en ont au moins un. Le piège $4\,000 = 4 \times 10^3$ place un 7 puis remplit librement le reste : le code 7777 est alors compté quatre fois.
Question 9 : Combien d'entiers de 1 à 100 sont divisibles par 2 ou par 3 ?
Réponse : D. Il y a $50$ multiples de 2 et $33$ multiples de 3, mais les $16$ multiples de 6 sont dans les deux listes : $50 + 33 - 16 = 67$. Le piège $83 = 50 + 33$ compte deux fois ces multiples de 6.
Question 10 : On distribue 7 bonbons identiques à 4 enfants, et un enfant peut n'en recevoir aucun. Combien de distributions sont possibles ?
Réponse : B. Une distribution est une solution en entiers naturels de $x_1 + x_2 + x_3 + x_4 = 7$ : 7 étoiles et 3 barres, soit $\binom{10}{3} = 120$. Le piège $16\,384 = 4^7$ choisit un enfant pour chaque bonbon, comme si les bonbons étaient tous différents.
Question 11 : Combien d'entiers de 1 à 100 sont divisibles par 2, par 3 ou par 5 ?
Réponse : A. La formule pour trois ensembles donne $50 + 33 + 20 - 16 - 10 - 6 + 3 = 74$ : on retire les multiples de 6, de 10 et de 15, puis on rajoute les 3 multiples de 30. Le piège $71$ oublie ce dernier terme : les multiples de 30, ajoutés trois fois puis retirés trois fois, ne seraient plus comptés du tout.
Question 12 : Combien de mots de 4 lettres, ayant un sens ou non, peut-on écrire avec les lettres de ANANAS, chacune servant au plus autant de fois que dans ANANAS ?
Réponse : C. La composition n'est pas fixée, donc on sépare les cas (sans A, il ne reste que 3 lettres). Avec 3 A et 1 N, ou 3 A et 1 S : $\frac{4!}{3!} = 4$ mots chacun ; avec 2 A et 2 N : $\frac{4!}{2!\,2!} = 6$ ; avec 2 A, 1 N et 1 S, ou 1 A, 2 N et 1 S : $\frac{4!}{2!} = 12$ chacun ; total $4 + 4 + 6 + 12 + 12 = 38$. Le piège $26$ oublie le cas où le A n'apparaît qu'une fois.
Question 13 : Un groupe compte 6 hommes et 5 femmes. Combien de comités de 3 personnes comptent au moins une femme ?
Réponse : B. Tous les comités, moins ceux sans femme : $\binom{11}{3} - \binom{6}{3} = 165 - 20 = 145$. Le piège $225 = 5 \times \binom{10}{2}$ choisit « une femme » puis deux personnes quelconques : un comité de deux femmes est compté deux fois, un comité de trois femmes trois fois.
Question 14 : Combien de solutions en entiers l'équation $x_1 + x_2 + x_3 = 10$ admet-elle avec $x_1 \geqslant 2$, $x_2 \geqslant 2$ et $x_3 \geqslant 2$ ?
Réponse : D. Pose $y_i = x_i - 2$ : l'équation devient $y_1 + y_2 + y_3 = 4$ en entiers naturels, d'où $\binom{4+3-1}{4} = \binom{6}{4} = 15$ solutions. Le piège $36 = \binom{9}{7}$ ne retire que 1 à chaque inconnue, comme si la contrainte était $x_i \geqslant 1$.
Question 15 : Combien y a-t-il de surjections de $\{1, 2, 3, 4\}$ sur $\{a, b, c\}$ ?
Réponse : A. Parmi les $3^4 = 81$ applications, $2^4 = 16$ oublient une valeur donnée et $1^4 = 1$ oublie deux valeurs données : $81 - 3 \times 16 + 3 \times 1 = 36$. Le piège $72$ envoie d'abord trois éléments sur $\{a, b, c\}$, de $\binom{4}{3} \times 3! = 24$ façons, puis le dernier n'importe où : chaque surjection est alors comptée deux fois.
Sources
Ministère de l'Enseignement supérieur, de la Recherche et de l'Innovation, programme de mathématiques des classes préparatoires MPSI et MP2I (2021), partie « Dénombrement ».