L’étude des permutations d’un ensemble fini remonte aux travaux de Joseph-Louis Lagrange sur la résolution des équations algébriques : en 1770, il observe que les propriétés de résolubilité d’une équation polynomiale dépendent de la façon dont ses racines peuvent être permutées entre elles. Cette idée sera reprise et approfondie par Évariste Galois, qui associera à toute équation un groupe de permutations de ses racines — le point de départ de la théorie qui porte aujourd’hui son nom. Augustin-Louis Cauchy, de son côté, développe dans les années 1840 la notation en cycles encore utilisée aujourd’hui et démontre les premiers résultats structurels sur le groupe symétrique.
Au-delà de son rôle historique, l’ensemble des permutations de {1,…,n}, muni de la composition, constitue le premier exemple substantiel de groupe fini non commutatif (dès que n⩾3) que l’on rencontre en CPGE. Ce chapitre en étudie la structure : notation en cycles, décomposition d’une permutation, et signature — un invariant à valeurs dans {−1,1} dont l’usage sera central au chapitre Déterminants, où il permettra de définir la formule développée du déterminant d’une matrice carrée. Il possède également un intérêt combinatoire propre, indépendant de cette application future.
Permuter les éléments de {1,…,n}, c’est en choisir un réarrangement : une façon de les remettre en correspondance bijective avec eux-mêmes. Cette idée très simple — déjà rencontrée de façon informelle au chapitre Dénombrement pour compter les listes sans répétition — se formalise naturellement à l’aide de la notion de bijection, et l’ensemble de toutes ces bijections hérite d’une structure de groupe pour la composition, dans l’esprit du chapitre Structures algébriques.
Soit n∈N∗. On appelle permutation de {1,…,n} toute bijection de {1,…,n} dans lui-même. On note Sn l’ensemble des permutations de {1,…,n}, muni de la loi de composition ∘.
Une permutation σ∈Sn se représente commodément par le tableau de ses images, dit en notation à deux lignes : σ=(1σ(1)2σ(2)⋯⋯nσ(n))
Pour n=5, la bijection σ définie par σ(1)=3, σ(2)=5, σ(3)=4, σ(4)=1, σ(5)=2 est un élément de S5, noté : σ=(1325344152)
Pour tout n∈N∗, (Sn,∘) est un groupe, appelé groupe symétrique d’indice n. Il n’est pas commutatif dès que n⩾3.
La composition de deux bijections de {1,…,n} dans lui-même est encore une bijection de {1,…,n} dans lui-même, donc ∘ est bien une loi interne sur Sn. Elle est associative, comme toute composition d’applications. L’application identité id{1,…,n} est un élément de Sn, neutre pour ∘. Enfin, toute bijection admet une bijection réciproque : pour σ∈Sn, σ−1∈Sn vérifie σ∘σ−1=σ−1∘σ=id. Ainsi (Sn,∘) est un groupe.
Pour la non-commutativité, il suffit d’exhiber un contre-exemple dans S3 : avec σ=(122133) et τ=(112332), on calcule (σ∘τ)(2)=σ(3)=3 alors que (τ∘σ)(2)=τ(1)=1, donc σ∘τ=τ∘σ.
Pour tout n∈N∗, Sn est un ensemble fini et ∣Sn∣=n!.
Construire une permutation σ∈Sn revient à choisir successivement σ(1), puis σ(2), etc. Il y a n choix possibles pour σ(1) ; une fois σ(1) fixé, il reste n−1 valeurs possibles pour σ(2) puisque σ est injective ; et ainsi de suite, jusqu’à un seul choix possible pour σ(n). Le nombre de permutations est donc n×(n−1)×⋯×1=n!.
Cette croissance est extrêmement rapide : ∣S10∣=3628800 et ∣S20∣ dépasse 2,4×1018. Il est donc hors de question, dès que n dépasse quelques unités, d’étudier Sn en énumérant ses éléments un par un — d’où l’intérêt d’outils structurels comme les cycles.
Encore 20 blocs dans ce document. Le reste du programme est écrit de la même main, avec les figures interactives et votre progression.