Combinatoire/Exercices/Arrangements

Les exercices sur cette page nécessitent parfois l'usage d'une calculatrice. Les nombres en jeu étant grands, certaines calculatrices pourraient ne pas être capables d'effectuer certains calculs. Cependant, nous nous sommes assurés que la calculatrice intégrée au moteur de recherche Google soit capable de les effectuer tous.

Cette liste d'exercices porte sur les arrangements, à la fois avec et sans répétition.

Exercices introductifs

Ces exercices sont des exercices de dénombrement avec des petits nombres. Le but est de vous permettre de faire vous-même la démarche qui sera détaillée dans le cours. Comprendre comment faire pour énumérer et compter de manière systématique vous permettra, avec un peu de chance, de mieux saisir la démarche générale qui mènera à la formule générale.

Seules les réponses sont indiquées ici ; une résolution détaillée sera faite dans le cadre du cours (voir le chapitre 3 pour l'exercice 2.1 et le chapitre 4 pour l'exercice 2.2)

2.1. Vous êtes un amateur de courses de chevaux. Aujourd'hui, les chevaux Alpha, Bêta, Gamma et Delta concourent et vous tentez de deviner le podium dans l'ordre.

A. Énumérez et comptez le nombre de possibilités.

B. Avant le départ, on apprend que Delta est blessé et qu’il est donc hors course. Combien reste-t-il de possibilités maintenant ?

Le lendemain, Delta est rétabli et un nouveau concurrent – un étalon noir vigoureux du nom d'Oméga, qui a naturellement les faveurs des pronostics – se présente.

C. Refaites la même chose qu'en A.

D. Plutôt que de prédire les trois premiers dans l'ordre, vous préférez cette fois-ci parier sur les deux premiers (toujours dans l'ordre) uniquement.

Après avoir fait ces calculs, essayez de penser à une manière de généraliser votre démarche au cas général, où il s'agit de déterminer les k premiers chevaux parmi n chevaux.

Solution

A = 24, B = 6, C = 60 et D = 20.

 

2.2. Aujourd’hui se tient une remise des prix à l'école Sainte-Combinatoire. Quatre élèves (appelons les Alphonse, Berthe, Coco et Delphine) sont en lice pour les prix d'excellence en mathématiques, en littérature et en sciences. Chaque élève espère en recevoir le maximum, pourquoi pas tous.

A. Énumérez et comptez le nombre de remises de prix possibles.

B. Le comité de discipline a puni Delphine pour mauvais comportement : elle ne pourra pas gagner de prix, en dépit de ses bons résultats. Combien reste-t-il de possibilités maintenant ?

C. Le premier prix est annoncé : c’est Coco qui obtient le prix de mathématiques. Combien reste-t-il de possibilités pour les deux autres prix ? (Delphine revient dans la course pour cette question.)

Comme la dernière fois, essayez de généraliser vos calculs pour n candidats et k prix ; n'hésitez pas à dessiner des arbres comme dans le chapitre sur les arrangements sans répétition.

Solution

A = 64, B = 27 et C = 16.

 

Arrangements sans répétition

2.3. Calculez les valeurs suivantes, éventuellement avec une calculatrice. Les grands nombres seront écrits en notation scientifique, avec 6 chiffres après la virgule.

$a.\qquad A_{4}^{2}$ $b.\qquad A_{5}^{3}$ $c.\qquad A_{6}^{2}$ $d.\qquad A_{4}^{4}$ $e.\qquad A_{8}^{1}$

$f.\qquad A_{100}^{2}$ $g.\qquad A_{12}^{1}$ $h.\qquad A_{10}^{5}$ $i.\qquad A_{75}^{2}$ $j.\qquad A_{7}^{2}$

$k.\qquad A_{100}^{98}$ $l.\qquad A_{75}^{55}$ $m.\qquad A_{7}^{7}$ $n.\qquad A_{7}^{5}$ $o.\qquad A_{77}^{75}$

Exemples de résolutions

On résout ce genre d'exercices en utilisant la formule des arrangements puis en calculant les factorielles. Par exemple, pour l'exercice a :

$a.\qquad A_{4}^{2}={\frac {4!}{(4-2)!}}={\frac {24}{2}}=12$.

Si les factorielles sont trop grandes, on peut toujours simplifier grâce à la méthode vue dans la série d'exercices sur les factorielles. Par exemple pour l'exercice f :

$f.\qquad A_{100}^{2}={\frac {100!}{98!}}={\frac {100\times 99\times 98!}{98!}}=100\times 99=9900$.

Dans certains cas il est totalement impossible de faire le calcul à la main et il est nécessaire de faire appel à une calculatrice. Par exemple pour l'exercice k :

$k.\qquad A_{100}^{98}={\frac {100!}{2!}}={\frac {100!}{2}}$.

100! est un très grand nombre. Une calculatrice donnera comme résultat $4{,}666311\times 10^{157}$.

 

Solution

$a.\qquad 12$

$b.\qquad 60$

$c.\qquad 30$

$d.\qquad 24$

$e.\qquad 8$

$f.\qquad 9900$

$g.\qquad 12$

$h.\qquad 30240$

$i.\qquad 55500$

$j.\qquad 42$

$k.\qquad 4{,}666311\times 10^{157}$

$l.\qquad 1{,}019735\times 10^{91}$

$m.\qquad 5040$

$n.\qquad 2520$

$o.\qquad 7{,}259155\times 10^{112}$

 

2.4. Les affiliés d'un club doivent élire un président, un vice-président et un trésorier, parmi n candidats. Sachant que tous les candidats se présentent à tous les postes, et que les fonctions sont non-cumulables, combien y a-t-il de possibilités :

a. Pour n = 3 ?

b. Pour n = 6 ?

c. Pour n = 10 ?

d. Pour n = 101 ?

Exemple de résolution

Cette situation correspond à un arrangement sans répétition ; en effet :

• on a un groupe de n objets (les candidats) parmi lesquels on doit en choisir 3, pour occuper les 3 fonctions ;
• les fonctions sont non-cumulables, ce qui correspond à la condition « sans répétition » ;
• les fonctions sont différentes, ce qui signifie que « l'ordre » des choix est important ; nous sommes donc dans le cas d'un arrangement.

Il suffit donc d’utiliser la formule avec k = 3. Exemple, avec n = 3 :

$A_{3}^{3}={\frac {3!}{0!}}={\frac {6}{1}}=6$.

 

Solution

a. 6
b. 120
c. 720
d. 999900

 

2.5. Pour un tour de magie, un prestidigitateur demande à un membre de son public de piocher, une par une, 3 cartes dans un paquet de cartes, et ensuite de les mélanger à nouveau. Le magicien doit alors deviner les 3 cartes dans l'ordre. En sachant que toutes les cartes du paquet sont différentes, combien de possibilités a le magicien, si :

a. Le paquet de cartes contient les 52 cartes habituelles ?

b. Le paquet de cartes ne contient que les trèfles ?

c. Le paquet ne contient que les cartes plus hautes que le 7 inclus (c'est-à-dire 32 cartes) ?

d. Le paquet ne contient que les 4 rois ?

Solution

a. 132600
b. 1716
c. 29760
d. 24

 

Arrangements avec répétition

2.6. Calculez les valeurs suivantes, éventuellement avec une calculatrice. Les grands nombres seront écrits en notation scientifique, avec 6 chiffres après la virgule.

$a.\qquad B_{4}^{2}$ $b.\qquad B_{5}^{3}$ $c.\qquad B_{3}^{7}$ $d.\qquad B_{4}^{4}$ $e.\qquad B_{8}^{1}$

$f.\qquad B_{100}^{2}$ $g.\qquad B_{1}^{12}$ $h.\qquad B_{12}^{1}$ $i.\qquad B_{75}^{2}$ $j.\qquad B_{7}^{8}$

$k.\qquad B_{100}^{98}$ $l.\qquad B_{2}^{100}$ $m.\qquad B_{7}^{7}$ $n.\qquad B_{5}^{7}$ $o.\qquad B_{9}^{3}$

Exemple de résolution

Il suffit ici d'appliquer la formule. Par exemple :

$b.\qquad B_{5}^{3}=5^{3}=125$.

 

Solution

$a.\qquad 16$

$b.\qquad 125$

$c.\qquad 2187$

$d.\qquad 256$

$e.\qquad 8$

$f.\qquad 10000$

$g.\qquad 1$

$h.\qquad 12$

$i.\qquad 5625$

$j.\qquad 5764801$

$k.\qquad 10^{196}$

$l.\qquad 1,267651\times 10^{30}$

$m.\qquad 823543$

$n.\qquad 78125$

$o.\qquad 729$

 

2.7. Dans un certain pays, on donne à chaque véhicule automobile un sigle d'immatriculation, qui doit être unique pour pouvoir l'identifier. Ce sigle est composé de chiffres et de lettres. Pour les différentes situations suivantes, déterminez combien de sigles d'immatriculation peuvent exister :

a. Une plaque d'immatriculation porte 6 chiffres.

b. Une plaque d'immatriculation porte 6 lettres de l'alphabet.

c. Une plaque d'immatriculation porte 6 caractères, pouvant être soit des chiffres, soit des lettres de l'alphabet.

d. Une plaque d'immatriculation porte 6 caractères, les 3 premiers étant des chiffres, les 3 derniers étant des lettres de l'alphabet.

Exemple de résolution

Cette situation (pour les points a, b et c) correspond à un arrangement avec répétition. En effet :

• on doit choisir 6 symboles parmi une liste de n symboles ;
• un même symbole peut apparaître plusieurs fois. On est donc dans un cas avec répétition ;
• en revanche, l’ordre des symboles sur la plaque a de l'importance. Nous sommes donc dans le cas d'un arrangement.

Sachant cela, il suffit d'appliquer la formule :

$a.\quad B_{10}^{6}=10^{6}$.

Pour le point d., on n'a pas exactement un arrangement : en effet les trois premiers caractères et les trois derniers ne sont pas choisis parmi les n mêmes caractères. Mais on peut s'en sortir facilement on séparant le problème en deux : le choix des trois premiers caractères est un arrangement avec répétition, tout comme le choix des trois derniers.

$d=B_{10}^{3}\times B_{26}^{3}=1{,}7576\times 10^{7}$.

 

Solution

$a.\qquad 10^{6}$

$b.\qquad 3,089158\times 10^{8}$

$c.\qquad 2,176782\times 10^{9}$

$d.\qquad 1,7576\times 10^{7}$

 

2.8. Vous devez choisir un mot de passe de n caractères. Combien existe-t-il de mots de passe possibles si :

a. Le mot de passe ne comporte que des voyelles en minuscule et fait cinq lettres.

b. Idem mais avec un mot de passe de dix lettres.

c. Le mot de passe fait dix lettres et peut comporter chacune des 26 lettres de l'alphabet français.

d. Idem, mais on peut utiliser les 26 lettres minuscules, les 26 lettres majuscules, les 10 chiffres et 20 autres caractères.

e. 20 caractères, les 26 lettres minuscules.

f. 10 caractères, les 26 lettres minuscules, mais chaque lettre n'est utilisée qu'une fois au maximum.

Solution

$a.\qquad 7776$

$b.\qquad 6{,}046618\times 10^{7}$

$c.\qquad 1{,}411671\times 10^{14}$

$d.\qquad 1{,}374480\times 10^{19}$

$e.\qquad 1{,}9928149\times 10^{28}$

$f.\qquad 1{,}927522\times 10^{13}$

 

Arrangements avec ou sans répétition

2.9. Parmi les situations suivantes, identifiez celles qui correspondent à un arrangement avec répétition, celles qui correspondent à un arrangement sans répétition, et celles qui ne sont ni l'une, ni l'autre. Si possible, calculez le nombre d'arrangements possibles.

a. De combien de manières peut-on composer un podium avec les 8 athlètes finalistes de la finale olympique du 100 mètres ?

b. 3 clubs de football français parmi les 20 clubs de Ligue 1 sont qualifiés pour la Ligue des Champions chaque année. Combien existe-t-il de trios possibles, les trois places étant considérées comme équivalentes ?

c. De combien de manières peut-on répartir 20 pommes identiques entre deux personnes ?

d. De combien de manières peut-on ranger 10 objets distincts dans 3 tiroirs ?

e. De combien de manières peut-on composer 2 équipes de 7 joueurs avec 14 joueurs ?

f. Un homme lègue sa maison, son bateau, sa collection de timbres et sa fortune. Chacune de ces choses étant considérée comme indivisible, de combien de manières peut-il répartir son héritage entre ses 8 petit-fils, en sachant qu’il ne veut pas en donner deux à la même personne ?

g. De combien de manières peut-on donner trois prix littéraires à 5 livres ?

h. De combien de manières peut-on classer (du meilleur au moins bon) 3 livres ?

i. De combien de manières peut-on répondre à un vrai ou faux de 20 questions (ne pas répondre à une question n’est pas une option) ?

j. De combien de manières peut-on choisir 5 députés parmi une liste de 30 candidats ?

Exemples de résolutions

Toutes ces situations correspondent à des choix d'un certain nombre d'éléments parmi n. Pour identifier les arrangements, il faut se poser les questions suivantes :

• Est-ce qu’il s'agit de choisir k objets sans que l’ordre du choix importe ? Si oui il ne s'agit pas d'un arrangement.
• Est-ce que les objets peuvent être choisis plusieurs fois ?

Voici les explications pour les énoncés qui ne correspondent pas à des arrangements :

b. L'ordre des 3 équipes de tête n'a pas d'importance, ce n'est donc pas un arrangement.

c. Le fait que les pommes soient identiques empêche de considérer cela comme un arrangement.

e. La situation ici est plus compliquée, mais ce n’est pas un arrangement. Si on considère qu’il s'agit d'assigner à chaque joueur une équipe ; on a alors 14 choix successifs à faire ; ce serait un arrangement s'il n'y avait pas la contrainte des sept joueurs. Si on considère de choisir simplement les sept joueurs de la première équipe (la seconde équipe étant alors fixée), on ne tombe pas non plus dans le cas d'un arrangement car l’ordre n'a pas d'importance.

j. Les cinq députés occupent le même poste et il n'y a pas ici de notion d'ordre. Ce n'est donc pas un arrangement.

 

Solution

a. Arrangement sans répétition ; 336.

b. Pas un arrangement.

c. Pas un arrangement.

d. Arrangement avec répétition ; 59049.

e. Pas un arrangement.

f. Arrangement sans répétition ; 1680.

g. Arrangement avec répétition ; 125.

h. Arrangement sans répétition ; 6.

i. Arrangement avec répétition ; 1048576.

j. Pas un arrangement.

 

2.10. L'ADN est constitué de triplets de quatre nucléotides, représentés par A, T, G et C. Les triplets peuvent comporter plusieurs fois la même base (comme AAA), et deux triplets comportant les mêmes bases mais dans un ordre différent sont différents (ATG n’est pas le même que GTA).

Sachant que chaque triplet amène à la synthèse d'un acide aminé, qu’il y a 20 acides aminés différents et qu’il faut que chaque acide aminé soit codé par au moins un triplet, tentez d'expliquer pourquoi l'unité codante de base est un triplet et non pas un doublet ou un quadruplet.

Solution

Un triplet est un arrangement avec répétition, avec k = 3 et n = 4. Il y a donc 64 triplets possibles, ce qui est suffisant pour coder 20 acides aminés. Si l'on n'avait qu'un doublet, on n'aurait que 16 possibilités, pas assez donc. Avec un quadruplet, on aurait 256 possibilités, ce qui est inutilement beaucoup.

 

Exercice 2-11

Soient $n,k,j\in \mathbb {N}$ tels que $j\leq k$. Démontrer que $A_{n}^{j}\,A_{n-j}^{k-j}=A_{n}^{k}$ de deux façons : par un raisonnement combinatoire ou par le calcul.

Solution

• Combinatoirement : pour choisir, dans un ensemble à n éléments, un k-uplet d'éléments distincts, il suffit de choisir un j-uplet éléments distincts puis, parmi les n – j éléments restants, un (k – j)-uplet d'éléments distincts.
• Calculatoirement : si $k\leq n$, $A_{n}^{j}\,A_{n-j}^{k-j}={\frac {n!}{(n-j)!}}{\frac {(n-j)!}{((n-j)-(k-j))!}}={\frac {n!}{(n-k)!}}=A_{n}^{k}$. Si $k>n$, $A_{n}^{j}\,A_{n-j}^{k-j}=A_{n}^{j}\,0=0=A_{n}^{k}$.

 

Exercice 2-12

Combien de mots sans répétition de lettre peut-on former avec un alphabet de n lettres ?

Solution

Pour tout k de 0 à n, on peut former $A_{n}^{k}$ mots de k lettres. Le nombre total de mots est donc $N=\sum _{k=0}^{n}A_{n}^{k}=\sum _{k=0}^{n}{\frac {n!}{(n-k)!}}=\sum _{j=0}^{n}{\frac {n!}{j!}}$.

 

Remarque : le nombre trouvé est égal à la partie entière de $n!\,\mathrm {e}$ : voir Fonction exponentielle/Annexe/Démonstration que la somme infinie de tous les inverses des k! est égale à e#Corollaire : irrationalité de e.

Exercice 2-13

Combien de mots peut-on former en utilisant uniquement des lettres de BAZAR ?

Solution

On forme d'abord un mot de k lettres (k = 0, 1, 2 ou 3) en utilisant uniquement des lettres de BZR, puis on insère 0, 1 ou 2 A, en choisissant leurs emplacements dans un mot final de k, k + 1 ou k + 2 lettres. Le nombre total de mots (en comptant le mot vide) est donc :

$\sum _{k=0}^{3}A_{3}^{k}\left({\binom {k}{0}}+{\binom {k+1}{1}}+{\binom {k+2}{2}}\right)=\sum _{k=0}^{3}{\frac {3!}{(3-k)!}}\left(1+(k+1)+{\frac {(k+2)(k+1)}{2}}\right)=3\sum _{k=0}^{3}{\frac {(k+2)(k+3)}{(3-k)!}}=3\left(1+6+20+30\right)=171$.