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.

fin de la boite de navigation du chapitre

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

Définition

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

(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

Démarche intuitive

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 :

${\text{Nombre d'arrangements}}=n\times (n-1)\times (n-2)\times \cdots \times (n-k+2)\times (n-k+1)$.

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

Formule des arrangements sans répétition

Pour tous n, k ∈ ℕ tels que k ≤ n, on désigne par $A_{n}^{k}$ le nombre de manières de choisir k objets parmi n objets, chaque objet ne pouvant être choisi qu'une fois et l’ordre du choix étant pris en compte, et l'on a

$A_{n}^{k}={\frac {n!}{(n-k)!}}$.

Fin du théorème

Cas particuliers

La formule juste au-dessus est bien définie si k ≤ n. En particulier, le dénominateur n'est jamais nul car une factorielle n'est jamais nulle. Si k > n, l’expression n'a pas de sens car n – k est alors négatif, et nous n'avons pas défini la factorielle d'un nombre négatif. Cela est cohérent avec la remarque faite plus haut : on ne peut pas choisir (par exemple) 8 objets différents s'il n'y a que 3 objets.

Cette formule se comporte raisonnablement bien dans les cas limites :

• Si n = k, On a (n – k)! = 0! = 1 et donc la formule se simplifie en $A_{n}^{n}=n!$. On voit ici l'utilité de la convention 0! = 1 prise dans le chapitre précédent.
• Si k = 0, on obtient toujours 1. Effectivement, il n'y a qu'une seule façon de ne choisir aucun objet.

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

On peut énoncer la définition de $A_{n}^{k}$ et démontrer l'égalité ci-dessus plus formellement :

Début d’un théorème

Définition et théorème

Le nombre d'injections d'un ensemble à $k$ éléments dans un ensemble à $n$ éléments, noté $A_{n}^{k}$, est égal à $n(n-1)(n-2)\dots (n-k+2)(n-k+1)={\begin{cases}{\frac {n!}{(n-k)!}}&{\text{si }}k\leq n\\0&{\text{sinon.}}\end{cases}}$

Fin du théorème

Démonstration

Soient N et K deux ensembles finis de cardinaux respectifs n et k.

• Si k > n, il n'existe aucune injection de K dans N et donc $A_{n}^{k}=0$.
• Si k ≤ n, démontrons l'égalité par récurrence sur l'entier k.
  • Si k = 0, il existe une seule application de l'ensemble vide K = ∅ dans l'ensemble N et cette application (de graphe vide) est injective, donc $A_{n}^{0}=1$.
  • Si 1 ≤ k ≤ n, supposons l'égalité vérifiée au rang k – 1 et démontrons-la au rang k.
    Soit x un élément de K. Posons G = K\{x}. Nous avons card(G) = k – 1.
    Considérons l'application de I(K, N) (l'ensemble des injections de K dans N) dans I(G, N) qui, à chaque injection de K dans N, associe sa restriction à G. Chaque élément de I(G, N) a exactement n – k + 1 antécédents dans I(K, N). En effet, il y a autant de façons de prolonger une injection de G dans N en une injection de K dans N que de choix de l'image de x parmi les n – (k – 1) images permises. D'après le lemme des bergers, on a donc $A_{n}^{k}=A_{n}^{k-1}(n-k+1)$. Or (par hypothèse de récurrence) $A_{n}^{k-1}={\frac {n!}{(n-k+1)!}}$. On a donc bien $A_{n}^{k}={\frac {n!}{(n-k+1)!}}(n-k+1)={\frac {n!}{(n-k)!}}$.

 

Exercices à faire

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.