Théorie > Combinatoire > Dénombrement

Arrangements

Sans répétition

Supposons maintenant être en présence de $n$ objets distincts $\{a_1, \ldots, a_n\}$. Nous nous demandons cette fois-ci de combien de manière on peut prendre $k$ objets parmi ceux-ci et les ranger. Cela revient à se demander de combien de façons différentes on peut choisir $k$ objets parmi les $n$, l'ordre des choix ayant une importance. On parle du nombre d'arrangements de $k$ objets parmi $n$.

Exemples concrets :
  1. On possède $6$ livres et une étagère pouvant accueillir $4$ livres. De combien de manières peut-on remplir l'étagère (l'ordre des livres ayant son importance) ?
  2. Combien existe-t-il de nombres à exactement $3$ chiffres distincts, tous non-nuls?

Le nombre d'arrangements de $k$ objets parmi $n$ (avec $0 \leq k \leq n$) est donné par
$$A^k_n = \frac{n!}{(n-k)!}.$$

Démonstration :
Tout comme pour les permutations, on a d'abord $n$ façons de choisir le premier objet, puis $(n-1)$ façons de choisir le deuxième objet, ... et $(n-k+1)$ façons de choisir le $k^\text{ème}$ objet. On a donc $\displaystyle n \cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n-k)!}$ façons de choisir $k$ objets parmi $n$ (l'ordre des choix ayant de l'importance).

Solutions des exemples :
  1. On a $n = 6$ et $k = 4$. le nombre de façons de remplir l'étagère est donc égal à
    $$\frac{6!}{(6-4)!} = \frac{720}{2} = 360.$$
  2. Pour construire un nombre à trois chiffres distincts non-nuls, on a $9$ chiffres disponibles, et on désire en choisir $3$ et les ordonner pour construire le nombre. Il y a donc autant de tels nombres que d'arrangements de $3$ objets parmi $9$, c'est-à-dire
    $$\frac{9!}{(9-3)!} = 9\cdot 8 \cdot 7 = 504.$$

Avec répétitions

Les arrangements avec répétitions ne désignent pas le même phénomène que les permutations avec répétitions. Ici, les $n$ objets que nous considérerons seront toujours distincts, mais on pourra cette fois choisir plusieurs fois le même objet dans notre arrangement (d'où le terme répétition). Cette situation n'a donc plus réellement de sens avec les livres sur une étagères, à moins que l'on dispose de chaque livre en une infinité d'exemplaires (et qu'on peut donc mettre plusieurs exemplaires du même livre sur notre étagère).

Exemples concrets :
  1. Dix balles numérotées de $1$ à $10$ sont placées dans une urne. A quatre reprises, on pioche une balle, note son numéro et remet la balle dans l'urne. Combien de résultats différents peut-on obtenir après ce processus (l'ordre des numéros notés ayant son importance) ?
  2. On dispose de $2$ sortes de bonbon, chacune en grande quantité. De combien de manières peut-on donner un bonbon à chaque élève d'une classe de $20$ étudiants ?

Le nombre d'arrangements avec répétitions de $k$ objets parmi $n$ est donné par
$$B_n^k = n^k.$$

Démonstration :
On doit effectuer $k$ choix, et pour chacun de ceux-ci, on a $n$ possibilités. Le nombre de façons d'effectuer ces choix est donc simplement $n \cdot \ldots \cdot n = n^k$.

Solutions des exemples :
  1. On a dix balles, d'où $n = 10$, et on effectue quatre tirages, d'où $k = 4$. On a donc $10^4 = 10000$ résultats possibles.
  2. Il y a ici $n = 2$ objets, un objet représentant une sorte de bonbon. On choisit, à $k = 20$ reprises, une des deux sortes. Il y a donc $2^{20}$ manières de distribuer des bonbons aux élèves.