Nombre de permutations de $E_n$. Permutations d"un ensemble à $n$ éléments.

Dans cet article, nous voyons que les ensembles à $n$ éléments ($n$ étant un entir strictement positif donné) possèdent $n\times(n-1)\times 2\times 1$ éléments.

Pour arriver à ce résultat, nous commençons par dénombrer le nombre de permutations de l'ensemble $$E_n=\left\{ 1,2, \ldots , n\right\}$$

Ensuite, nous voyons que pour tout entier $n$ strictement positif, un ensemble $E$ à $n$ éléments a pour ensemble de permutations un ensemble en bijection avec l'ensemble des bijections de $E_n$. Le nombre de permutations d'un ensemble fini ne dépend donc que de son nombre d'éléments.

Nombres de permutations de $E_n$

Une permutation de $E_n$ est une bijection de $E_n$ dans lui-même.

Ainsi $\varphi$ est une permutation de $E_n$ si et seulement si tout élément $y$ de $E_n$ possède un et seul antécédent $x$ par $\varphi$, c'est-à-dire un unique élément $x$ tel que $\varphi(x)=y$.

Nous allons commencer par déterminer le nombre de permutations de $E_n$.

On notera pour tout entier strictement positif $n$, $p(n)$ le nombre de permutation de $E_n$.

• Si $n=1$, $E_n=E_1=\left\{ 1 \right\} $, il n'y a qu'une seule fonction $E_n\longrightarrow E_n$, définie par $1\longmapsto 1$. Cette fonction est une permutation de $E_1$ et c'est donc la seule. Donc $p(1)=1$.
• Si $n=2$, $E_2=\left\{ 1,2 \right\} $, il n'y a que deux permutations :  $$\textrm{id}=\left(\begin{array}{cc} 1 &2 \\ 1 &2 \end{array} \right)\ \textrm{et} \ \ \left(\begin{array}{cc} 1 &2 \\ 2 &1 \end{array} \right)  $$ donc $p(2)=2$.

• Si $n=3$, $E_3=\left\{ 1,2,3 \right\} $, il y a six permutations : $$\textrm{id}=\left(\begin{array}{ccc} 1 &2 & 3 \\ 1 &2 & 3\end{array} \right),  \ \left(\begin{array}{ccc} 1 &2 & 3 \\ 1 &3 & 2\end{array} \right),\  \left(\begin{array}{ccc} 1 &2 & 3 \\ 2 &1 & 3\end{array} \right)$$ 
  $$\left(\begin{array}{ccc} 1 &2 & 3 \\ 2 &3 & 1\end{array} \right), \left(\begin{array}{ccc} 1 &2 & 3 \\ 3 &1 & 2\end{array} \right),  \ \left(\begin{array}{ccc} 1 &2 & 3 \\ 3 &2 & 1\end{array} \right)   $$
  donc $p(3)=6$.

Plus généralement, pour construire une permutation de $E_n$, il faut choisir l'image de 1, puis l'image de 2, ...., puis l'image de $n$ de sorte à ce que les $n$ nombres aient une image différente.

Regardons de combien de façons on peut construire une permutation $\sigma$ de $E_n$ : 

Initialisation.

• Etape 1 :$\sigma(1)$ peut être n'importe quel nombre de $E_n$. Cela nous donne $n$ possibilités.
• Etape 2 : $\sigma(2)$ peut être n'importe quel nombre de $E_n$ sauf $\sigma(1)$, il y a $n-1$ tels nombres. 
  Pour chacun des $n$ choix de $\sigma(1) $, nous avons $(n-1)$ possibilités pour $\sigma(2) $. Il y a donc $n\times (n-1)$ possibilités pour $(\sigma(1),\sigma(2))$.

Hérédité.

• Etape $k$ implique Etape $k+1$ : Supposons qu'à l'étape $k<n$, nous avons $n\times(n-1)\times \ldots\times (n-(k-1))$ possibilités pour $(\sigma(1),\sigma(2),\ldots,\sigma(k))$.

Alors $\sigma(k+1)$ peut être choisi dans $E_n$ sauf parmi $\sigma(1),\ldots,\sigma(k) $, c'est-à-dire parmi $n-k$ éléments. Ainsi pour compléter chacun des $n\times(n-1)\times \ldots\times (n-(k-1)) $ $k$-uplets $(\sigma(1),\sigma(2),\ldots,\sigma(k))$ en $(k+1)$-uplet $(\sigma(1),\sigma(2),\ldots,\sigma(k),\sigma(k+1))$, il y a $n-k$ possibilités. 

Cela fait donc $n\times(n-1)\times \ldots\times (n-(k-1))\times(n-k) $ possibilités pour $(\sigma(1),\sigma(2),\ldots,\sigma(k),\sigma(k+1))$. 

Conclusion. 

Ainsi par récurrence, nous avons montré que $p(k)=n\times(n-1)\times\ldots\times (n-(k-1))\times (n-k) $

En particulier, pour $k=n $, nous avons $p(n)=n\times (n-1)\times (n-(n-1))=n\times(n-1)\times\ldots\times 1$. 

On note pour tout entier $n>0$,

$$n!=n\times (n-1)\times (n-(n-1))=n\times(n-1)\times\ldots\times 1 $$

Et par convention : $0!=1$.

Le nombre de permutations de $E_n$ est donc $n!$.

Bijection $\mathfrak S_n\longrightarrow \mathfrak S(E)$

Dans cet partie: 

• $n$ est une entier strictement positif 
• $E$ désigne un ensemble fini de cardinal $n$
• $E_n=\left\{1,2,\ldots,n \right\}$
• $\mathfrak S(E)$ désigne l'ensemble des permutations $E\longrightarrow E$ 
• $\mathfrak S(E)$ désigne l'ensemble des permutations $E\longrightarrow E$ 

Dans cette partie, nous construisons une bijection $\mathfrak S(E) \longrightarrow \mathfrak S_n$. 

En conséquence de cette bijection, on obtiendra que le nombre d'éléments de $\mathfrak S(E)$ est égal au nombre d'éléments de $\mathfrak S_n$ (voir l'article sur les ensembles finis).

Soit $\varphi:E_n\longrightarrow E$ une bijection.

Ainsi $E=\left\{\varphi(1),\varphi(2),\ldots,\varphi(n) \right\}$

Pour toute permutation $\sigma$ de $E_n$, on note $\hat{\sigma}$ la fonction de $E\longrightarrow E$ définie pour tout $i$, $1\leq i\leq n$ par

$$(1)\ \ \ \ \ \ \hat{\sigma}(\varphi(i))=\varphi(\sigma(i)) $$

Propriété 1. Pour tout $\sigma\in\mathfrak S_n$, $\hat{\sigma}$ est une bijection $E\longrightarrow E$.

Démonstration. Il s'agit de démontrer que $\hat{\sigma}$ est une $E\longrightarrow E$ est surjective et injective.

• Surjectivité : si $y=\varphi(j)\in E$, alors $x=\sigma^{-1}(\varphi(j))$ est un antécédent de $y$ : 

$$\hat{\sigma}(x)=\hat{\sigma}\left(\varphi\left(\sigma^{-1}(j)\right)\right)=\varphi\left(\sigma\left(\sigma^{-1}(j) \right)\right)=\varphi(j)=y$$

• Injectivité : Soit $x=\varphi(i)$ et $x'=\varphi(k)$ tels que $\hat{\sigma}(x)=\hat{\sigma}(x')$, c'est-à-dire $\hat{\sigma}(\varphi(i))=\hat{\sigma}(\varphi(k))$, ou encore $\varphi\left(\sigma(i)\right)=\varphi\left(\sigma(k)\right)$. On en déduit que $\sigma(i)=\sigma(k)$ et donc puisque $\sigma$ est injective, $i=k$. 

On a donc montré que nous avons une fonction $\Phi:\mathfrak S_n \longrightarrow \mathfrak S(E)$ définie par 

$$\Phi(\sigma)=\hat{\sigma} $$

D'après $(1)$, $\Phi(\sigma)\circ \varphi=\varphi\circ \sigma $, d'où

$$(2)\ \ \ \ \ \ \Phi(\sigma)=\varphi\circ \sigma\circ \varphi^{-1} $$

Propriété 2. $\Phi$ est surjective.

Démonstration. Soit $\alpha\in\mathfrak S(E)$. 

Nous allons créer une permutation $\sigma$ de $E_n$ telle que $\alpha=\Phi(\sigma)=\hat\sigma$. 

Remarquons d'après $(2)$ que $\sigma$ et $\alpha$ doivent vérifier $\alpha =\varphi\circ \sigma\circ \varphi^{-1} $ qui équivaut à $\varphi^{-1}\circ\alpha\circ \varphi=\sigma $. 

On définit donc la fonction $\sigma:E_n\longrightarrow E_n$ de la manière suivante :  

$$\sigma=\varphi^{-1}\circ\alpha\circ \varphi$$ 

La fonction composée $\sigma$ est donc une bijection $E_n \longrightarrow E_n$. C'est un élément de $\mathfrak S_n$.  

De plus, cette fonction $\sigma$ est un antécédent de $\alpha$ par $\Phi$ :

$$\Phi(\sigma)= \Phi\left(\varphi^{-1}\circ\alpha\circ \varphi\right)=\varphi\circ\left(\varphi^{-1}\circ\alpha\circ \varphi\right)\circ\varphi^{-1}=\left(\varphi\circ\varphi^{-1}\right)\circ\alpha\circ \left(\varphi\circ\varphi^{-1}\right)$$

Donc 

$$\Phi(\sigma)=\textrm{id}_E\circ \alpha\circ\textrm{id}_{E_n}=\alpha $$

Propriété 3. $\Phi$ est injective.

Preuve. Soit $\sigma $ et $\tau$ deux éléments de $\mathfrak S_n$ tels que $\Phi(\sigma)=\Phi(\tau) $. Alors $\varphi\circ \sigma\circ \varphi^{-1} =\varphi\circ \tau\circ \varphi^{-1} $ d'où en composant à droite et à gauche par $\varphi $ et $\varphi^{-1} $ respectivement, $\varphi=\tau$.

D'après les propriétés 3 et 4, on obtient donc que $\Phi$ définit une bijection entre $\mathfrak S_n$ et $\mathfrak S(E)$. Par ailleurs, sa bijection réciproque est donnée par $\Phi(\alpha)=\varphi^{-1} \circ\alpha\circ \varphi$.

On en déduit entre autres que$\mathfrak S_n$ et $\mathfrak S(E)$ ont le même nombre d'éléments. 

Propriété 4. Dans un ensemble $E$ quelconque à $n$ éléments, il y a $n!$ permutations.

Et après

 Pour les lecteurs intéréssés par le début de la théorie des groupes, on pourra consulter l'article sur le goupe des permutations $\mathfrak S_n$.