Combinatoire/Arrangements avec répétition

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

fin de la boite de navigation du chapitre

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

Définition

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 avec 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

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

Démarche intuitive

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 :

${\text{Nombre d'arrangements}}=\underbrace {n\times n\times \cdots \times n\times n} _{k{\text{ fois}}}$.

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

Formule des arrangements avec répétition

Pour tout n, k ∈ ℕ, si l'on désigne par $B_{n}^{k}$ le nombre de manières de choisir k objets parmi n objets, chaque objet pouvant être choisi plusieurs fois et l’ordre du choix étant pris en compte, alors :

$B_{n}^{k}=n^{k}$.

C'est aussi le nombre d’applications d'un ensemble à k éléments vers un ensemble à n éléments.

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 $B_{n}^{k}$ introduite ci-dessus est spécifique à cette leçon de Wikiversité.