Leçons de niveau 13

Combinatoire/Arrangements avec répétition

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Avant de commencer...
  • Assurez-vous (si ce n’est pas déjà fait !) de savoir correctement manipuler les factorielles via les exercices sur les factorielles.
  • L'exercice 2.2 (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
Arrangements avec répétition
Icône de la faculté
Chapitre no 4
Leçon : Combinatoire
Chap. préc. :Arrangements sans répétition
Chap. suiv. :Permutations sans répétition

Exercices :

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

Dans ce chapitre, nous étudierons le deuxième type de comptage important : les arrangements avec répétition. Si vous avez compris le chapitre précédent, celui-ci ne posera pas de problème car le procédé utilisé est exactement le même.

Introduction[modifier | modifier le wikicode]

Définition[modifier | modifier le wikicode]

Pour rappel, ce qui caractérise les arrangements (par rapport aux combinaisons, que nous étudierons plus tard), c’est que l’ordre dans lequel les objets sont choisis est important. Ici, nous considérerons les arrangements avec répétition, ce qui signifie qu'un même objet peut être choisi plusieurs fois. Les exemples suivants peuvent être considérés comme des exemples d'arrangements avec répétition.

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

  • le choix, par 12 personnes, de leurs livres préférés parmi 5 livres ;
  • la remise de k prix à n candidats potentiels, chaque candidat pouvant en recevoir un nombre quelconque. Ce sera notre exemple introductif, que nous détaillerons dans la prochaine section.

Notons que dans le cas des arrangements avec répétition, il est possible que le nombre de choix à effectuer soit plus grand que le nombre d'objets à choisir, puisque chaque objet peut être choisi plusieurs fois.

Exemple introductif[modifier | modifier le wikicode]

Nous devons donc remettre 3 prix à 4 candidats, chacun pouvant éventuellement en recevoir plusieurs. Comme pour le chapitre précédent, nous allons essayer de compter le nombre de possibilités, et comme la dernière fois, on va s'y prendre de manière systématique pour éviter d’en oublier.

La méthode sera exactement la même : nous allons envisager successivement la remise du premier prix, du deuxième prix et du troisième prix.

  • Pour le premier prix, il y a 4 choix possibles correspondant aux 4 candidats.
  • Pour le second prix, il y a toujours 4 choix possibles, et ce quel que soit le récipiendaire du premier prix. En effet, dans ce cas-ci le fait d’avoir reçu le premier prix n'exclut pas de recevoir le second. On obtient donc finalement 16 possibilités pour les 2 premiers prix.
  • Pour le troisième prix, il y a encore une fois 4 choix possibles, pour la même raison. On obtient donc 64 possibilités.

On peut représenter ce raisonnement par un arbre de décision.

Établissement de la formule théorique[modifier | modifier le wikicode]

Wikipédia possède un article à propos de « Arrangement avec répétition ».

Démarche intuitive[modifier | modifier le wikicode]

Généralisons maintenant la démarche que nous venons d'effectuer. Soit le choix de k objets successifs parmi n, avec répétitions possibles. 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 possibilités ;
  • à l'étape trois, on a n possibilités ;
  • de manière générale, à l'étape p, on a n choix possibles.

Comme dans l'exemple, le nombre d'arrangements final est le produit du nombre de choix possibles pour chaque étape. Comme il y a k choix, il y a k étapes et l'on a donc :

.

Cette formule correspond évidemment à la définition de la k-ième puissance de n. On peut donc conclure par cette formule :

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

N.B. Ce nombre s'exprime si simplement qu'il ne nécessite pas de notation dédiée. La notation introduite ci-dessus est spécifique à cette leçon de Wikiversité.