Combinatoire/Arrangements sans répétition

Avant de commencer...
  • Assurez-vous de savoir correctement manipuler les factorielles via les exercices sur les factorielles.
  • L'exercice 2.1 (que l’on trouve sur cette page) vous permettra de préparer ce chapitre via un exercice introductif.
Début de la boite de navigation du chapitre

Nous pouvons dans ce chapitre entrer dans le vif du sujet.

Arrangements sans répétition
Icône de la faculté
Chapitre no 3
Leçon : Combinatoire
Chap. préc. :Factorielles
Chap. suiv. :Arrangements avec répétition

Exercices :

Arrangements
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Combinatoire : Arrangements sans répétition
Combinatoire/Arrangements sans répétition
 », n'a pu être restituée correctement ci-dessus.

La totalité des problèmes dans ce cours pourraient se formuler de la manière suivante : combien y-a-t-il de manières de choisir k objets parmi n objets ?

Si vous trouvez cette question abstraite, n’hésitez pas à penser au premier exemple que nous avons traité, le tirage au sort ; on a k numéros tirés parmi n numéros et le but est de compter combien de tirages différents sont possibles.

Dans le premier chapitre, nous avons vu que cette question pouvait avoir plusieurs réponses selon la manière dont on effectue le tirage :

  • d'une part, on peut soit considérer que chaque numéro peut être tiré plusieurs fois (on parle alors de tirage avec remise) ou au contraire ne peut apparaître qu’à une reprise (on parle alors de tirage sans remise) ;
  • d'autre part, on peut soit considérer que l'ordre de tirage à une importance, soit que l'ordre est indifférent.

Si l’on croise ces deux critères, nous obtenons les quatre cas différents que nous allons étudier dans ce cours. Leurs noms sont résumés dans ce tableau :

Ce que nous étudierons
Sans remise Avec remise
Ordre important Arrangement sans répétition Arrangement avec répétition
Ordre sans importance Combinaison sans répétition Combinaison avec répétition

Pour débuter nous étudierons les arrangements sans répétition.

Introduction

modifier

Définition

modifier

On désigne donc par « arrangement » les choix successifs de k objets parmi n objets. Si les objets choisis sont les mêmes mais que l’ordre dans lequel ils sont choisis est différent, les arrangements sont considérés comme différents. Ici on considérera les arrangements sans répétition (ou « sans remise »), ce qui signifie que les k objets choisis sont différents.

Les situations suivantes peuvent par exemple être considérées comme des arrangements sans répétition :

  • la répartition des trois médailles (or, argent et bronze) lors d'une compétition olympique. Ici les « n objets » sont les concurrents de l'épreuve et les k objets choisis sont les trois vainqueurs. Dire que « l’ordre a de l'importance » signifie ici que ce qui compte, ce n’est pas seulement quels concurrents reçoivent une médaille, mais aussi la nature de la médaille qui est donnée à chacun. En effet, pour un sportif, être sur la plus haute marche du podium est sensiblement différent du fait d’être le second ;
  • le choix, parmi un certain nombre de candidats, du président, du vice-président et du trésorier d'un comité ;
  • le tiercé de tête dans un concours hippique. Ce sera l'exemple introductif.

Notons que dans tous les cas, le nombre d'objets doit être au moins égal au nombre de choix, sinon cela n'a plus de sens. Si l'on doit répartir trois médailles mais qu’il n'y a que deux sportifs en lice, on est dans une situation impossible à résoudre. On suppose donc toujours k ≤ n.

Exemple introductif

modifier

(Si vous ne l'avez pas fait, je vous encourage à essayer de résoudre vous-même l'exercice qui nous servira ici d'exemple ; le lien se trouve dans le cadre en haut de la page.)

Situons à nouveau le contexte : 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. Combien y-a-t-il de podiums possibles ?

Nous pouvons, pour résoudre cet exercice, simplement essayer d'énumérer les solutions, un peu comme nous l'avons fait dans le chapitre introductif pour les tirages du sort. Mais il faut alors le faire de manière à être certain que toutes les possibilités ont bien été envisagées. Pour cela nous avons besoin d'une méthode qui nous assure que nous sommes exhaustifs.

Pour ce faire, nous allons décomposer le problème en plusieurs sous-problèmes que nous traiterons successivement. Plutôt que de chercher directement quelles sont les podiums possibles, nous allons d’abord déterminer le premier, ensuite le second, puis le troisième. Explicitons :

  • tout d’abord, nous devons choisir le cheval qui arrivera le premier. Il y a exactement quatre possibilités : Alpha, Bêta, Gamma et Delta ;
  • ensuite, choisissons le cheval qui arrivera le second. On pourrait penser qu’il y a également 4 solutions ; mais on doit prendre en compte le fait que le premier cheval a déjà été choisi.
Par exemple, si Alpha est premier, il est impossible qu’il soit second également ; il n'y a alors plus que trois solutions : Bêta, Gamma et Delta. On peut tenir le même raisonnement pour tous les vainqueurs possibles. Autrement dit, quel que soit le vainqueur, il y a exactement 3 seconds possibles.
À ce point du raisonnement, comme on a 4 premiers différents à qui on peut adjoindre 3 seconds différents, on en arrive à 12 possibilités différentes pour juste les deux premiers.
On suit le même raisonnement pour déterminer le troisième. Si on connait les deux premiers, il n'y a plus que 2 possibilités pour le troisième, et ce quels que soient les deux premiers. On arrive donc à un total de 24.

On peut représenter cette situation par un arbre. À chaque extrémité correspond un arrangement différent.

On peut faire la même chose avec d'autres chiffres. Considérons par exemple les deux premiers d'une course de cinq chevaux (Alpha, Bêta, Gamma, Delta et Omega).

  • Choisissons d’abord le premier : il y a évidemment cinq possibilités.
  • Ensuite, étant donné qu'on connaît le premier cheval, il reste quatre possibilités pour le second. Cela fait 5×4 = 20 possibilités.

Établissement de la formule théorique

modifier

Démarche intuitive

modifier

Généralisons maintenant les exemples que nous avons étudiés. Soit le choix de k objets successifs parmi n. Combien y-a-t-il de choix possibles ? Nous pouvons suivre la même méthode qu'au-dessus :

  • tout d’abord, choisissons le premier objet. Il y a exactement n possibilités ;
  • à l'étape deux, on a n – 1 possibilités car on ne peut plus choisir le premier objet ;
  • à l'étape trois, on a n – 2 possibilités car on ne peut plus choisir les deux premiers objets ;
  • de manière générale, à l'étape p, on a n – (p – 1) = n – p + 1 choix possibles ;
  • à la dernière étape correspondent donc n – k + 1 possibilités.

Comme dans l'exemple, le nombre d'arrangements final est le produit des choix possibles pour chaque étape. On a donc :

 .

Cette formule correspond à un quotient de deux factorielles (si vous ne vous en rendez pas compte, il est peut-être utile de se référer aux exercices 1.2 et 1.3 sur cette page). On peut donc conclure par cette formule :

Début d’un théorème
Fin du théorème



Nombre d'injections d'un ensemble fini vers un autre

modifier

On peut énoncer la définition de   et démontrer l'égalité ci-dessus plus formellement :

Début d’un théorème
Fin du théorème

Exercices à faire

modifier

Les exercices relatifs à ce chapitre sont les exercices 2.3, 2.4 et 2.5 qui se trouvent sur cette page. Ils consistent à savoir appliquer la formule dans des cas identifiés comme étant des arrangements sans répétition. L'exercice 2.2 servira d'exemple introductif au chapitre suivant ; n'hésitez pas d'ores et déjà à essayer de le faire.