Formule du crible/Exercices/sur le dénombrement des surjections

Exercices 2-1

a) De combien de façons peut-on ranger 20 chemises de couleurs différentes dans 10 tiroirs en laissant exactement 5 tiroirs vides ?

b) Même question en supposant que l'on veuille ranger 10 chemises indifférenciables (même couleur) dans 10 tiroirs en laissant exactement 5 tiroirs vides

Solution

a) Pour ranger les chemises il faut choisir les 5 tiroirs qui recevront les chemises, soit $\scriptstyle {10 \choose 5}$ = 252 possibilités. Associer ensuite, de façon surjective, chacune des 20 chemises aux 5 tiroirs choisis pour les y ranger. Soit :

$S_{20,5}=\sum _{k=0}^{5}(-1)^{5-k}{5 \choose k}k^{20}=89904730860000$

possibilités.

Il y a donc 252 × 89904730860000 = 22655992176720000 façons de ranger 20 chemises dans 10 tiroirs en laissant exactement 5 tiroirs vides.

b) Si les chemises sont indifférenciables, on commence par choisir les 5 tiroirs qui recevront les chemises, soit $\scriptstyle {10 \choose 5}$ = 252 possibilités. On dénombre ensuite tous les quintuplets de nombres entiers non nuls dont la somme est 10. On sait (cf. Combinatoire/Combinaisons avec répétition) qu'il y en a ${\binom {10-1}{5-1}}={\binom {9}{4}}={\frac {9\times 8\times 7\times 6}{4\times 3\times 2}}=9\times 2\times 7=126$. Vérifions :

(6, 1, 1, 1, 1) avec 5 permutations différenciables des nombres possibles.

(5, 2, 1, 1, 1) avec 20 permutations différenciables des nombres possibles.

(4, 3, 1, 1, 1) avec 20 permutations différenciables des nombres possibles.

(4, 2, 2, 1, 1) avec 30 permutations différenciables des nombres possibles.

(3, 3, 2, 1, 1) avec 30 permutations différenciables des nombres possibles.

(3, 2, 2, 2, 1) avec 20 permutations différenciables des nombres possibles.

(2, 2, 2, 2, 2) avec 1 permutations différenciables des nombres possibles.

Nous avons trouvé 126 quintuplets différenciables de nombres entiers non nuls dont la somme est 10. Pour chaque choix des 5 tiroirs, on a donc 126 façons de ranger les chemises en ne considérant que le nombre de chemises allant dans chaque tiroir.

Nous avons donc 252 × 126 = 31752 façons de ranger 10 chemises indifférenciables dans une armoire de 10 tiroirs en laissant exactement 5 tiroirs vides.

Remarque Pour trouver le nombre de quintuplets de nombres dont la somme est 10, on pourrait aussi raisonner astucieusement ainsi : On peut écrire : $1+1+1+1+1+1+1+1+1+1=10$ Pour trouver un quintuplet de nombre dont la somme est 10, il suffit en fait de partitionner le premier membre en cinq ensembles en rajoutant des parenthèses. Par exemple, au quintuplet (2,1,3,3;1), on associera l'écriture : $(1+1)+(1)+(1+1+1)+(1+1+1)+(1)=10$ Il y a donc autant de quintuplets que de façon de rajouter les cinq couples de parenthèses et l'on remarque qu'il y a aussi autant de façon de rajouter les cinq couples de parenthèses que ce qu'il y a de façons de sélectionner les 4 signes + entre les parenthèses. Comme il y a 9 signes +, le nombre de choix des 4 signes + sera une combinaison de 4 parmi 9 soit 9!/(5!✕4!) = 126 possibilités.