La notion de factorielle est un prérequis à la lecture de cet article. Cette notion est introduite dans ici. Par exemple : $4!=4\times3\times2\times 1$ (se prononce “factorielle 4” et non “4 factorielle”).

Permutation

Le nombre de permutations d’un ensemble est le nombre de “mélanges” que l’on peut effectuer sur cet ensemble.

Par exemple : si nous prenons une pomme rouge (R), une pomme bleu (B) et une pomme verte (V). Combien de mélanges peut-on faire ? Nous avons les mélanges :

• R B V
• R V B
• B V R
• V R B
• B R V
• V B R

Ce qui nous fait 6 mélanges possibles.

Dénombrer (compter le nombre de possibilités) peut être très long ! C’est pourquoi nous avons la formule :

$$\text{Nombre de permutations} = n!$$

n étant le nombre d’éléments dans l’ensemble.

Dans notre exemple, notre ensemble $\{R,V,B\}$ possède 3 éléments. En utilisant notre formule, cela nous fait $n!=3!=3\times 2 = 6$ permutations.

Arrangement

Un arrangement (sans répétition) sur un ensemble est le nombre de possibilités de prendre $k$ éléments dans un ensemble à $n$ éléments (en prenant en compte l’ordre).

En reprenant l’exemple précédent : si nous prenons une pomme rouge (R), une pomme bleue (B) et une pomme verte (V). Combien y a-t-il de façons (en gardant l’ordre) de prendre 2 pommes parmi ces 3 pommes ?

• A B
• B A
• A C
• C A
• B C
• C B

Ce qui nous fait 6. De la même manière, il y a une formule pour calculer le nombre d’arrangement facilement. La voici :

$$A^k_n=\frac{n!}{(n-k)!}$$

Dans notre cas $k = 2$ et $n=3$. Nous avons donc $\frac{3!}{(3-2)!}$ ce qui nous donne $\frac{6}{1}=6$ possibilités.

Pour développer votre intuition, $A^3_3 = 3!$. Et ceci est vrai pour tout $n=k$. L’arrangement est une “extension” du nombre de permutation d’un ensemble, nous cherchons juste à dénombrer le nombre de parties ordonnées de cet ensemble.

Combinaisons

Le nombre de combinaisons d’un ensemble est le nombre de possibilités d’avoir $k$ éléments parmi $n$ éléments (sans prendre en compte l’ordre, sans répétition).

Prenons le même exemple : si nous prenons une pomme rouge (R), une pomme bleue (B) et une pomme verte (V). Combien y a -t-il de façons (sans ordre) de prendre 2 pommes parmi ces 3 pommes ?

• A B
• A C
• B C

Pour un ensemble à 3 éléments, nous avons donc 4 combinaisons.

La formule est encore une fois très similaire :

$$C^k_n=\binom{n}{k}=\frac{n!}{k!(n-k)!}$$

Dans notre exemple : $C^2_3=\binom{3}{2}=\frac{3!}{2!(3-2)!} = \frac{6}{2} = 3$

Pour en savoir plus sur les combinaisons (avec exercice) : Coefficient binomial - k parmi n

Arrangement avec répétitions

L’arrangement avec répétitions est similaire à l’arrangement sans répétition mais ne se calcule pas de la même manière.

Prenons un exemple différent : Combien y a-t-il de possibilités dans un cadenas (décimal) à 3 chiffres ?

Il y a :

• 0 0 0
• 0 0 1
• 0 0 2
• …
• 9 9 9

Ce qui fait 1000 possibilités.

Prenons un autre exemple : Combien y a-t-il de possibilités dans un cadenas (binaire) à 3 chiffres ?

Nous avons :

• 0 0 0
• 0 0 1
• 0 1 0
• 0 1 1
• 1 0 0
• 1 0 1
• 1 1 0
• 1 1 1

Ce qui fait 8 possibilités.

La formule pour dénombrer le nombre d’arrangements avec répétitions est la suivante :

$$n^k$$

Dans notre premier exemple, nous avons $n=10$ et $k=3$ ce qui nous fait $10^3=10\times10\times 10 =100$.

Dans notre deuxième exemple, nous avons $n=2$ et $k=3$ ce qui nous fait $2^3=2\times 2\times2 = 8$

Tableau récapitulatif (avec exemples)

Commentaire

Bien évidemment, le dénombrement ne se limite pas à ces 4 méthodes, il existe une multitude de manières de dénombrer. Si vous voulez voir une autre méthode, nous avons proposons un exercice corrigé ici.