Aller au contenu
Sup et Spé
Télécharger l'application

Accueil › MPSI › Maths

MPSI · Maths · semaine 30

Groupe symétrique

Permutations, cycles et transpositions, décomposition en cycles à supports disjoints, signature d'une permutation et ses propriétés.

Sommaire

Le cours

Résumé en cinq points

  1. SnS_n est le groupe des bijections de {1,…,n}\{1,\ldots,n\}, de cardinal n!n!, non commutatif dès que n⩾3n\geqslant 3.
  2. Un cycle de longueur pp décale circulairement pp éléments et fixe les autres. Deux cycles à supports disjoints commutent.
  3. Toute permutation différente de l'identité se décompose en cycles à supports deux à deux disjoints, de façon unique à l'ordre près. On l'obtient par la méthode des orbites.
  4. Toute permutation est un produit de transpositions. Ce produit n'est pas unique, mais la parité du nombre de facteurs l'est.
  5. La signature est l'unique morphisme de SnS_n dans {−1,1}\{-1,1\} valant −1-1 sur les transpositions. Un cycle de longueur pp a pour signature (−1)p−1(-1)^{p-1}. Elle sert à définir le déterminant.
Pourquoi ce chapitre

Le groupe symétrique est le premier groupe non commutatif que l'on manipule. Il donne un contenu concret au vocabulaire du chapitre sur les structures algébriques :

  • un groupe fini ;
  • des sous-groupes ;
  • un morphisme à valeurs dans un groupe à deux éléments.

Sa première destination en MPSI est la construction des déterminants, puisque la signature est le coefficient de signe qui intervient dans la formule et qui explique pourquoi échanger deux colonnes change le signe.

Les permutations apparaissent aussi dans les exercices de dénombrement et de probabilités, par exemple pour compter :

  • les tirages sans remise ;
  • les dérangements.

Deux savoir-faire sont attendus : décomposer une permutation donnée en cycles à supports disjoints et calculer sa signature. Ces deux opérations reviennent ensuite comme briques de calcul.

Fin de l'aperçu gratuit

Encore 12 parties de cours et 9 corrigés.

Essayer 7 jours gratuitement Sans engagement · cours, exercices et fiches complets

Méthodes et exercices

Exercices classiques corrigés

Rangés par thème, du plus simple au plus exigeant. Difficulté et durée indicatives.

Décomposition en cycles 1

Exercice 1. Décomposer, signer, élever à une puissance ★

Application du cours · 15 min · Khôlle

Dans S9S_9, σ\sigma a pour suite d'images 5,7,9,2,1,6,4,3,8.5, 7, 9, 2, 1, 6, 4, 3, 8.

Décomposer σ\sigma en cycles à supports disjoints, puis en transpositions.

Calculer sa signature, son ordre, σ1000\sigma^{1000} et σ−1\sigma^{-1}.

Voir l'indice

Technique méthode des orbites, puis réduction des exposants.

Voir le corrigé offert
  1. Orbites : 1→5→11 \to 5 \to 1, puis 2→7→4→22 \to 7 \to 4 \to 2, puis 3→9→8→33 \to 9 \to 8 \to 3. Le point 66 est fixe. Donc σ=(1 5)(2 7 4)(3 9 8)\sigma = (1\ 5)(2\ 7\ 4)(3\ 9\ 8). Contrôle : 2+3+3+1=92 + 3 + 3 + 1 = 9.
  2. En transpositions : σ=(1 5)(2 4)(2 7)(3 8)(3 9).\sigma = (1\ 5)(2\ 4)(2\ 7)(3\ 8)(3\ 9). On obtient cinq facteurs.
  3. Signature : ε(σ)=(−1)×1×1=−1\varepsilon(\sigma) = (-1) \times 1 \times 1 = -1, en accord avec la parité des cinq facteurs.
  4. Ordre : les facteurs commutent, donc σk=Id\sigma^k = \mathrm{Id} si et seulement si kk est multiple de 22 et de 33. L'ordre vaut 66.
  5. On a 1000=2×5001000 = 2 \times 500 et 1000=3×333+11000 = 3 \times 333 + 1. Donc σ1000=(2 7 4)(3 9 8)\sigma^{1000} = (2\ 7\ 4)(3\ 9\ 8).
  6. σ−1=(1 5)(2 4 7)(3 8 9)\sigma^{-1} = (1\ 5)(2\ 4\ 7)(3\ 8\ 9).

piège : À l'étape 4, il faut justifier « kk multiple de chaque longueur ». Si σk=Id\sigma^k = \mathrm{Id}, chaque puissance de cycle doit valoir Id\mathrm{Id}, car chaque puissance agit seulement sur son propre support et des supports disjoints ne peuvent pas se compenser.

Signature et parité 1

Exercice 2. Carrés dans Sn ★★

Classiques de khôlle et concours · 20 min · Khôlle

Montrer que ε(σ2)=1\varepsilon(\sigma^2) = 1 pour toute permutation σ\sigma.

En déduire qu'une transposition et un cycle de longueur 44 ne sont jamais des carrés.

Montrer que tout cycle de longueur 33 est un carré.

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Dénombrement des cycles 1

Exercice 3. Dénombrer les cycles ★★

Classiques de khôlle et concours · 25 min · Khôlle

Pour 2≤p≤n2 \leq p \leq n, compter les cycles de longueur pp dans SnS_n.

En déduire la répartition des 2424 éléments de S4S_4 selon leur décomposition, puis le nombre d'éléments d'ordre 22.

Voir le début du corrigé
  1. Une liste de pp éléments distincts se choisit de n!(n−p)!\frac{n!}{(n - p)!} façons.

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Conjugaison et centre 2

Exercice 4. Conjugué d'un cycle ★★

Classiques de khôlle et concours · 20 min · Khôlle

Soit c=(a1 … ap)c = (a_1 \ \dots \ a_p) et ρ∈Sn\rho \in S_n.

Montrer que ρcρ−1=(ρ(a1) … ρ(ap)).\rho c \rho^{-1} = (\rho(a_1) \ \dots \ \rho(a_p)). En déduire que deux cycles de même longueur sont conjugués.

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 5. Centre de Sn ★★

Classiques de khôlle et concours · 20 min · Khôlle

Pour n≥3n \geq 3, montrer que la seule permutation qui commute avec toutes les autres est l'identité.

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Signature et parité 1

Exercice 6. Les permutations paires ★★

Classiques de khôlle et concours · 20 min · D'après un écrit CCINP MP

Pour n≥2n \geq 2, on note AA l'ensemble des permutations paires de SnS_n.

Montrer que AA est un sous-groupe de SnS_n et que son cardinal vaut n!2\frac{n!}{2}.

Voir le début du corrigé
  1. AA est le noyau du morphisme ε\varepsilon, c'est donc un sous-groupe.

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Générateurs de Sn 1

Exercice 7. Familles de transpositions suffisantes ★★★

Approfondissement · 40 min · D'après un écrit CCINP MP

Soit n≥2n \geq 2.

Montrer que toute permutation est produit de transpositions de la forme (1 k)(1 \ k), puis de transpositions de la forme sk=(k  k+1),s_k = (k \ \ k+1), puis de facteurs pris parmi (1 2)(1 \ 2) et c=(1 2 … n).c = (1 \ 2 \ \dots \ n).

Voir le début du corrigé
  1. Pour aa et bb distincts et différents de 11, on a (a b)=(1 a)(1 b)(1 a)(a\ b) = (1\ a)(1\ b)(1\ a), par conjugaison de (1 b)(1\ b) par (1 a)(1\ a). …

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Signature et parité 1

Exercice 8. Morphismes de Sn dans C ★★

Classiques de khôlle et concours · 25 min · Type oral CCINP

Soit n≥2n \geq 2. Déterminer tous les morphismes de groupes φ\varphi de SnS_n dans le groupe multiplicatif C∗\mathbb{C}^*.

Voir le début du corrigé
  1. Toute transposition s'écrit ρ(1 2)ρ⁻¹ (exercice 4). …

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Générateurs de Sn 2

Exercice 9. Les cycles de longueur 3 ★★

Classiques de khôlle et concours · 30 min · Type écrit Mines

Soit n≥3n \geq 3.

Montrer que toute permutation paire est produit de cycles de longueur 33.

Voir le début du corrigé
  1. Une permutation paire s'écrit comme produit d'un nombre pair de transpositions, car ε\varepsilon vaut (−1)k(-1)^k sur un produit de kk transpositions. …

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 10. Nombre minimal de transpositions ★★★

Approfondissement · 60 min · Type oral X-ENS

On note c(σ)c(\sigma) le nombre d'orbites de σ\sigma, points fixes compris.

Soit τ=(a b)\tau = (a \ b).

Montrer que c(στ)=c(σ)+1c(\sigma\tau) = c(\sigma) + 1 si aa et bb sont dans la même orbite de σ\sigma, et c(στ)=c(σ)−1c(\sigma\tau) = c(\sigma) - 1 sinon.

En déduire que le nombre minimal de transpositions nécessaires pour écrire σ\sigma vaut n−c(σ)n - c(\sigma).

Voir le début du corrigé
  1. Cas d'une même orbite. On écrit l'orbite sous la forme (a x1 … xk b y1 … yl)(a\ x_1\ \ldots\ x_k\ b\ y_1\ \ldots\ y_l), avec kk et ll éventuellement nuls. …

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Fiche de cours rédigée à partir du programme officiel de MPSI (2021), chapitre « Groupe symétrique et déterminants », partie A. Elle couvre le groupe des permutations de {1,…,n}\{1,\ldots,n\}, les cycles, les transpositions, la décomposition en cycles à supports disjoints et la signature. Le programme introduit le groupe symétrique en vue de l'étude des déterminants, mais aussi pour son intérêt propre et pour ses interventions en algèbre et en probabilités.