Arrangements et permutations
Activité 1.5 — élire un bureau
Le conseil des élèves élit un président, un vice-président et un secrétaire parmi 18 candidats.
- Décris un résultat. L’ordre compte-t-il ? Un élève peut-il revenir ?
Un bureau est une suite de 3 élèves : (président, vice-président, secrétaire). L’ordre compte, car les fonctions sont différentes. Un élève ne peut pas cumuler deux fonctions.
- Combien de bureaux différents sont possibles ?
\(18 \cdot 17 \cdot 16 = 4896\) bureaux.
- Et si un même élève pouvait cumuler les fonctions ?
\(18 \cdot 18 \cdot 18 = 18^{3} = 5832\) bureaux.
Définition 1.1 — arrangements
Un arrangement de \(p\) éléments pris parmi \(n\) est une suite de \(p\) éléments choisis parmi \(n\) éléments donnés (l’ordre compte).
- Avec répétition (un élément peut revenir) : il y en a \(n^{p}\).
- Sans répétition (éléments distincts, \(p \leq n\)) : il y en a
\[ A_{n}^{p} = \underbrace{n (n-1) (n-2) \cdots (n-p+1)}_{p \text{facteurs}}. \]
Au premier choix, aucun élément n’est pris : \(n\) choix. Au \(k\)-ième choix, \(k - 1\) éléments sont déjà pris : il reste \(n - k + 1\) choix. Le dernier facteur (au \(p\)-ième choix) est donc \(n - p + 1\) : pour le bureau, \(18 \cdot 17 \cdot 16\) et \(16 = 18 - 3 + 1\).
Définition 1.2 — factorielle
Pour tout naturel \(n \geq 1\), \(n! = n (n-1) \cdots 2 \cdot 1\) (lire « factorielle \(n\) »). On pose \(0! = 1\).
Propriété 1.4
Pour \(0 \leq p \leq n\) :
\[ A_{n}^{p} = \frac{n!}{(n-p)!}. \]
Démonstration 1.1
On range les \(n\) éléments en ligne : \(n!\) rangements. Seules les \(p\) premières places comptent (pour le bureau : les 3 premiers d’un classement des 18 candidats). Deux rangements qui ne diffèrent que par l’ordre des \(n - p\) derniers donnent le même arrangement : chaque arrangement provient de \((n-p)!\) rangements (pour le bureau, de \(15!\) classements). On regroupe, puis on divise : \(A_{n}^{p} = \frac{n!}{(n-p)!}\). Par le calcul, les facteurs de \(n - p\) à \(1\) se simplifient et il reste les \(p\) premiers facteurs de \(n!\).
Définition 1.3 — permutations
Une permutation de \(n\) éléments est une façon de les ranger tous dans un ordre : c’est un arrangement sans répétition de \(n\) éléments pris parmi \(n\). Il y en a \(A_{n}^{n} = n!\).
Remarque 1.3
Avec \(p = n\), la formule donne \(A_{n}^{n} = \frac{n!}{0!}\). Pour retrouver \(n!\), il faut \(0! = 1\) : c’est ce qui justifie cette convention. Elle a aussi un sens : \(0!\) compte les façons de ranger zéro objet, et il y en a exactement une (ne rien ranger). À la calculatrice : touches \(x!\) et nPr ; on écrit toujours la formule avant le résultat.
✎ Exercice 1.8
Combien de codes PIN à 4 chiffres existe-t-il ? Combien ont leurs quatre chiffres différents ? Représente les deux ensembles de codes par un diagramme.
codes à 4 chiffres
\(T\)
\(D\)
5040
4960
(\(T\) : tous les codes ; \(D\) : les codes à quatre chiffres différents.)
Codes : suites de 4 chiffres avec répétition, \(10^{4} = 10 \, 000\). Chiffres différents : sans répétition, \(A_{10}^{4} = 10 \cdot 9 \cdot 8 \cdot 7 = 5040\). Les codes à chiffres différents font partie de tous les codes ; les autres sont \(10 \, 000 - 5040 = 4960\).
Relis la définition des arrangements.
Un chiffre peut-il revenir ? Dans chacune des deux questions ?
Codes à chiffres différents : 10 choix, puis 9, puis 8, puis 7.
Un code est une suite de 4 chiffres (l’ordre compte). Avec répétition : \(10^{4} = 10 \, 000\) codes. Sans répétition : \(A_{10}^{4} = 10 \cdot 9 \cdot 8 \cdot 7 = 5040\) codes. Les codes à chiffres différents font partie de tous les codes ; il reste \(10 \, 000 - 5040 = 4960\) codes ayant au moins un chiffre répété.
- Utiliser \(C_{10}^{4}\) : 1234 et 4321 sont deux codes différents.
- Compter 9 choix pour le premier chiffre : un code PIN peut commencer par 0.
✎ Exercice 1.9 ⟵ à faire à la maison
Douze coureurs prennent le départ d’une course. Combien de podiums (premier, deuxième, troisième) sont possibles ? De combien de façons les douze coureurs peuvent-ils franchir la ligne d’arrivée (sans ex æquo) ?
Un podium est une suite de 3 coureurs distincts : \(A_{12}^{3} = 12 \cdot 11 \cdot 10 = 1320\). Un classement complet est une permutation des 12 coureurs : \(12! = 479 \, 001 \, 600\).
Relis la définition des arrangements et celle des permutations.
Un podium est-il une suite ou un groupe ? Un coureur peut-il y figurer deux fois ?
Premier : 12 choix ; deuxième : 11 ; troisième : 10.
Un podium est une suite de 3 coureurs distincts : \(A_{12}^{3} = 12 \cdot 11 \cdot 10 = 1320\) podiums. Un classement complet range les 12 coureurs : c’est une permutation, \(12! = 479 \, 001 \, 600\) classements.
- Utiliser \(C_{12}^{3}\) : le podium (A, B, C) diffère du podium (B, A, C).
✎ Exercice 1.10
Calcule sans calculatrice : \(\frac{10!}{8!}\) ; \(\frac{7!}{5! \cdot 2!}\) ; \(\frac{(n+1)!}{n!}\).
\(\frac{10!}{8!} = 10 \cdot 9 = 90\) ; \(\frac{7!}{5! \cdot 2!} = \frac{7 \cdot 6}{2} = 21\) ; \(\frac{(n+1)!}{n!} = n + 1\).
Relis la définition de la factorielle.
Quels facteurs sont communs au numérateur et au dénominateur ?
\(10! = 10 \cdot 9 \cdot 8!\).
- \(\frac{10!}{8!} = \frac{10 \cdot 9 \cdot 8!}{8!} = 90\).
- \(\frac{7!}{5! \cdot 2!} = \frac{7 \cdot 6 \cdot 5!}{5! \cdot 2} = \frac{42}{2} = 21\).
- \(\frac{(n+1)!}{n!} = \frac{(n+1) \cdot n!}{n!} = n + 1\).
- Simplifier \(\frac{10!}{8!}\) en \(\frac{10}{8}\) : on simplifie des facteurs, pas les nombres sous le « ! ».
✎ Exercice 1.11 ⟵ à faire à la maison
Sans calculatrice, calcule : \(6!\) ; \(\frac{9!}{7!}\) ; \(\frac{8!}{6! \cdot 2!}\) ; \(\frac{5!}{0!}\). Simplifie \(\frac{n!}{(n-2)!}\).
\(6! = 720\) ; \(\frac{9!}{7!} = 9 \cdot 8 = 72\) ; \(\frac{8!}{6! \cdot 2!} = \frac{8 \cdot 7}{2} = 28\) ; \(\frac{5!}{0!} = \frac{120}{1} = 120\) ; \(\frac{n!}{(n-2)!} = n(n-1)\).
Relis la définition de la factorielle et la convention \(0! = 1\).
Dans un quotient de factorielles, quels facteurs se simplifient ?
\(9! = 9 \cdot 8 \cdot 7!\).
\(6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720\) ; \(\frac{9!}{7!} = \frac{9 \cdot 8 \cdot 7!}{7!} = 72\) ; \(\frac{8!}{6! \cdot 2!} = \frac{8 \cdot 7}{2} = 28\) ; \(\frac{5!}{0!} = \frac{120}{1} = 120\) ; \(\frac{n!}{(n-2)!} = \frac{n(n-1)(n-2)!}{(n-2)!} = n(n-1)\).
- Simplifier \(\frac{9!}{7!}\) en \(\frac{9}{7}\) : on ne simplifie pas « les points d’exclamation ».
- Prendre \(0! = 0\) : on convient que \(0! = 1\).
✎ Exercice 1.12
Arnaud fête son anniversaire avec 3 copains et 2 copines. Les 6 enfants descendent le toboggan l’un après l’autre. Combien d’ordres de passage sont possibles
sans contrainte ? b) si Arnaud passe en premier ?
si les deux filles passent en premier ? d) si les deux filles passent l’une juste après l’autre ?
Un ordre de passage est une permutation des enfants. a) \(6! = 720\). b) Arnaud est placé ; on range les 5 autres : \(5! = 120\). c) Les deux filles aux deux premières places : \(2!\) ; les 4 garçons ensuite : \(4!\) ; \(2! \cdot 4! = 48\). d) On colle les deux filles en un seul bloc : on range 5 objets (\(5!\)), puis les filles dans le bloc (\(2!\)) : \(5! \cdot 2! = 240\).
Relis la définition des permutations et le principe multiplicatif.
Quelle est la place la plus contrainte ? Par quoi commencer ?
- Colle les deux filles en un seul « bloc » : combien d’objets faut-il ranger ?
Un ordre de passage est une permutation des 6 enfants. a) \(6! = 720\). b) Arnaud occupe la première place ; on range les 5 autres : \(5! = 120\). c) Les filles aux places 1 et 2 : \(2!\) façons ; les 4 garçons ensuite : \(4!\) façons ; \(2! \cdot 4! = 48\). d) Le bloc des deux filles et les 4 garçons font 5 objets : \(5!\) ; dans le bloc, deux ordres : \(5! \cdot 2! = 240\).
- Oublier que les deux filles peuvent échanger leurs places (\(2!\)).
- Compter \(6!\) en oubliant que le bloc ne forme qu’un seul objet à ranger.