BURHAN.

Arrangements et permutations : Cours de Mathématiques 1BAC Sciences Mathématiques, chapitre Dénombrement

Arrangements et permutations : notion du chapitre Dénombrement du programme de maths 1BAC SM, expliquée pas à pas, avec 2 exemples guidés. Pour les élèves de 1BAC Sciences Mathématiques, option française (BIOF).

Notions du cours (10)

Apprendre avec Burhan

Arrangements et permutations

Étape 1 sur 4

Un podium

Huit coureurs disputent une course. Le podium désigne trois coureurs dans l'ordre : or, argent, bronze. L'ordre compte : Sara en or et Yassine en argent, ce n'est pas l'inverse. Et un coureur ne peut pas occuper deux marches : il n'y a pas de répétition. Pour voir la structure, prends seulement trois coureurs, aa, bb et cc, et deux marches, or et argent. Les podiums sont abab, acac, baba, bcbc, caca et cbcb : 66 podiums, soit 3×23 \times 2. Avec huit coureurs et trois marches, le raisonnement est le même.

Devine : Combien de podiums ?

Combien de podiums différents la course des huit coureurs peut-elle donner ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :512512

Faux.

838^{3} permettrait au même coureur d'occuper deux marches.

Choix B :5656

Faux.

Ce nombre ne tient pas compte de l'ordre : il compte les groupes de trois coureurs.

Choix C :2424

Faux.

8×38 \times 3 ne correspond à aucune suite de choix.

Choix D :336336

Juste.

Juste : 8×7×68 \times 7 \times 6.

Voir la correction complète

La médaille d'or offre 88 choix. L'argent revient à l'un des 77 autres coureurs, quel que soit le premier. Le bronze, à l'un des 66 restants. D'après le principe multiplicatif, il y a 8×7×6=3368 \times 7 \times 6 = 336 podiums.

Continuer : Factorielle, arrangements, permutations →

Étape 2 sur 4

Factorielle, arrangements, permutations

DéfinitionFactorielle ; arrangements ; permutations

Pour n∈N∗n \in \mathbb{N}^{*}, la factorielle de nn est n!=1×2×⋯×nn! = 1 \times 2 \times \dots \times n. Par convention, 0!=10! = 1.

Soit EE un ensemble fini de cardinal n≥1n \geq 1 et pp un entier tel que 1≤p≤n1 \leq p \leq n.

  • Un arrangement de pp éléments de EE est une pp-liste d'éléments de EE deux à deux distincts. On note AnpA_{n}^{p} le nombre de ces arrangements.
  • Une permutation de EE est un arrangement des nn éléments de EE.

Exemplepremières factorielles, permutations de trois lettres

  • 0!=10! = 1, 1!=11! = 1, 2!=22! = 2, 3!=63! = 6, 4!=244! = 24, 5!=1205! = 120 et 6!=7206! = 720.
  • Chaque factorielle s'obtient de la précédente : n!=n×(n−1)!n! = n \times (n - 1)! pour n≥1n \geq 1.
  • Les permutations de {a,b,c}\{a, b, c\} sont (a,b,c)(a, b, c), (a,c,b)(a, c, b), (b,a,c)(b, a, c), (b,c,a)(b, c, a), (c,a,b)(c, a, b) et (c,b,a)(c, b, a) : il y en a 6=3!6 = 3!.

← Étape précédenteContinuer : Nombre d'arrangements →

Étape 3 sur 4

Nombre d'arrangements

Pour le podium, le nombre de choix diminue de 11 à chaque marche. Pourquoi est-ce vrai ? La preuve construit un arrangement élément par élément. Elle applique ensuite le principe multiplicatif, puis réécrit le produit avec des factorielles.

PropriétéNombre d'arrangements et de permutations

Soit n∈N∗n \in \mathbb{N}^{*} et pp un entier tel que 1≤p≤n1 \leq p \leq n. Alors Anp=n(n−1)(n−2)⋯(n−p+1)=n!(n−p)!,A_{n}^{p} = n(n-1)(n-2)\cdots(n-p+1) = \dfrac{n!}{(n-p)!}, le produit comptant pp facteurs. En particulier, le nombre de permutations d'un ensemble à nn éléments est Ann=n!A_{n}^{n} = n!.

Démonstration

Étape 1. Soit EE un ensemble de cardinal nn. On construit un arrangement (x1,…,xp)(x_1, \dots, x_p) en pp étapes : on choisit x1x_1 dans EE, puis x2x_2 dans E∖{x1}E \setminus \{x_1\}, et ainsi de suite. À l'étape kk, les éléments déjà pris forment une partie de EE à k−1k - 1 éléments ; xkx_k est choisi dans son complémentaire, qui a n−(k−1)n - (k - 1) éléments (cardinal du complémentaire), quels que soient les choix précédents.

Étape 2. Si p=1p = 1, An1=nA_{n}^{1} = n. Si p≥2p \geq 2, le principe multiplicatif donne Anp=n(n−1)⋯(n−p+1)A_{n}^{p} = n(n-1)\cdots(n-p+1).

Étape 3. Si p<np < n, (n−p)!=1×2×⋯×(n−p)(n-p)! = 1 \times 2 \times \dots \times (n-p), donc n(n−1)⋯(n−p+1)×(n−p)!=n(n−1)⋯(n−p+1)×(n−p)×⋯×2×1=n!n(n-1)\cdots(n-p+1) \times (n-p)! = n(n-1)\cdots(n-p+1) \times (n-p) \times \dots \times 2 \times 1 = n!. Si p=np = n, le produit vaut déjà n!n! et (n−p)!=0!=1(n-p)! = 0! = 1. Dans les deux cas, Anp=n!(n−p)!A_{n}^{p} = \dfrac{n!}{(n-p)!} ; en particulier, Ann=n!A_{n}^{n} = n!.

À retenirCe qu'il faut retenir de la preuve

Retiens le geste : à l'étape kk, il reste n−(k−1)n - (k - 1) éléments non encore pris, quels que soient ceux déjà choisis. Le principe multiplicatif donne un produit de pp facteurs consécutifs, de nn à n−p+1n - p + 1. En le complétant par (n−p)!(n - p)!, on obtient n!n!.

Vérifie : Combien de choix à l'étape k ?

Dans la preuve, pourquoi l'élément xkx_k a-t-il n−(k−1)n - (k - 1) possibilités ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :Parce que les k−1k - 1 éléments déjà pris ne peuvent plus servir.

Juste.

Juste : on retire de EE une partie à k−1k - 1 éléments, et la formule du complémentaire donne n−(k−1)n - (k - 1).

Choix B :Parce que ce nombre dépend des éléments déjà pris.

Faux.

Justement non : seul leur nombre compte, pas leur identité.

Choix C :Parce que l'ordre des éléments ne compte pas ici.

Faux.

Dans un arrangement, l'ordre compte.

Choix D :Parce qu'un même élément peut être choisi plusieurs fois.

Faux.

Dans un arrangement, les éléments sont deux à deux distincts : aucune répétition.

Voir la correction complète

Avant l'étape kk, on a pris x1,…,xk−1x_1, \dots, x_{k-1}, deux à deux distincts. Ils forment une partie de EE à k−1k - 1 éléments. Son complémentaire dans EE a n−(k−1)n - (k - 1) éléments, d'après la formule du complémentaire. Ce nombre ne dépend pas des éléments pris.

Exempletirages successifs sans remise

  • Une urne contient 55 boules numérotées de 11 à 55. On tire trois boules l'une après l'autre, sans remise, en notant les numéros dans l'ordre. Un résultat est un arrangement de 33 éléments de {1,2,3,4,5}\{1, 2, 3, 4, 5\} : il y en a A53=5×4×3=60A_{5}^{3} = 5 \times 4 \times 3 = 60.
  • L'ordre d'arrivée complet des huit coureurs est une permutation : 8!=40 3208! = 40\,320 ordres possibles.
  • Et le podium : A83=8!5!=336A_{8}^{3} = \dfrac{8!}{5!} = 336.

Arbre de choix horizontal à trois niveaux. B_k désigne la boule numéro k. De la racine partent B_1, des points de suspension et B_5. Après B_1, le deuxième tirage offre B_2, B_3, des points de suspension et B_5, sans B_1 ; après B_5, il offre B_1, B_2, des points de suspension et B_4. Après B_1 puis B_2, le troisième tirage offre seulement B_3, B_4 et B_5. Sur chaque chemin, un numéro n'apparaît jamais deux fois.

Arbre partiel des trois tirages sans remise : cinq branches au premier tirage, quatre au deuxième, trois au troisième, la boule déjà sortie ne revenant jamais.

← Étape précédenteContinuer : Cas limites, puis à toi →

Étape 4 sur 4

Cas limites, puis à toi

Attentionles cas limites

✗ « 0!=00! = 0, donc 4!0!\dfrac{4!}{0!} n'a pas de sens. »

✓ Par convention, 0!=10! = 1. Ainsi A44=4!0!=24=4!A_{4}^{4} = \dfrac{4!}{0!} = 24 = 4! : les permutations sont bien des arrangements. Autre limite : AnpA_{n}^{p} n'est défini que pour p≤np \leq n. Avec trois coureurs seulement, on ne remplit pas cinq places distinctes.

À toi : Un cadenas exigeant

Un cadenas exige un code de quatre chiffres deux à deux distincts. Combien de codes sont possibles ? Écris le résultat avec la notation des arrangements, puis calcule-le. Écris ta réponse avant de dévoiler la correction.

Besoin d'aide ? Indice 1

Les chiffres sont pris dans {0,1,…,9}\{0, 1, \dots, 9\} ; l'ordre compte, et aucune répétition n'est permise.

Encore bloqué ? Indice 2

Le nombre de choix diminue de 11 à chaque chiffre.

Encore bloqué ? Indice 3

Point délicat : compte les facteurs de ton produit ; il doit y en avoir autant que de chiffres du code, et pas davantage.

Voir la solution complète

Un code est une 44-liste de chiffres deux à deux distincts : un arrangement de 44 éléments de {0,1,…,9}\{0, 1, \dots, 9\}, qui en a 1010. D'après le nombre d'arrangements, il y a A104=10×9×8×7=5040A_{10}^{4} = 10 \times 9 \times 8 \times 7 = 5040 codes. C'est environ la moitié des 10 00010\,000 codes du cadenas ordinaire.

← Étape précédenteFin de la notion

S'entraîner sur cette notion

Sources du cours

  • Référentiel BURHAN du chapitre « Dénombrement » (1bac · sciences-mathematiques · mathematiques)