Nombre de permutations d’un ensemble fini à $n$ éléments. Factorielle $n$
1. Permutation d’un ensemble fini à $n$ éléments
Définition 1.
Soit $n$ un entier naturel non nul. Soit $E$ un ensemble fini à $n$ éléments.
On appelle « permutation de $E$ » toute liste ordonnée de tous (les $n$) éléments distincts deux à deux de $E$. Autrement dit, une permutation de $E$ est une « $n$-liste » des éléments distincts deux à deux de $E$.
Définir une nouvelle permutation, c’est dresser la liste de tous (les $n$) éléments de $E$ écrits dans un nouvel ordre.
Exemples
Exercice résolu n°1.
1°) Soit $n$ un entier naturel compris entre $1$ et $5$. Soit $E_n$ un ensemble fini à $n$ éléments. Donner les ensembles ${\mathcal P}_n$, en extension, de toutes les permutations de $E_n$.
2°) Faire une conjecture pour déterminer la progression du nombre $p_n$ de permutations en fonction de $n$.
Méthode
Faire un arbre de dénombrement ou des cases. Les $n$ éléments doivent être deux à deux différents.
1°) Ensemble des permutations pour $n=1$.
$E=\{a\}$. Il n’existe qu’une seule manière de dresser la liste de « tous » les éléments de $E$.
Ici, ${\mathcal P}_1=\{(a)\}$. Le nombre de permutations est donc égal à $1$.
2°) Ensemble des permutations pour $n=2$.
$E=\{a;b\}$. On dresse un arbre à deux branches, puis une branche pour éviter les répétitions.
Il existe exactement deux manières de dresser la liste de « tous » les éléments de $E$.
Ici, ${\mathcal P}_2=\{(a;b);(b;a)\}$. Le nombre de permutations est donc égal à $2$.
Calcul du nombre de permutations, en utilisant les cases :
$$\begin{array}{|c|c|}\hline
1er&2e\\ \hline
2\text{ choix}&1\text{ choix}\\ \hline
\end{array}$$
Par conséquent, le nombre de permutations est $2\times1=2$.
3°) Ensemble des permutations pour $n=3$.
$E=\{a;b;c\}$. On dresse un arbre à trois branches, puis deux, puis une branche pour éviter les répétitions.
Il existe exactement six manières de dresser la liste de « tous » les éléments de $E$.
Ici, ${\mathcal P}_3=\{(a;b;c);(a;c;b);(b;a;c);(b;c;a);(c;a;b);(c;b;a)\}$.
Calcul du nombre de permutations, en utilisant les cases :
$$\begin{array}{|c|c|c|}\hline
1er&2e&3e\\ \hline
3\text{ choix}&2\text{ choix}&1\text{ choix}\\ \hline
\end{array}$$
Par conséquent, le nombre de permutations est $3\times2\times1=6$.
4°) Ensemble des permutations pour $n=4$.
$E={a;b;c;d}$. On dresse un arbre à quatre branches, puis trois, puis deux, puis une branche pour éviter les répétitions. (A faire à la main !)
Il existe exactement 24 manières de dresser la liste de « tous » les éléments de $E$. Ici,
$\begin{array}{rcl}
{\mathcal P}_4&=&\{(a;b;c;d);(a;b;d;c);(a;c;b;d);\\ &&(a;c;d;b);(a;d;b;c);(a;d;c;b);\\
&& (b;a;c;d);(b;a;d;c);(b;c;a;d);\\ && (b;c;d;a);(b;d;a;c);(b;d;c;a);\\
&& (c;a;b;d);(c;a;d;b);(c;b;a;d);\\ &&(c;b;d;a);(c;d;a;b);(c;d;b;a)\\
&& (d;a;b;c);(d;a;c;b);(d;b;a;c);\\ &&(d;b;c;a);(d;c;a;b);(d;c;b;a) \}\\
\end{array}$.
Calcul du nombre de permutations, en utilisant les cases :
$$\begin{array}{|c|c|c|c|}\hline
1er&2e&3e&4e\\ \hline
4\text{ choix}&3\text{ choix}&2\text{ choix}&1\text{ choix}\\ \hline
\end{array}$$
Par conséquent, le nombre de permutations est $4\times3\times2\times1=24$.
5°) Ensemble des permutations pour $n=5$.
$E={a;b;c;d;e}$. On dresse un arbre à cinq branches, puis quatre, trois, deux, puis une branche pour éviter les répétitions. (A faire à la main !)
Ça se complique avec un arbre de dénombrement !
Pour compter le nombre de permutations, on peut procéder avec des cases et des points de suspension.
$$\begin{array}{|c|c|c|c|c|}\hline
1er&2e&3e&4e&5e\\ \hline
5\text{ choix}&4\text{ choix}&3\text{ choix}&2\text{ choix}&1\text{ choix}\\ \hline
\end{array}$$
Par conséquent, le nombre de permutations est $5\times4\times3\times2\times1=120$.
2°) Nous avons obtenu la progression suivantes :
$n=1\longrightarrow p_1=1$.
$n=2\longrightarrow p_2=2$.
$n=3\longrightarrow p_3=6$.
$n=4\longrightarrow p_4=24$.
$n=5\longrightarrow p_5=120$.
Vous avez trouvé la formule ? Sinon avancez aux paragraphes suivants.
2. Nombre de permutations d’un ensemble fini à $n$ éléments.
Propriétés 2.
Soit $n$ un entier naturel non nul, $n\geqslant 1$.
Le nombre $p_n$ de permutations d’un ensemble fini $E$ à $n$ éléments est égal à $n!$ (factorielle $n$).
$$\boxed{\;n! = n(n-1)(n-2)\times\cdots\times2\times1\;}$$
Pour en savoir plus sur ce nombre et les démonstrations de ses propriétés, cliquez sur le lien « Factorielle $n$ ».
Méthode
- On prend la totalité des éléments de $E$
- L’ordre des éléments est très important.
Il s’agit du nombre de permutations d’un ensemble fini à $n$ éléments. - Le nombre de tous les ordres possibles, est égal à $n!$.
3. Exercices résolus
Exercice résolu n°2.
De combien de manières peut on placer 8 personnes, sur un côté, le long d’une table rectangulaire ? Expliquez.
Exercice résolu n°3.
De combien de manières peut on placer 8 personnes, sur un côté, le long d’une table circulaire à 8 places avec au moins un voisin différent ? Expliquez.
Corrigé
Soit $E$ l’ensemble des huit personnes. $E=\{A;B;C;D;E;F;G;H\}$.
- Si on ne tient pas compte du fait que la table est circulaire, c’est-à-dire si la table est rectangulaire, en U ou en fer à cheval, le nombre de permutations est égal à $8! =40320$.
- Or, comme la table est circulaire, pour chaque permutation donnée, si on garde le même ordre et on décale toutes les personnes d’un rang, dans l’un des deux sens, on obtient le même ordre de placement des convives.
- Il y a $8$ manières de faire changer de place aux convives sans changer de permutation. Voir Fig. 3. avec deux des ces rotations avec le même ordre.
- Le nombre de manière de placer différemment les invités est donc ! $\dfrac{8!}{8}=7!=5040$.
- Conclusion. Il y a $7!=5040$ manières différentes de placer 8 personnes autour d’une table avec au moins un voisin différent.
Vues : 2177