QCM : Dénombrement (Prépa, 1re année)
Dénombrer, c'est compter les éléments d'un ensemble fini sans les énumérer un par un, en le découpant, en le mettant en bijection avec un ensemble connu ou en le comptant de deux façons. Ces techniques servent en probabilités, en algèbre (formule du binôme, polynômes) et en informatique (complexité, structures de données).
Combien l'intervalle d'entiers $\llbracket 12,40\rrbracket$ contient-il d'éléments ?
$k\mapsto k-11$ est une bijection de $\llbracket 12,40\rrbracket$ sur $\llbracket 1,29\rrbracket$, donc le cardinal vaut $40-12+1=29$. Le piège classique est d'écrire $b-a=28$ et d'oublier l'une des deux bornes.
Soient $E$ un ensemble à $4$ éléments et $F$ un ensemble à $3$ éléments. Combien existe-t-il d'applications de $E$ dans $F$ ?
Chacun des $4$ éléments de départ reçoit une image parmi les $3$ éléments d'arrivée : $3^4=81$. La réponse $64=4^3$ inverse base et exposant. La réponse $24=4!$ compte des permutations. La réponse $12$ confond avec le cardinal de $E\times F$.
Combien existe-t-il d'injections de $\llbracket 1,3\rrbracket$ dans $\llbracket 1,6\rrbracket$ ?
Une injection correspond à une $3$-liste d'éléments distincts de $\llbracket 1,6\rrbracket$ : $6\times5\times4=120$. La réponse $20=\binom{6}{3}$ oublie que l'ordre des images compte. La réponse $216=6^3$ compte toutes les applications. La réponse $729=3^6$ inverse en plus base et exposant.
Combien d'entiers de $\llbracket 1,60\rrbracket$ sont divisibles par $4$ ou par $6$ ?
Il y a $15$ multiples de $4$ et $10$ multiples de $6$. Un entier est multiple de $4$ et de $6$ si et seulement s'il est multiple de $\operatorname{ppcm}(4,6)=12$, et il y en a $5$. Donc $15+10-5=20$. La réponse $25$ oublie l'intersection. La réponse $23$ prend les multiples de $24=4\times6$ au lieu de ceux de $12$. La réponse $40$ compte les entiers divisibles ni par $4$ ni par $6$.
Dans un jeu de $32$ cartes contenant $4$ dames, combien de mains de $5$ cartes contiennent au moins une dame ?
On passe au complémentaire : $\binom{32}{5}-\binom{28}{5}=201\,376-98\,280=103\,096$. La réponse $125\,860=4\binom{31}{4}$ choisit une dame puis $4$ cartes quelconques, et compte plusieurs fois les mains à plusieurs dames. La réponse $81\,900=4\binom{28}{4}$ compte les mains à exactement une dame. La réponse $98\,280$ compte les mains sans dame.
Combien de mots distincts s'écrivent avec toutes les lettres de BANANE ?
Le mot compte $6$ lettres, dont deux A et deux N. Chaque mot est obtenu $2!\times2!=4$ fois parmi les $6!=720$ ordonnements de jetons distincts. Le lemme des bergers donne $720/4=180$. La réponse $720$ ignore les répétitions. La réponse $360$ ne tient compte que d'une des deux lettres doublées. La réponse $90$ divise par $8$, comme si trois lettres étaient doublées.
Soient $E$ et $F$ deux ensembles et $f:E\to F$. Laquelle de ces affirmations est vraie ?
Si $f$ est injective, $\operatorname{Card}f(E)=\operatorname{Card}E$. Comme $f(E)\subset F$, on obtient $\operatorname{Card}E\le\operatorname{Card}F$. L'affirmation sur $\mathbb{N}$ est fausse : $n\mapsto n+1$ est injective sans être surjective, car le théorème exige des ensembles finis. Pour une surjection, l'inégalité va dans l'autre sens : $\operatorname{Card}F\le\operatorname{Card}E$. Enfin, un cardinal commun ne suffit pas : il faut en plus que $f$ soit injective ou surjective, une application constante ne convient pas.
Combien existe-t-il de chemins de $(0,0)$ à $(4,3)$ formés de pas $(1,0)$ ou $(0,1)$ ?
Un chemin compte $7$ pas. Il est déterminé par la position des $3$ pas vers le haut parmi les $7$, ce qui donne $\binom{7}{3}=35$ chemins. La réponse $128=2^7$ oublie que le nombre de pas dans chaque direction est imposé. La réponse $210=7\times6\times5$ ordonne les positions choisies. La réponse $12$ multiplie simplement les coordonnées.
Que vaut $\displaystyle\sum_{k=0}^{5}k\binom{5}{k}$ ?
La formule $\sum_k k\binom{n}{k}=n2^{n-1}$ (double comptage des couples (partie, élément pointé)) donne $5\times2^4=80$. Contrôle direct : $0+5+20+30+20+5=80$. La réponse $160=5\times2^5$ oublie que, une fois l'élément pointé fixé, il ne reste que $n-1$ éléments libres. La réponse $32$ est $\sum_k\binom{5}{k}$, sans le facteur $k$.
Dans un club de $10$ personnes, on forme un bureau composé d'un président, d'un secrétaire et de $2$ autres membres sans fonction particulière. Combien de bureaux sont possibles ?
On choisit le président ($10$ façons), puis le secrétaire ($9$ façons), puis les $2$ autres membres parmi les $8$ restants, sans ordre ($\binom{8}{2}=28$ façons). On obtient $10\times9\times28=2520$. La réponse $5040=10\times9\times8\times7$ ordonne aussi les deux membres simples. La réponse $1260=\binom{10}{2}\binom{8}{2}$ oublie que président et secrétaire ont des rôles distincts. La réponse $210=\binom{10}{4}$ ignore tous les rôles.