Groupes
\(\def\up{{\uparrow}}\def\d{{\downarrow}}\def\lf{{\leftarrow}}\def\rg{{\rightarrow}}\def\rel#1{\,{\mathscr #1}\,}\def\N{{\mathbb N}}\def\Z{{\mathbb Z}}\def\Q{{\mathbb Q}}\def\R{{\mathbb R}}\)

Introduction

Nous allons consacrer ce chapitre à l'étude du jeu du taquin. Ce casse-tête solitaire a été inventé par Sam Loyd aux États-Unis à la fin du 19ème siècle. Il se présente sous la forme d'un plateau de \(16\) cases réparties sur \(4\) lignes et \(4\) colonnes sur lesquelles sont placées \(15\) pièces numérotées de \(1\) à \(15\) con­for­mé­ment à la figure ci-dessous. L'une des 16 cases est vide pour permettre aux \(15\) pièces de cou­lis­ser le long des lignes ou des colonnes.

Configuration*(*) Vous pouvez saisir la votre puis va­li­der. Case vide = 16 : pro­po­sée par Sam Loyd

Jeu du taquin. Cliquez sur une pièce pour la pousser vers la case vide (elle entraîne les pièces sur son chemin).

Le but du jeu est de ranger les 15 pièces dans l'ordre croissant de \(1\) à \(15\) en faisant coulisser une pièce \(n\) adjacente à la case vide dans cette case vide, libérant ainsi la case sur laquelle elle était ini­tia­le­ment placée pour un futur mouvement. Sam Loyd proposa la somme de $1.000 au premier qui trouverait une solution. Vous pouvez essayer vous-même avec le simulateur ci-dessus qui vous permet de faire glisser jusqu'à trois pièces alignées vers la case vide d'un seul coup plutôt que les déplacer les unes après les autres.

Ce jeu a été décliné de très nombreuses façons, par exemple en remplaçant les nombres par des portions d'une image à reconstituer à la manière d'un puzzle. Le célèbre Rubik's Cube est en quelque sorte une extension à trois dimensions de ce pro­blè­me. L'objectif de ce chapitre est de comprendre pourquoi Sam Loyd ne risquait pas de perdre ses $1.000 et de trouver comment résoudre d'autres configurations quand elles admettent une solution.

Nous avons étudié aux chapitres précédents les ensembles, les relations qui pouvaient les lier et leur cardinalité. Nous allons à présent les animer en les équipant de quelques rouages.

Lois de composition et structures

Magmas

On appelle loi de composition interne sur un ensemble \(X\) toute application \(\diamond\) de \(X\times X\) dans \(X\). Le couple \((X,\diamond)\) est appelé un magma.

Dans la suite, \((X,\diamond)\) désigne un magma. On note généralement une loi de composition de manière infixe, soit \(x\;{\color{#FF0}\diamond}\;y\) plutôt que préfixe \({\color{#88F}\,\diamond}(x,y)\). L'ad­di­tion et la multiplication définies sur l'ensemble des entiers naturels au cha­pi­tre Combinatoire sont donc des lois de com­po­si­tion internes. La réunion \(\cup\) et l'intersection \(\cap\) sur l'ensemble \({\mathscr P}(X)\) des parties d'un ensemble \(X\) sont des lois de composition internes. La composition des applications \(\circ\) d'un ensemble \(X\) dans lui-même, définit une loi de com­po­si­tion interne sur \(X^X\). La concaténation \(\cdot\) est une loi de composition interne sur l'ensemble des mots définis sur un alphabet fini \(\Sigma\) : \(bon.jour=bonjour\) sur \(\Sigma=\{a,\ldots,z\}\).

Partie stable. Une partie \(A\) d'un ensemble \(X\) muni d'une loi de composition interne \(\diamond\) est dite stable pour la loi \(\diamond\) si et seulement si tous les composés d'éléments de cette partie restent dans cette partie :

\begin{equation} \forall (x,y)\in A \times A\quad x\diamond y \in A. \end{equation}

Dans ce cas, la loi de composition \(\diamond\) restreinte aux éléments de \(A\) est une loi de composition in­ter­ne sur \(A\), appelée loi induite par \(\diamond\) sur \(A\), et on conserve la même notation pour le magma \((A,\diamond)\). L'ensemble des entiers pairs est une partie stable pour la loi d'addition \(+\) sur l'ensemble des entiers naturels \(\N\). L'ensemble des bijections d'un ensemble \(X\) sur lui-même est une partie stable de \(X^X\) pour la loi de compositions des applications \(\circ\) (cf. exercice).

Associativité. Une loi de composition interne \(\diamond\) est dite associative si et seulement si

\begin{equation} \forall (x,y,z)\in X^\quad x\diamond(y\diamond z)= (x\diamond y)\diamond z. \end{equation}

Dans ce cas le magma est dit magma associatif. L'addition et de la multiplication sur les entiers na­tu­rels sont deux lois associatives, c'est cette propriété qui nous permet de nous affranchir des pa­ren­thè­ses dans l'expression \(x+y+z\) et l'ex­pres­sion \(x\times y\times z\). Ces expressions n'auraient pas de sens si ces lois n'étaient pas associatives. Le magma \((X^X,\circ)\) est associatif (cf. exercice).

Commutativité. On dit que deux éléments \(x\) et \(y\) de \(X\) commutent si et seulement si

\begin{equation} x\diamond y = y \diamond x. \end{equation}

On appelle centre d'un magma, le sous-ensemble noté \(Z_X\) des éléments de \(X\) qui commutent avec n'im­por­te quel élément de \(X\). Si \(Z_X=X\), c'est-à-dire si deux éléments quel­con­ques de \(X\) commutent, le magma est appelé magma commutatif. C'est le cas de l'ensemble \(\N\) pour les deux lois d'addition et de multiplication. En revanche la loi de composition \(\circ\) des applications n'est en gé­né­ral pas com­mu­ta­ti­ve pour le magma \((X^X,\circ)\) (composez les applications \(n\mapsto n+1\) et \(n\mapsto 2n\) de \(\N^\N\)).

Élément neutre. On appelle élément neutre pour la loi \(\diamond\) tout élément \(e\in X\) tel que

\begin{equation} x\diamond e = e \diamond x=x. \end{equation}

Il est nécessairement unique (preuve en exercice). Un magma dont la loi possède un élément neutre est dit magma uni­fè­re. L'entier \(0\) est l'élément neutre pour l'addition dans \(\N\) et l'entier \(1\) est l'élé­ment neutre pour la mul­ti­pli­ca­tion dans \(\N\). L'ensemble \(X\) est l'élément neutre pour l'intersection sur l'ensemble \({\mathscr P}(X)\) des parties de \(X\). Le magma \((X^X,\circ)\) est uni­fère d'élément neutre l'application iden­ti­que \(\text{Id}_X\).

Distributivité. Si un ensemble \(X\) est muni de deux lois de compositions internes \(\star\) et \(\diamond\), on dit que \(\star\) est distributive à gauche (resp. distributive à droite) sur \(\diamond\) si et seulement si

\begin{align} \forall (x,y,z)\in X^3\ \ x\star(y\diamond z) &= (x\star y)\diamond(x\star z),\\ \text{resp.}\ \ \forall (x,y,z)\in X^3\ \ (x\diamond y)\star z &= (x\star z)\diamond(y\star z). \end{align}

Si la loi est à la fois distributive à gauche et à droite, on dit simplement qu'elle est distributive. La mul­ti­pli­ca­tion \(\times\) est distributive sur l'addition \(+\) dans \(\N.\)

\[\forall (a,b,c)\in\N^3\quad a\times(b+c)=(a\times b)+(a\times c).\]

L'intersection \(\cap\) est distributive par rapport à la réunion \(\cup\) sur l'ensemble \({\mathscr P}(X)\) des parties d'un en­semb­le \(X\), \[\forall (A,B,C)\in{\mathscr P}(X)^3\quad A\cap(B\cup C)=(A\cap B)\cup(A\cap C).\]

Démontrez qu'un élément neutre d'un magma unifère est nécessairement unique.
Démontrez que la réunion est également distributive sur l'intersection sur l'ensemble \({\mathscr P}(X)\) des parties d'un en­semb­le \(X\).
Démontrez que la différence symétrique \(\Delta\) est une loi de composition interne associative sur l'ensemble \({\mathscr P}(X)\) des parties d'un en­semb­le \(X\). On rappelle que \(X\;\Delta\; Y=(X\cup Y)\setminus(X\cap Y)\).

Éléments réguliers. On appelle élément régulier à gauche (resp. élément régulier à droite) tout élé­ment \(r\in X\) tel que

\begin{align} \forall (x,y)\in X\times X\quad r\diamond x&=r\diamond y\ \Rightarrow\ x=y,\\ \text{resp.}\ \ \forall (x,y)\in X\times X\quad x\diamond r&=y\diamond r\ \Rightarrow\ x=y. \end{align}

Ces identités expriment que l'on peut simplifier une équation à gauche et/ou à droite par un élément régulier à gauche et/ou à droite. Un élément qui est la fois régulier à gauche et à droite est dit élément ré­gu­lier. L'élément neutre pour une loi de composition est nécessairement régulier. Dans \(\N\), tout élément est régulier pour l'addition et tout élément non-nul est régulier pour la multiplication. Dans \({\mathscr P}(X)\) le seul élément régulier pour l'in­ter­sec­tion est l'élément neutre \(X\).

Éléments symétrisables. Supposons à présent que le magma \((X,\diamond)\) soit unifère d'élément neutre \(e.\) On dit qu'un élément \(x\in X\) est symétrisable à gauche (resp. symétrisable à droite) s'il existe (au moins) un élément \(x'\in X\) tel que

\begin{align} x'\diamond x&=e,\\ \text{resp.}\ \ x\diamond x'&=e. \end{align}

On dit alors que \(x'\) est un symétrique à gauche (resp. symétrique à droite) de \(x\). On dit que \(x\) est symétrisable s'il est à la fois symétrisable à gauche et à droite.

Soit \((X,\diamond)\) un magma associatif et unifère d'élément neutre \(e\) et \(x\in X\).
  1. Si \(x\) est symétrisable à gauche (resp. à droite), il est régulier à gauche (resp. à droite) ;
  2. Si \(x\) est symétrisable, son symétrique à gauche est égal à son symétrique à droite ;
  3. Si \(x\) est symétrisable, il admet un unique symétrique, on l'appelle le symétrique de \(x\).
  4. Le composé de deux éléments symétrisables est symétrisable.

L'entier naturel 0 est le seul élément qui admet un symétrique (lui-même) pour l'addition dans \(\N\), et \(1\) est le seul élément qui admet un symétrique (lui-même à nouveau) pour la mul­ti­pli­ca­tion dans \(\N\). L'ensemble des entiers relatifs \(\Z\) contient par construction, en sus des entiers naturels, tous leurs symétriques pour l'addition. En revanche pour la multiplication, seuls deux éléments de \(\Z\) admettent un symétrique, ce sont \(-1\) et \(1\). Les éléments sy­mé­tri­sa­bles pour la loi de composition des ap­pli­ca­tions sont les bijections.

Démontrez la proposition précédente.

Solution d'une équation. C'est l'existence de symétriques qui permet de résoudre une équation. En effet, soit \((X,\diamond)\) un magma associatif unifère et \(a\) et \(b\) deux éléments de \(X\). Considérons l'équa­tion

\begin{equation} \label{eq:eqmagma} a\diamond x=b \end{equation}

Si \(a\) admet un symétrique à gauche \(a'\), alors il existe une unique solution :

\begin{align*} a'\diamond(a\diamond x)&=a'\diamond b\\ (a'\diamond a)\diamond x&=a'\diamond b\quad\text{par associativité},\\ e\diamond x&=a'\diamond b\quad\text{par symétrique à gauche},\\ x&={\color{#88F}a'\diamond b}\quad\text{car \(e\) est l'élément neutre}. \end{align*}

Si \(a\) admet un symétrique à droite \(a''\), alors \(x={\color{#FC0}a''\diamond b}\) est une solution, en effet

\begin{align*} a\diamond(a''\diamond b)&=(a\diamond a'')\diamond b\quad\text{par associativité},\\ &=e\diamond b\quad\text{par symétrique à droite},\\ &=b\quad\text{car \(e\) est l'élément neutre}. \end{align*}

D'après la proposition précédente, on sait que si \(a\) est symétrisable, \(a'=a''\) et dans ce cas \(a'\diamond b\) est l'unique solution de l'équation \((\ref{eq:eqmagma}).\) L'étude est symétrique pour l'équation \(x\diamond a=b\) pour laquelle \(b\diamond a'\) est l'unique solution.

Vocabulaire. Les différentes combinaisons de propriétés que peut satisfaire la loi de composition d'un magma \((X,\diamond)\) définissent de nouveaux objets très utilisés en mathématiques et en informatique. Un magma associatif est qualifié de semi-groupe. Un magma associatif et unifère est qualifié de mo­noï­de. Un magma associatif, unifère et où tout élément est symétrisable est qualifié de groupe, nous y reviendrons plus loin.

Les notions abstraites et les manipulations formelles que nous venons d'étudier semblent s'adresser exclusivement à un public de ma­thé­ma­ti­ciens et peuvent paraître dénuées de tout intérêt pratique. Elles sont utilisées en permanence en in­for­ma­ti­que et en particulier en théorie des langages qui fournit un cadre scientifique pour l'étude des langages de programmation.

Lois de composition externe

On appelle loi de com­po­si­tion externe sur un ensemble \(X\) à domaine d'opé­ra­teurs \(\Omega\) toute application de \(\Omega\times X\) dans \(X\).

Partie stable. De la même manière que pour une loi de composition interne, on dit qu'une partie \(A\) d'un ensemble \(X\) muni d'une loi de composition externe \(\star\) est stable pour cette loi si et seulement si

\begin{equation} \forall(\alpha,x)\in\Omega\times X\quad \alpha\star x\in A. \end{equation}

Dans ce cas en restreignant la loi aux éléments de \(A\), il s'agit encore d'une loi externe, appelée loi induite par \(\star\) sur \(A\).

Si l'on dispose d'un magma unifère associatif \((X,\diamond)\) d'élément neutre \(e\), on peut par exemple cons­trui­re une loi de composition externe \(\cdot\) sur \(X\) à domaine d'opérateur \(\N\) en itérant la loi interne : c'est l'application puissance \(\N\times X\rightarrow X\) définie par

\begin{equation} (n,x)\mapsto n\cdot x:=\begin{cases} e&\text{si}\ n=0,\\ \overbrace{x\diamond x\diamond\cdots\diamond x}^{n\ \text{fois}\ x}&\text{si}\ n > 0. \end{cases} \end{equation}

Quand la loi interne \(\diamond\) est notée comme une loi multiplicative, on utilise souvent l'écriture ex­po­nen­tiel­le \(x^n\) plutôt que \(n\cdot x\) pour désigner l'élément \(x\diamond x\diamond\cdots\diamond x\) et on en déduit im­mé­dia­te­ment que \begin{equation} \label{eq:additivitéexp} x^n\diamond x^m=x^{n+m}. \end{equation} Nous étudierons d'autres lois de compositions externes dans les prochains chapitres.

Morphismes

Une relation binaire, une loi de composition interne ou externe sur un ensemble \(X\), définissent des structures sur cet ensemble. Si deux ensembles \(X\) et \(Y\) sont munis de structures, il est naturel de s'intéresser aux applications \(f:X\rightarrow Y\) qui les respectent. Pour faire une métaphore, si une tige coulisse dans un cylindre (la relation binaire sur l'ensemble \(X\) des pièces en acier), et qu'on réalise un filetage de ces pièces pour les transformer (via l'application \(f\)) respectivement en boulon et en écrou (dans l'ensemble \(Y\) de la visserie), ces deux pièces doivent encore s'assembler (la relation bi­nai­re sur l'ensemble \(Y\)).
Soit \(f:X\rightarrow Y\) une application. Si \(X\) et \(Y\) sont munis res­pec­ti­ve­ment des re­la­tions binaires \(\rel{R}\) et \(\rel{S}\), on dit que \(f\) est un morphisme si et seulement si \begin{equation} x{\rel{R}}x'\Rightarrow f(x)\rel{S}f(x'). \end{equation} Si \(X\) et \(Y\) sont munis respectivement des lois de composition internes \(\diamond\) et \(\star\), on dit que \(f\) est un morphisme si et seulement si \begin{equation} f(x\diamond x')=f(x)\star f(x'). \end{equation}

Nous avons déjà rencontré un morphisme au chapitre Combinatoire. Une application croissante entre deux ensembles ordonnés respecte la relation d'ordre, c'est un morphisme d'ensembles or­don­nés. La notation exponentielle introduite en \((\ref{eq:additivitéexp}\)) définit implicitement un morphisme

\begin{align*} f_x:(\N,+)&\longrightarrow(X,\diamond)\\ n&\longmapsto x^n \end{align*}

La fonc­tion exponentielle étudiée dans le cours d'analyse est également un morphisme de \((\R,+)\) dans \((\R,\times)\), en effet \(\text{exp}(x+y)=\text{exp}(x)\times\text{exp}(y)\).

Quand un mor­phis­me \(f:X\rightarrow Y\) est bijectif et que le mor­phis­me réciproque \(f^{-1}\) est aussi un mor­phis­me on parle d'iso­mor­phis­me. Un isomor­phis­me \(f:X\rightarrow X\) est appelé un au­to­mor­phis­me. Si \(f:X\rightarrow X\) est un mor­phis­me, on parle d'en­do­mor­phis­me. On précise souvent la nature du mor­phis­me, c'est-à-dire la structure qui équipe les ensembles reliés par le mor­phis­me, on parlera donc de mor­phis­me d'ensembles ordonnés, ou de mor­phis­me de semi-groupes ou de mor­phis­mes de grou­pes, etc.
Démontrez que si \(X\) et \(Y\) sont deux ensembles munis de lois de composition internes, alors la bijection réciproque \(f^{-1}\) d'un morphisme bijectif \(f:X\rightarrow Y\) est nécessairement un morphisme.
Soient \(X\), \(Y\) et \(Z\) trois ensembles structurés et \(f:X\rightarrow Y\) et \(g:Y\rightarrow Z\) deux morphismes (resp. isomorphismes). Démontrez que l'application \(g\circ f\) est un morphisme de \(X\rightarrow Z\) (resp. isomorphismes).

Transport d'une structure. Soit \(X\) un ensemble muni d'une structure et \(Y\) un ensemble quel­con­que. Quand on dispose d'une bijection \(f:X\rightarrow Y\), on transporte très facilement la structure de \(X\) à \(Y.\) Par exemple si \(\rel{R}_X\) est une relation binaire définie sur \(X\), il suffit de définir la relation \(\rel{R}_Y\) sur \(Y\) par \[y\;\rel{R}_Y\;y'\Leftrightarrow f^{-1}(y)\;\rel{R}_X\;f^{-1}(y').\] Nous laissons soin au lecteur de transporter une loi de composition interne et une loi de com­po­si­tion externe.

Compatibilité. Inévitablement, si l'on multiplie les structures sur un ensemble, peuvent se poser des problèmes de compatibilité. L'omniprésence des relations d'équivalence et des lois de composition sur les ensembles qui servent d'outillage de base, justifie que l'on se questionne sur l'articulation d'une relation d'équivalence avec la loi de composition interne \(\diamond\) d'un magma \((X,\diamond)\).

Si l'on dispose d'une relation d'équivalence \(\rel{R}\) et d'une loi de composition interne \(\diamond\) sur un ensemble \(X,\) on souhaite pouvoir équiper l'ensemble quotient \(X/\rel{R}\) de la même loi de composition. Ainsi, si \(A\) et \(B\) désignent deux classes d'équivalence pour \(\rel{R}\), on veut que la composition \(A\overline{\diamond} B\) pour cette loi interne sur \(X/\rel{R}\) soit la classe d'équi­va­len­ce de \(a\diamond b\) si \(a\) et \(b\) désignent des représentants quelconques de \(A\) et de \(B\) respectivement. C'est le sens des définitions à venir et c'est cet objectif qu'il faut garder à l'esprit pour ne pas se perdre dans les méandres de ces toutes ces cons­truc­tions algébriques.

Soit \((X,\diamond)\) un magma muni d'une relation d'équivalence \(\rel{R}\). On dit que \(\rel{R}\) est com­pa­tib­le à gauche (resp. com­pa­tib­le à droite) avec la loi \(\diamond\) si et seulement si \begin{align} \forall(x,x',y)\in X^3\quad (x{\rel{R}}x')&\Rightarrow ({\color{#88F}x}\diamond y){\rel{R}}({\color{#88F}x'}\diamond y).\\ \text{resp.}\ \ \forall(x,x',y)\in X^3\quad (x{\rel{R}}x')&\Rightarrow (y\diamond {\color{#88F}x}){\rel{R}}(y\diamond {\color{#88F}x'}).\\ \end{align} On dit que \(\rel{R}\) est com­pa­tib­le avec la loi \(\diamond\) si et seulement si elle est compatible à gauche et à droite, ce qui équivaut à \begin{equation} \forall(x,x',y,y')\in X^4\quad (x{\rel{R}}x')\wedge(y{\rel{R}}y')\ \Rightarrow (x\diamond y){\rel{R}}(x'\diamond y'). \end{equation}

Notons que si la loi est commutative, la compatibilité à gauche est équivalente à la compatibilité à droite.

Soit \((X,\diamond)\) un magma muni d'une relation d'équivalence \(\rel{R}\) com­pa­tib­le avec \(\diamond\). Soit \(\varphi: X\rightarrow X/\rel{R}\) la surjection canonique. Alors il existe une unique loi de com­po­si­tion interne sur l'ensemble quotient \(X/\rel{R}\) telle que \(\varphi\) soit un morphisme. Elle est ap­pe­lée loi quotient de \(\diamond\) par \(\rel{R}\).
Démontrez ce théorème.

Par abus de langage, la loi quotient est souvent notée comme la loi de l'ensemble.

Construction de \({\mathbb Z}\)

La construction de l'ensemble des entiers relatifs est un cas particulier de symétrisation. C'est un procédé général qui a pour objectif de rajouter les éléments qui manquent à un ensemble muni d'une loi de composition afin que les équations du type \((\ref{eq:eqmagma})\) admettent une solution.

Considérons le magma \((\N,+)\) qui est unifère, associatif et commutatif et soient \(a\) et \(b\) deux entiers naturels. L'équation

\begin{equation} \label{eq:symetrisation} x+a=b \end{equation}

n'admet de solution dans \(\N\) que si \(b\geq a\). Le cas échéant, on a bien sûr envie d'écrire que cette solution est égale à \(b-a\), mais nous n'avons pas encore de loi soustractive dans notre attirail, c'est précisément l'objet de notre construction. La solution \(x\), quand elle existe dépend donc des deux nombres \(a\) et \(b\), soit du couple \((a,b)\). Supposons que \(x\) soit une solution de cette équation et soit \(d\in\N\). Dans ce cas, \(x\) est également so­lu­tion de toutes les équations

\begin{equation} x+a+d=b+d. \end{equation}

Ainsi, il existe une relation naturelle entre tous les couples \((a,b)\) pour lesquels l'équation \((\ref{eq:symetrisation})\) admet la même solution. On est tenté de définir cette relation par \((n,m){\rel{R}}(n',m')\Leftrightarrow n-n'=m-m'\), mais il faut l'écrire sans soustractions :

\begin{equation} \label{eq:relbin} (n,m){\rel{R}}(n',m')\Leftrightarrow n+m'=m+n', \end{equation}
Démontrez que la relation binaire définie sur l'ensemble \(\N\times\N\) par l'égalité \((\ref{eq:relbin})\) est une relation d'équivalence.

On définit alors l'addition sur \(\N\times\N\) qui est une loi de composition interne :

\begin{equation} \label{eq:addZ} (n,m)+(n',m') := (n+m,n'+m'). \end{equation}
Démontrez que la relation binaire \((\ref{eq:relbin})\) est compatible avec la loi ad­di­ti­ve définie en \((\ref{eq:addZ})\) sur \(\N\times\N.\)

On définit \(\Z:=(\N\times\N)/\rel{R}\). D'après le théorème sur la loi quotient, l'ensemble \(\Z\) est muni d'une loi quotient. On montre facilement que \((0,0)\) est l'élément neutre pour l'addition définie en \((\ref{eq:addZ})\) et que cette addition est associative et commutative. D'autre part, tout couple \((n,m)\) admet un symétrique, il s'agit du couple \((m,n)\), en effet

\begin{align*} (n,m)+(m,n)&=(n+m,m+n)\\ &=(n+m,n+m)\\ \text{et}\ \ (n+m,n+m)\;&R\;(0,0). \end{align*}

On vérifie aisément que les couples \((n,0)\) avec \(n \geq 0\) et les couples \((0,m)\) avec \(m > 0\) représentent des classes deux-à-deux distinctes et que toutes les classes sont représentées. D'autre part les classes \((0,n)\) sont les opposées des classes \((n,0)\). On montre que le sous-ensemble de \(((\N\times\N)/\rel{R},+)\) cons­ti­tué des couples \((n,0)\) est isomorphe à \((\N,+)\), cela justifie de noter \(n\) le couple \((n,0)\). Sy­mé­tri­que­ment, on note \((-n)\) le couple \((0,n)\).

Si l'on représente le produit cartésien \(\N\times\N\) dans un repère, les représentants de type \((n,0)\) dé­cri­vent l'axe des abscisses et les représentants du type \((0,m)\) dé­cri­vent l'axe des ordonnées. La figure ci-dessous permet de visualiser les classes d'équi­va­len­ce de ces couples d'entiers qui re­pré­sen­tent les entiers relatifs de l'intervalle \([-10,10]\).

Construction de \(\Z\) comme classes d'équivalences de l'ensemble \(\N\times\N\) pour la relation \(\rel{R}\).

Saisissez la valeur de l'entier relatif \(n=\;\) pour voir les éléments de sa classe d'équivalence.

Pour achever la construction de \(\Z\), nous ne donnerons que les grandes lignes. La multiplication est définie comme suit : \[ (n,n')\times (m,m')=(nm+n'm',nm'+mn'). \] Elle a pour élément neutre \(1=(1,0)\), elle est associative et commutative et compatible avec la relation d'équivalence \(\rel{R}\). On vérifie que \((n,0)\times(m,0)=(nm,0)\), que \((n,0)\times(0,m)=(0,nm)\) et que \((0,n)\times(0,m)=(nm,0)\), ce qui permet de retrouver les écritures condensées usuelles puisque l'on a noté \(n\) le couple \((n,0)\) et \(-n\) le couple \((0,n)\). Pour la relation d'ordre, on peut montrer qu'il existe une seule relation d'ordre total sur \(\Z\), c'est la relation définie par \[x\leq y\Leftrightarrow y-x\in\N,\] qui prolonge la relation d'ordre sur les entiers naturels. On démontre que toute partie non-vide et minorée de \(\Z\) admet un plus petit élément.

Notons pour conclure cette section que le procédé de construction du corps des fractions de \(\Z\), à savoir \(\Q\) est tout à fait similaire en partant cette fois de l'équation

\begin{equation} q\times x=p. \end{equation}
En nous inspirant de la construction de \(\Z\), trouvez la relation d'équivalence \(\rel{R}\) entre couples de \(\Z\times\Z\) et la loi de composition sur \(\Z\times\Z\) pour construire l'ensemble \(\Q\) comme le quotient \((\Z\times\Z)/\rel{R}\).

Groupes

Généralités

Nous allons aborder une dernière structure dans ce chapitre. Nous aurons besoin de la structure de groupe pour étudier le problème du taquin. D'autres structures seront abordées dans le chapitre Arithmétique. Les groupes sont des structures extrêmement utiles, ils font l'objet d'une attention toute particulière au point qu'une théorie à part entière leur est consacrée. Cette théorie est très utile pour résoudre de nombreux problèmes de combinatoire, de géométrie, etc. Les chimistes en font grand usage dans l'étude des structures moléculaires et leurs symétries.

Un magma \((X,\diamond)\) unifère, associatif et où tout élément est symétrisable est appelé un groupe. Si l'ensemble \(X\) est fini, \((X,\diamond)\) est appelé groupe fini et le cardinal \(|X|\) est ap­pe­lé l'ordre du groupe.

L'ensemble des entiers relatifs \(\Z\) muni de l'addition est un groupe, de surcroît commutatif (on dit aussi groupe abélien*(*) Niels Henrik Abel fut un mathématicien nor­végien qui a dé­mon­tré, entre autres, que l'on ne pouvait pas ré­sou­dre une équation de degré \(\geq 5\) par radicaux.). Nous reviendrons en détail sur ce groupe en arithmétique. Le sous-ensemble \(\{-1,1\}\) de \(\Z\) muni de la multiplication est un groupe commutatif.

Par analogie avec l'addition dans \(\Z\), quand la loi de groupe est notée ad­di­ti­ve­ment, on note souvent \(0\) l'élément neutre au lieu de \(e\) et on parle d'opposé d'un élément \(x\) plutôt que de symétrique que l'on note généralement \((-x)\). De même quand la loi de groupe est notée multiplicativement, on note souvent \(1\) l'élément neutre au lieu de \(e\) et on parle d'inverse d'un élément \(x\) plutôt que de symétrique que l'on note généralement \(x^{-1}\). Par abus de langage, nous parlerons souvent du groupe \(G\) pour signifier \((G,\diamond)\), confondant ainsi groupe et ensemble sous-jacent.

Soient \((G,\diamond)\) et \((G',\star)\) deux groupes notés multiplicativement et \(f:G\rightarrow G'\) un morphisme de grou­pes. On vérifie que l'image de l'élément neutre \(e\) de \((X,\diamond)\) est l'élément neutre \(e'\) de \((X',\star)\), i.e.

\begin{equation} \label{eq:imneutre} f(e)=e'. \end{equation}

On vérifie que l'image du symétrique \(x^{-1}\) de \(x\) est le symétrique de l'image de \(x\), i.e.

\begin{equation} \label{eq:iminverse} f(x^{-1})={f(x)}^{-1}. \end{equation}

D'autre part, pour tout entier relatif \(n\in\Z\), on a

\begin{equation} f(x^n)=(f(x))^{n}. \end{equation}

L'ensemble des entiers relatifs \(\Z\) est un groupe commutatif pour l'addition, ce n'est pas un groupe pour la multiplication. En revanche l'ensemble des réels \(\R\) est un groupe commutatif pour l'addition et \(\R\setminus\{0\}\) est un groupe pour la multiplication.

On considère une famille \((G_i,\diamond_i)_{i\in I}\) de groupes et on note \(G\) le produit de la famille \((G_i)_{i\in I}.\) On définit la loi produit \(\diamond\) sur \(G\) par \begin{equation} x\diamond y = (x_i\diamond_i y_i)_{i\in I}. \end{equation} Montrez que chaque projection \(p_i:G\rightarrow G_i\) est un morphisme surjectif de groupes. Montrez que le groupe produit \((G,\diamond)\) est commutatif si et seulement si chacun des groupes \((G_i,\diamond_i)\) est commutatif.

Application : définissez l'addition sur des \(n\)-uplets de \(R^n\).

Sous-groupes

On appelle sous-groupe d'un groupe \((G,\diamond)\), tout groupe \((H,\diamond)\) où \(H\) est une partie stable de \(G\) munie de la loi induite par celle de \(G\).

L'ensemble \(\{-1,1\}\) est un sous-groupe de \((\Z,\times)\). L'ensemble \(T:=\{3k\mid k\in\Z\}\) des multiples de \(3\) est un sous-groupe de \((\Z,+)\).

Si \(H\) est un sous-groupe de \(G\), l'injection canonique \(j:H\rightarrow G\) vérifie \(j(x\diamond y)=j(x)\diamond j(y)\), c'est donc un morphisme de groupes. Et d'après \((\ref{eq:imneutre})\) et \((\ref{eq:iminverse})\), l'élément neutre de \(H\) est celui de \(G\) et le symétrique d'un élément de \(H\) est le même que son symétrique dans \(G\) :

Un groupe et l'un quelconque de ses sous-groupes partagent le même élément neutre. Tout élément d'un sous-groupe a le même symétrique dans ce sous-groupe que dans le groupe.

La preuve du théorème suivant est laissée en exercice.

Soit \((G,\diamond)\) un groupe d'élément neutre \(e\) et \(H\subseteq G\). Les quatre assertions suivantes sont équivalentes :
  1. \(H\) est un sous-groupe de \(G\) ;
  2. \(H\) est stable et \(e\in H\) et \(\forall x\in H\ \ x^{-1}\in H\) ;
  3. \(H\) est stable et \(H\not=\varnothing\) et \(\forall x\in H\ \ x^{-1}\in H\) ;
  4. \(H\not=\varnothing\) et \(\forall (x,y)\in H\times H\ \ x\diamond y^{-1}\in H\).

Si \((G,\diamond)\) est un groupe, \((G,\diamond)\) est évidemment un sous-groupe de \((G,\diamond)\), c'est le plus grand élément pour la relation \(\subseteq.\) Pour cette même relation d'ordre, le plus petit sous-groupe de \(G\) est le sous-groupe \((\{e\},\diamond)\) où \(e\) est l'élément neutre de \(G\) pour la loi \(\diamond\). On vérifie aisément que si \(H\) est un sous-groupe de \(G\) qui est lui même un sous-groupe de \(K\), alors \(H\) est un sous-groupe de \(K\).

Soit \((G,\diamond)\) un groupe. Vérifiez que l'ensemble noté \({\mathfrak S}(G)\) des bijections de l'ensemble \(G\) dans lui-même muni de la loi de composition des applications est un groupe. Montrez que le sous-ensemble des au­to­mor­phis­mes muni de la loi induite \(\circ\), noté \((\text{Aut}(G),\circ)\) est un sous-groupe de \(({\mathfrak S}(G),\circ)\).

L'intersection d'une famille de sous-groupes d'un groupe \(G\) est un sous-groupe de \(G\). Soit \(A\subseteq G\) une partie d'un groupe \(G\), l'intersection de tous les sous-groupes de \(G\) qui contiennent \(A\) n'est jamais vide puisque \(G\) est un sous-groupe de \(G\) et contient \(A\).

Soit \(G\) un groupe et \(A\subseteq G\). On appelle sous-groupe engendré par \(A\), noté \(\text{gr}(A),\) le plus petit (au sens de l'inclusion) sous-groupe de \(G\) qui contient \(A\). C'est l'intersection de tous les sous-groupes de \(G\) qui contiennent \(A\). On dit que \(A\) est une partie génératrice de \(G\).

On admettra le théorème suivant :

Soit \((G,\diamond)\) un groupe noté multiplicativement d'élément neutre \(e\) et \(A\) une partie de \(G\). Si \(x^1\) désigne \(x\) et \(x^{-1}\) le symétrique de \(x\), alors le sous-ensemble \(H\) des produits quelconques d'éléments \(a\) ou \(a^{-1}\) de \(A\), i.e de la forme \begin{equation} a_1^{\epsilon_1}\diamond a_2^{\epsilon_2}\diamond\cdots\diamond a_n^{\epsilon_n}\quad\text{où}\ \ \epsilon_i\in\{-1,1\}. \end{equation} avec par convention \(H=\{e\}\) si \(A=\varnothing\), est le sous-groupe de \(G\) engendré par \(A\).
On appelle groupe monogène tout groupe engendré par un singleton. Un grou­pe monogène et fini est appelé groupe cyclique.

Si l'on se donne un morphisme de groupe \(f:G\rightarrow G'\), l'image directe d'un sous-groupe \(H\) de \(G\) est une partie stable de \(G'\) et c'est un sous-groupe de \(G'\) pour la loi induite. De même, l'image réciproque d'un sous-groupe \(H'\) de \(G'\) est un sous-groupe de \(G\) pour la loi induite.

Soit \(f:G\rightarrow G'\) un morphisme de groupe. L'image \(\text{Im}(f):=f(G)\) est un sous-­groupe de \(G'\) et le sous-groupe \(\text{Ker}(f):=f^{-1}(\{e\})\) de \(G\) est appelé noyau de \(f\).

L'image (resp. le noyau) d'un morphisme fournit un critère simple pour décider s'il s'agit d'un morphisme surjectif (resp. injectif), ce qui s'avère très utile en pratique :

Un morphisme de groupes \(f:G\rightarrow G'\) est une surjection si et seulement si \(\text{Im}(f)=G'\) et une injection si et seulement si \(\text{Ker}(f)=\{e\}\) où \(e\) est l'élément neutre pour la loi de groupe de \(G\).
On désignera par \(\diamond\) et \(\star\) les lois de composition internes respectives des groupes \(G\) et \(G'\) notée mul­ti­pli­ca­ti­ve­ment et \(e\) et \(e'\) leurs éléments neutres respectifs.

Le résultat est évident pour la surjection par définition. Pour l'autre partie, on sait que l'image de \(e\) est \(e'\), que \(f\) soit injective ou non, mais si c'est cas \(e\) est l'unique élément dont l'image est \(e'\), autrement dit \(\text{Ker}(f)=\{e\}\). Réciproquement, supposons que \(\text{Ker}(f)=\{e\}\). On veut prouver que \[\forall (x,y)\in G\times G\ \ f(x)=f(y)\Rightarrow x=y.\] L'élément \(f(y)\) admet un symétrique \(f(y)^{-1}\) (notation multiplicative) dans \(G'\) puisqu'il s'agit d'un groupe, donc si \(f(x)=f(y)\), \begin{align*} f(x)\star f(y)^{-1}&=f(y)\star f(y)^{-1}\\ f(x)\star f(y)^{-1}&=e'\\ f(x\diamond y^{-1})&=e' \end{align*} Autrement dit, \(x\diamond y^{-1}\in\text{Ker}(f)\), soit : \begin{align*} x\diamond y^{-1}&=e\\ (x\diamond y^{-1})\diamond y&=e\diamond y\\ x\diamond (y^{-1})\diamond y)&=y\\ x\diamond e&=y\\ x&=y. \end{align*}
Justifiez chaque égalité de la preuve ci-dessus en identifiant les propriétés des lois de grou­pe qui ont été appliquées.

On rappelle que le centre de \(G\) est la partie \(Z_G\) des éléments de \(G\) qui com­mu­tent avec tous les élé­ments du groupe, i.e.

\[Z_G=\{a\in G\mid\forall x\in G\ \ x\diamond a=a\diamond x\}\]

Soit \(a\in Z_G\), on a donc \(\forall x\in G\ \ x\diamond a = a \diamond x\) et en composant à droite par le symétrique de \(a\) noté \(a^{-1}\), on a nécessairement

\[\forall x\in G\ \ x=a\diamond x\diamond a^{-1}.\]
Démontrez que l'application \(\varphi_a:G\rightarrow G\) définie par \(x\mapsto a\diamond x\diamond a^{-1}\) est un automorphisme du groupe \((G,\diamond).\) On l'appelle automorphisme intérieur de \(G\). Quel est l'automorphisme réciproque de \(\varphi_a\) ? Démontrez que l'application \(\varphi:a\mapsto \varphi_a\) est un morphisme du groupe \((G,\diamond)\) dans le groupe \((\text{Aut}(G),\circ)\). Vérifiez que \(\text{Ker}(\varphi)=Z(G).\) En déduire que le centre d'un groupe \(G\) est un sous-groupe de \(G\) pour la loi induite.
On dit que deux éléments \(x\) et \(x'\) d'un groupe \((G,\diamond)\) sont conjugués si et seu­le­ment s'il existe \(a\in G\) tel que \begin{equation} x'= a\diamond x\diamond a^{-1}. \end{equation}
Vérifiez que la relation de conjugaison sur un groupe \(G\) est une relation d'équivalence.
On appelle sous-groupe normal d'un groupe \((G,\diamond)\) tout sous-groupe de \(G\) qui est invariant par tout automorphisme intérieur de \(G\), i.e. \begin{equation} \forall a\in G\quad a\diamond H=H\diamond a. \end{equation} où \(a\diamond H:=\{a\diamond x\mid x\in H\}\) et où \(H\diamond a:=\{x\diamond a\mid x\in H\}\). On note alors \(H\triangleleft G\).

Le singleton \(\{e\}\) est toujours un sous-groupe normal d'un groupe dont l'élément neutre est \(e\). Si un groupe \(G\) est commutatif, tous ses sous-groupes sont normaux, cette notion a donc surtout un intérêt dans l'étude des groupes non-commutatifs. On montre facilement que l'image ou l'image réciproque d'un sous-groupe normal est un sous-groupe normal et en corollaire, le noyau d'un morphisme de groupe est toujours un sous-groupe normal.

L'étude des sous-groupes normaux est motivée par la caractérisation des relations d'équivalences qui sont compatibles avec une loi de groupe. En effet, il faut se souvenir que l'on ne peut quotienter un ensemble muni d'une loi de compotion interne par une relation d'équivalence que si celle-ci est com­pa­tib­le avec cette loi.

Soit \((G,\diamond)\) un groupe. Une relation d'équivalence \(\rel{R}\) sur \(G\) est compatible à gauche (resp. compatible à droite) avec la loi \(\diamond\) si et seulement si elle est de la forme \begin{equation} x{\rel{R}}y\Leftrightarrow x^{-1}\diamond y\in H\qquad\text{resp.}\ \ x{\rel{R}}y\Leftrightarrow y\diamond x^{-1}\in H, \end{equation} où \(H\) est un sous-groupe de \(G\).
Nous allons faire la preuve pour la compatibilité à gauche, la preuve étant similaire pour la com­pa­ti­bi­li­té à droite. On se donne une relation d'équivalence \(\rel{R}\) sur \(G\) compatible à gauche, autrement dit \[ \forall(x,x',y)\in G^3\ \ x{\rel{R}}x'\Rightarrow ({\color{#88F}x}\diamond y){\rel{R}}({\color{#88F}x'}\diamond y). \] On note \(H\) la classe d'équivalence de l'élément neutre \(e\). Soient \(x\) et \(y\) deux éléments de \(G\) tels que \(x{\rel{R}}y.\) Comme la relation \(\rel{R}\) est compatible à gauche avec la loi \(\diamond\), on a \(x^{-1}\diamond x{\rel{R}}x^{-1}\diamond y\), soit \(e{\rel{R}}x^{-1}\diamond y\) et donc \(x^{-1}\diamond y\in H.\) Inversement, \(x^{-1}\diamond y\in H\) s'écrit \(e{\rel{R}}x^{-1}\diamond y\) et on en déduit que \(x{\rel{R}}y.\) Donc \[ \forall(x,y)\in G\times G\quad x{\rel{R}}y\Leftrightarrow x^{-1}\diamond y\in H. \] Montrons que \(H\) est un sous-groupe de \(G\). Soient \(x\) et \(y\) deux éléments quelconques de \(H\). Comme \(e\in H\), \(x{\rel{R}}e\) et \(e{\rel{R}}y\) et par transitivité de la relation, \(x{\rel{R}}y\) soit \(x^{-1}\diamond y\in H\).
Réciproquement donnons nous un sous-groupe \(H\) de \(G\), la relation \(\rel{R}\) définie par \(x{\rel{R}}y\Leftrightarrow x^{-1}\diamond y\in H\) est réflexive car \(e\in H\). Elle est symétrique car si \(x^{-1}\diamond y\in H\), son symétrique \((x^{-1}\diamond y)^{-1}=y^{-1}x\) et appartient à \(H\). Elle est transitive car si \(x^{-1}\diamond y\in H\) et \(y^{-1}\diamond z\in H\), \begin{align*} (x^{-1}\diamond y)\diamond (y^{-1}\diamond y) &=x^{-1}\diamond (y\diamond y^{-1})\diamond y\quad\text{associativité}\\ &=x^{-1}\diamond e\diamond y\quad\text{associativité}\\ &=x^{-1}y. \end{align*}

On admettra le théorème suivant.

Soit \((G,\diamond)\) un groupe. Une relation d'équivalence sur \(G\) est compatible à gauche (resp. à droite) avec la loi de \(G\) si et seulement si elle est de la forme \(x^{-1}y\in H\) (resp. \(yx^{-1}\in H\)), où \(H\) est un sous-groupe de \(G\).

Soit \(a\) un élément d'un groupe \(G\) et \(H\) un sous-groupe de \(G\). Les ensembles \begin{equation} aH:=\{ah\mid h\in H\}\quad\text{et}\quad Ha:=\{ha\mid h\in H\}, \end{equation} sont appelés classe à gauche et classe à droite suivant \(H\). Ce sont les classes d'équivalence pour les deux relations d'équivalence suivantes respectivement : \begin{align*} \forall(x,y)\in G^2\quad (x\;\rel{R}_g\;y)\ &\Leftrightarrow (x^{-1}y\in H);\\ \forall(x,y)\in G^2\quad (x\;\rel{R}_d\;y)\ &\Leftrightarrow (yx^{-1}\in H). \end{align*}

L'ensemble des inverses des éléments de \(aH\) est l'ensemble \(Ha^{-1}\), il y a donc bijection entre les deux ensembles quotients \(G/\rel{R}_g\) et \(G/\rel{R}_d\). Si ces ensembles sont finis, ils ont donc même cardinal appelé indice de \(H\) dans \(G\) et noté \((G:H)\).

L'ordre d'un sous-groupe \(H\) d'un groupe fini \(G\) divise l'ordre du groupe \(G\) et \(|G|/|H|=(G:H)\).
L'application définie par \(x\mapsto ax\) de \(H\) dans \(aH\) est une bijection, toutes les classes à gauche forment une partition de \(G\) et ont le même cardinal que celui de \(H\). Le principe des bergers permet de conclure.

Soit \(\rel{R}\) une relation d'équivalence compatible avec la loi \(\diamond\), autrement dit compatible à gauche et à droi­te. Soit \(H\) la classe d'équivalence de l'élément neutre \(e\). On sait que \(H\) est un sous-groupe de \(G\) et que \(\forall x\in G\), \(x{\rel{R}}y\) si et seulement si \(y\in x\diamond H\) et \(y\in H\diamond x\), autrement dit

\begin{equation*} \forall x\in G\quad x\diamond H=H\diamond x, \end{equation*}

soit \(H\triangleleft G\). Réciproquement si \(H\triangleleft G\), la relation \(\rel{R}\) définie par \(x{\rel{R}}y\) si et seulement si \(x^{-1}\diamond y\in H\) qui équivaut à \(y\diamond x^{-1}\in H\) est compatible avec la loi \(\diamond\). On admettra les théorèmes suivants&8239;:

Les relations d'équivalence compatibles avec la loi de composition d'un groupe \((G,\diamond)\) sont de la forme \(x{\rel{R}}y\Leftrightarrow x^{-1}\diamond y\in H\) où \(H\) est un sous-groupe normal de \(G\).
Soit \((G,\diamond)\) un groupe et \(H\) un sous-groupe normal de \(G\). Le groupe quotient pour la relation d'équivalence \(x^{-1}\diamond y\in H\) est noté \(G/H\). La surjection canonique \(\varphi:G\rightarrow G/H\) est un morphisme de groupes.

Nous savons déjà que tout sous-groupe d'un groupe commutatif est normal. \((\Z,+)\) est un groupe com­mu­ta­tif, les relations d'équivalences compatibles avec l'addition sur \(\Z\) sont donc du type \[x{\rel{R}}y\Leftrightarrow x-y\in H\] où \(H\) est un sous-groupe de \(\Z\). L'étude de ce groupe particulier est le point de départ de l'ari­thmé­ti­que, ce que nous aborderons au chapitre éponyme Arithmétique.

Les groupes sont souvent notés multiplicativement mais ne sont pas toujours commutatifs, et donc si \((x_i)_{i\in I}\) est une famille d'éléments d'un groupe non-commutatif, on ne peut pas définir son produit en général. Néanmoins si la loi est associative et que l'ensemble d'indexation est l'intervalle \([1,n]\) de \(\N\), on définit les produits dans l'ordre croissant (resp. décroissant) des indices : \begin{align*} \prod_{i=1}^n x_i&:=x_1.x_2\,\ldots\,x_{n-1}.x_n,\\ \prod_{i=n}^1 x_i&:=x_n.x_{n-1}\,\ldots\,x_2.x_1. \end{align*}

Le groupe symétrique

Orbites

L'ensemble des permutations des éléments d'un ensemble joue un rôle très important en in­for­ma­ti­que. Par exemple, tous les algorithmes de tri sont intimement reliés à l'étude de cet ensemble. Nous verrons d'ailleurs que beaucoup de résultats mathématiques de cette section ne sont rien d'autres que des algorithmes déjà connus du lecteur sans même jamais avoir pratiqué les mathématiques.

L'ensemble \(X^X\) des bijections d'un ensemble \(X\) dans lui-même, appelées permutations, muni de la loi de composition des applications est un groupe appelé groupe symétrique de \(X\). On le note \(\def\Sn{{\mathfrak S}}\Sn(X)\). Si \(X=[1,n]\), le groupe est appelé groupe symétrique de degré n et il est noté \(\Sn_{n}\).
Nous avons vu en exercice que la composée de deux bijections est une bijection, le sous-ensemble \(\Sn(X)\) de \(X^X\) constitué des bijections est donc une partie stable pour la loi de composition \(\circ\) faisant de \((\Sn(X),\circ)\) un magma. L'associativité de la loi de composition a elle aussi été étudiée en exercice. L'application identique est évidemment une bijection et c'est l'élément neutre pour la composition des bijections. Chaque bijection \(f\) admet un symétrique pour la loi de composition, il s'agit bien sûr de la bijection réciproque \(f^{-1}\).

Nous savons d'après ce corollaire que l'ordre du groupe \({\mathfrak S}_n\) est égal à \(n!\) L'étude des per­mu­ta­tions sur un ensemble \(X\) équipotent à un ensemble \(Y\) revient à étudier les permutations de \(Y\). En effet si \(f:X\rightarrow Y\) est une bijection alors l'application \(\varphi:{\mathfrak S}(X)\rightarrow{\mathfrak S}(Y)\) définie par \(\sigma\mapsto f\circ \sigma\circ f^{-1}\) est un isomorphisme de groupes. Ceci montre que l'étude du groupe symétrique \({\mathfrak S}_n\) ne se limite pas à l'étude des permutations des éléments de l'ensemble \([1,n]\) mais concerne tous les ensembles de car­di­nal \(n\).

Arthur Cayley était un ma­thématicien anglaisTout groupe \(G\) est isomorphe à un sous-groupe de \({\mathfrak S}(G)\).
Si \((G,\diamond)\) est un groupe, on associe à tout \(a\in G\) l'application \(\sigma_a:x\mapsto a\diamond x\). L'équation \(a\diamond x=b\) admettant une unique solution l'application \(\sigma_a\) est bijective, donc \(\sigma_a\in{\mathfrak S}(G)\). La loi étant associative on sait que \(\sigma_{a\diamond b}=\sigma_{a}\circ \sigma_b\) ce qui fait de l'application \(\sigma:G\rightarrow{\mathfrak S}(G)\) définie par \(a\mapsto\sigma_a\) un morphisme de groupes, surjectif sur \(\text{Im}(\sigma)\). Reste à montrer qu'il est injectif. Son noyau \(\text{Ker}(\sigma):=f^{-1}(\text{Id}_G)\), autrement dit \begin{align*} \text{Ker}(\sigma)&=\{a\in G\mid \forall x\in G\ \ \sigma_a(x)=x\},\\ &=\{a\in G\mid \forall x\in G\ \ a\diamond x=x\}. \end{align*} Or \(\forall x\in G\ \ a\diamond x=x\) si et seulement si \(a=e\).

Nous allons dans la suite nous concentrer sur le groupe symétrique d'un ensemble fini et par­ti­cu­liè­re­ment sur le groupe \(\Sn_{n}\) de degré \(n\). On représente gé­né­ra­le­ment le graphe d'une per­mu­ta­tion \(\sigma\in{\mathfrak S}_n\) sous la forme d'une matrice de 2 lignes de \(n\) entiers tel que la première ligne contient tous les entiers de \(1\) à \(n\) dans l'ordre croissant et la seconde leurs images en vis-à-vis :

\begin{equation} \sigma=\begin{pmatrix} 1&2&3&\cdots&n\\ \sigma(1)&\sigma(2)&\sigma(3)&\cdots&\sigma(n) \end{pmatrix} \end{equation}
Décrivez toutes les permutations des groupes \(\Sn{1}\) et \(\Sn{2}\). Montrez que ces groupes sont com­mu­ta­tifs.
Pour tout entier \(n\geq 3\), le groupe \(\Sn_{n}\) n'est pas commutatif.

C'est un résultat important et facile à démontrer. Le fait que ce groupe ne soit pas commutatif en général lui donne un intérêt tout particulier et le théorème de Cayley montre que l'étude du groupe symétrique et de ses sous-groupes permet indirectement d'étudier les groupes de manière générale.

Démontrez ce théorème. Indication : Construisez deux permutations de \(\Sn_{n}\) où \(n\geq 3\) qui laissent tous les entiers \(k > 3\) fixes et qui ne commutent pas.
Démontrez que le centre \(Z(\Sn_{n})\) du groupe \(\Sn_n\) est réduit au singleton \(\{\text{Id}_n\}\). Indication : si \(\sigma\in Z(\Sn_n)\), \(\sigma\) commute avec toutes les permutations de \(\Sn_n\), en particulier avec une transposition \(\tau_{a,b}\).

La loi de composition des applications se comporte de manière similaire à un produit, ainsi pour al­lé­ger les écritures, le symbole de composition des applications \(\circ\) sera écrit comme un produit et très souvent omis dans les ex­pres­sions. On parlera donc du produit \(\sigma\tau\) au lieu de la composition\(\sigma\circ\tau\) de \(\sigma\) et \(\tau\). La notation \(\sigma^k\) désigne la \(k\)-ème itérée de \(\sigma\), i.e. la composition de \(k\) termes \(\sigma\) si \(k > 0\) ou de \(k\) termes \(\sigma^{-1}\) si \(k < 0\), et l'ap­pli­ca­tion identique \(\text{Id}_X\) si \(k=0\).

Soit \(\sigma\in\Sn(X)\) une permutation sur un ensemble fini \(X\). La relation binaire dé­fi­nie sur \(X\) par \(x\;\rel{R}_\sigma\;y\) si et seulement si \begin{equation} \exists k\in\Z\quad y=\sigma^k(x). \end{equation} est une relation d'équivalence. La classe d'équivalence d'un élément \(x\in X\) est appelée orbite de \(x\) suivant \(\sigma\), on la note \(\def\orb{{\mathscr O}}\orb_\sigma(x)\).
Quelles sont les orbites de la permutation identité ?
Soit \(\sigma\in\Sn(X)\) et \(\orb\) une orbite suivant \(\sigma\). Démontrez que l'application induite par \(\sigma\) sur \(\orb\) est une bijection.

La proposition suivante va nous permettre d'élaborer un algorithme pour déterminer comme calculer effectivement l'orbite d'un élément.

Soit \(\sigma\in\Sn(X)\) et \(\orb\) une orbite de cardinal \(p > 1\) suivant \(\sigma\). Alors \begin{equation} \label{eq:calculorb} \forall x\in\orb\quad \orb=\{x,\sigma(x),\sigma^2(x),\ldots,\sigma^{p-1}(x)\}\quad\text{et}\ \ \sigma^p(x)=x. \end{equation}
Par définition, l'orbite d'un élément \(x\in\orb\) est l'ensemble \(\{\sigma^k(x)\mid k\in\Z\}\). Cet ensemble étant fini, il existe nécessairement un entier \(p\in\Z\) qui est le plus petit entier \(m\) tel que \(x=\sigma^m(x)\). Soit \(k\) un entier quelconque. Si \(q\) et \(r\) désignent respectivement le quotient et le reste de la division euclidienne de \(k\) par \(p\), i.e. \(k=qp+r\) avec \(0\leq r < p\), on a \begin{align*} \sigma^k(x) &=\sigma^{r+qp}(x)\\ &=\sigma^{r+(q-1)p}(\sigma^p(x))\\ &=\sigma^{r+(q-1)p}(x)\\ &=\sigma^{r+(q-2)p}(\sigma(x))\\ &=\vdots\\ &=\sigma^r(x) \end{align*} Tous les restes possibles étant compris entre \(0\) et \(p-1\), on a donc \[\orb=\{\sigma^r(x)\mid 0\leq r < p\}.\] Reste à montrer que \(|\orb|=p\), autrement dit que les \(\sigma^r(x)\) pour \(r\in[0,p[\) sont deux-à-deux distincts. Soient \(r\) et \(r'\) tels que \( 0\leq r\leq r' < p \) et \(s^r(x)=s^{r'}(x)\). On en déduit que \(\sigma^{r'-r}(x)=x\) et comme \(0\leq r'-r < p\) ceci impose que \(r'=r\).

Cette proposition montre que pour construire l'orbite d'un élément \(x\), il suffit d'itérer ses images par \(\sigma\) tant que la nouvelle image obtenue est différente de \(x\). Considérons la permutation \(\sigma\in\Sn_{9}\) sui­van­te :

\begin{align} \label{def:perm1} \sigma=\begin{pmatrix} \color{yellow}1&\color{#F44}2&\color{yellow}3&\color{yellow}4&\color{#AAF}5&\color{#AAF}6&\color{#8DF}7&\color{yellow}8&\color{#AAF}9\\ \color{yellow}3&\color{#F44}2&\color{yellow}8&\color{yellow}1&\color{#AAF}6&\color{#AAF}9&\color{#8DF}7&\color{yellow}4&\color{#AAF}5 \end{pmatrix}. \end{align}

Calculons l'orbite de \(1\). On a \(\sigma(1)=3\), puis \(\sigma(3)=8\) puis \(\sigma(8)=4\) et finalement \(\sigma(4)=1.\) On ob­tient de cette façon quatre orbites pour cette permutation :

\begin{align*} \orb_\sigma({\color{yellow}1})&=\{{\color{yellow}1,3,8,4}\},\\ \orb_\sigma({\color{#F44}2})&=\{{\color{#F44}2}\},\\ \orb_\sigma({\color{#AAF}5})&=\{{\color{#AAF}5,6,9}\},\\ \orb_\sigma({\color{#8DF}7})&=\{{\color{#8DF}7}\}.\\ \end{align*}
Écrivez un programme en Python qui calcule les différentes orbites d'une permutation en la re­pré­sen­tant par un tuple saisi par l'utilisateur. Pour cela, vous écrirez une fonction orbite(k) qui renvoie le tuple correspondant à l'orbite de \(k\).
On appelle support d'une permutation \(\sigma\in\Sn(X)\), le sous-ensemble de \(X\) noté \(\text{supp}(\sigma)\) des éléments de \(X\) qui ne sont pas fixés par \(\sigma\), i.e. \begin{equation} \text{supp}(\sigma):=\{x\in X\mid\sigma(x)\not=x\}. \end{equation}

Le support de la permutation \((\ref{def:perm1})\) est \(\text{supp}(\sigma)=\{{\color{#FF0}1},{\color{#FF0}3},{\color{#FF0}8},{\color{#FF0}4},{\color{#AAF}5},{\color{#AAF}6},{\color{#AAF}9}\}\). Le support de la permutation iden­tique est l'ensemble vide.

Soient \(n\)et \(k\) deux entiers naturels tels que \(1 \leq k \leq n\). Montrer que l'application \(\sigma\) définie par \(\sigma(k) = 1 + (n + k -1)\% n\) où \(a \% b\) désigne le reste de la division euclidienne de \(a\) par \(b\), est une per­mu­ta­tion de \(\Sn_{n}\). Calculez son support.

Cycles

On appelle cycle toute permutation \(\sigma\in\Sn(X)\) telle qu'une seule orbite \(\orb\) suivant \(\sigma\) n'est pas réduite à un élément. Dans ce cas, \(\text{supp}(\sigma)=\orb\) et le cardinal de \(\orb\) est appelé la longueur du cycle. Un cycle de longueur \(p\) est appelé un p-cycle et un 2-cycle est appelé trans­po­si­tion.

La permutation \((\ref{def:perm1})\) contient donc un \(3\)-cycle et un \(4\)-cycle mais pas de transposition.

Démontrez que toute transposition \(\tau\) est une involution, c'est-à-dire vérifie \(\tau^2=\text{Id}.\)

À ce stade, nous savons que la restriction d'une permutation \(\sigma\) à une orbite \(\orb{}\) est une bijection (cf. exercice), c'est donc une permutation définie sur l'ensemble \(\orb{}\). En notant \(x_1\) un représentant de \(\orb{}\) et en définissant par récurrence \(x_{k+1}:=\sigma(x_k)\), l'assertion \((\ref{eq:calculorb})\) montre que cette restriction est de la forme

\begin{equation} \label{eq:circulante} \sigma=\begin{pmatrix} x_1&x_2&\cdots&x_{p-1}&x_p\\ x_2&x_3&\cdots&x_{p}&x_1 \end{pmatrix} \end{equation}

Ceci explique pourquoi on a qualifié de cycle une telle permutation (on déplace tous les étudiants d'une rangée d'une place sur leur gauche et le dernier étudiant se place en première position sur la rangée). On en déduit qu'un \(p\)-cycle opère un décalage circulaire sur les éléments de son orbite et laisse fixes les \(n-p\) éléments restants. Ceci justifie que l'on note un \(p\)-cycle \(\sigma\) par le \((p-1)\)-uplet \[(x_1,x_2,\ldots,x_{p-1})\] qui le caractérise puisque \(\sigma(x_i)=x_{i+1}\) pour \(i\in[1,p-1]\) et \(\sigma(x_p)=x_1\). Une transposition \((x_i,x_j)\) est par­fois notée \(\tau_{x_i,x_j}\).

Soit \((\sigma_i)_{i\in I}\) une famille de cycles d'un ensemble fini \(X\) de supports \(Y_i\) deux-à-deux disjoints et de réunion \(Y\). Alors
  1. Les \(\sigma_i\) commutent deux-à-deux ce qui permet de définir leur produit \[\sigma:=\prod_{i\in I}\sigma_i.\]
  2. La permutation \(\sigma\) coïncide avec \(\sigma_i\) sur \(X_i\) et avec l'application identique \(\text{Id}_X\) sur \(X\setminus Y\).
  3. Les \(X_i\) sont les orbites suivant \(\sigma\) qui ne sont pas réduites à un élément.

On déduit de l'étude menée le théorème suivant :

Toute permutation \(\sigma\) non identique d'un ensemble fini \(X\) se décompose de manière unique, à l'ordre près, en produit de cycles à supports deux-à-deux disjoints.

Les différents résultats obtenus montrent que l'algorithme que nous avons appliqué pour calculer les différentes orbites détermine également les différents cycles puisque nous avons calculé chaque orbite en itérant la permutation \(\sigma\).

Vous pouvez voir la décomposition en produit de cycles d'une permutation \(\sigma\) obtenue avec cet al­go­ri­thme en sai­sis­sant les images \(\sigma(i),\ i\in[1,n]\) d'une permutation \(\sigma\) de votre choix dans l'ordre crois­sant des valeurs \(i\) en les séparant par un espace puis en validant :

\(\sigma(X)=\,\big(\)\(\big)\).

Soit sous forme matricielle :

\(\sigma=\Big(\)\(\Big)\)
On obtient la décomposition en produit de cycles suivante :
\(\sigma=\,\)
et il y a or­bi­tes cons­ti­tuée(s) de point(s) fixe(s) : . La sig­na­tu­re (concept défini plus bas) de cet­te per­mu­ta­tion est \(\epsilon(\sigma)=(-1)\).

Le théorème suivant est un résultat bien connu du lecteur, il est simplement mas­qué par le vo­ca­bu­lai­re des permutations. Il dit en substance que l'on peut réorganiser les livres de sa bibliothèque comme on le souhaite en ne permutant jamais plus de deux livres à la fois, ce qui est bien pra­ti­que quand on n'a que deux mains.

Toute permutation \(\sigma\) d'un ensemble fini \(X\) de cardinal \(n\geq 2\) se décompose en produit de transpositions.
D'après le théorème précédent, il suffit de le prouver pour l'identité et pour un quelconque \(p\)-cycle. Si \(\sigma=\text{Id}_X\) toute transposition \(\tau\) vérifie \(\tau\tau=\text{Id}_X\). Si \(\sigma\) est un cycle, nous savons que sa restriction sur son support est une permutation de la forme \((\ref{eq:circulante})\), autrement dit \[\sigma=\prod_{i=1}^{p-1}(x_i,x_{i+1}).\]

Notons que la décomposition en produit de transpositions n'est pas unique. En revanche la parité du nombre de transpositions est constant (en exercice). En reprenant la permutation que vous avez saisie plus haut et en s'appuyant sur la preuve du théorème ci-dessus qui fournit une construction pour un cycle quelconque, on obtient cette décomposition en produit de transpositions :

\(\sigma=\,\)
Démontrez que si \(\sigma\) est un \(p\)-cycle, alors \(\sigma^p=\text{Id}\). Quelle est l'inverse d'un \(p\)-cycle ?
Écrivez une fonction Cycles(s) qui décompose une permutation s en produit de cycles à supports disjoints en adaptant le programme précédent qui calculait les différentes orbites d'une permutation. Cette décomposition sera représentée par un tuple de tuples. Écrivez une fonction Transpositions(s) qui décompose une permutation s en produit de trans­po­si­tions.

Le théorème précédent affirmait que l'on pouvait réorganiser sa bibliothèque en ne permutant que deux livres à la fois, le théorème suivant affirme que l'on peut même se restreindre à des permutations de deux livres dont les titres se succèdent dans l'ordre alphabétique (ce qui fixe un numéro d'ordre à chaque livre).

Le groupe des permutations \(\Sn_n\) est engendré par la famille de trans­po­si­tions \(\{(i,i+1)\}_{i\in[1,n-1]}.\)
D'après le théorème 11, il faut montrer que toute permutation est un produit de transpositions du type \((i,i+1)\). Nous savons déjà qu'une permutation se décompose en produit de transpositions d'après le théorème 27, il suffit donc de montrer que toute transposition \(\tau\) s'écrit comme un produit de trans­po­si­tions du type \((i,i+1)\). Soient \(i\) et \(j\) dans \([1,n]\) avec \(i < j\) et \(\tau=(i,j).\) Si \(i+1=j\), la per­mu­ta­tion \((i,j)\) est la transposition \((i,i+1)\) et le résultat est vrai. Si \(i+1 < j\), montrons que \begin{equation*} (i,j)={\color{#88F}(j-1,j)}{\color{#FFF}(i,j-1)}{\color{#88F}(j-1,j)} \end{equation*} Calculons l'image de \(i\) et de \(j\) par la permutation produit notée \(\pi\) à droite de l'égalité ci-dessus : \begin{align*} \pi(i)&={\color{#88F}(j-1,j)}{\color{#FFF}(i,j-1)}{\color{#88F}(j-1,j)}(i)\\ &={\color{#88F}(j-1,j)}{\color{#FFF}(i,j-1)}(i)\\ &={\color{#88F}(j-1,j)}(j-1)\\ &=j \end{align*} On obtient de façon similaire \(\pi(j)=i\). Il suffit de recommencer la même décomposition pour \((i,j-1)\) et de proche en proche pour conclure.

Permutations et tris

On se donne une liste*(*) Ce n'est rien d'autre qu'une séquence. de \(n\) valeurs dans un ensemble totalement ordonné \((X,\preceq)\). On cherche à trier les \(n\) valeurs de la liste \(L\) dans l'ordre croissant.

Si l'on développe un algorithme basé sur des comparaisons entre éléments de \(X\), on peut toujours supposer que \(X=[1,n]\) et qu'il est muni de l'ordre naturel \(\leq\). En effet, supposons que les éléments de la liste \(L\) soient tous distincts, on peut les numéroter \(x_1,x_2,\ldots,x_n\) (indépendamment de leur position dans la liste) de sorte que \[ \forall (i,j)\in[1,n]\times[1,n]\quad i < j \Leftrightarrow x_i \prec x_j. \] ce qui définit un isomorphisme d'ensembles ordonnés entre \(([1,n],\leq)\) et \((L[1,n],\preceq)\) où \(L[1,n]\) est l'ensemble des valeurs de la liste \(L\) (l'image de l'application \(L\)). Comparer deux éléments de la liste \(L\) ou deux entiers naturels est donc équivalent.

On suppose dorénavant que la liste \(L\) de longueur \(n\) contient exactement les \(n\) entiers de \(1\) à \(n\), autrement dit \(L\) définit implicitement une permutation du groupe symétrique \(\Sn_n\) :

\begin{equation} \sigma=\begin{pmatrix} 1&2&3&\ldots&n-1&n\\ L[1]&L[2]&L[3]&\ldots&L[n-1]&L[n] \end{pmatrix}. \end{equation}

où \(L[i]\) désigne la \(i\)-ème valeur dans la liste. Nous pourrions bien entendu conserver la notation \(L\) pour cette permutation. Pour trier \(L\) on dispose d'une opération \(i\rightleftharpoons j\) qui échange le contenu des cellules d'indices \(i\) et \(j\) de la liste. Cette opération est réalisée par l'algorithme suivant :

Echanger(L,i,j)
   aux ← L[i]
   L[i] ← L[j]
   L[j] ← aux

Notons que l'on sait déjà que la liste triée sera la liste \([1,2,\ldots,n]\), ce n'est pas tant le résultat du tri qui nous motive ici mais la manière de le réaliser. L'opération d'échange \(i\rightleftharpoons j\) définit implicitement la transposition \((\sigma(i),\sigma(j))\). N'importe quel algorithme de tri comparatif consiste en une succession d'échanges \(i\rightleftharpoons j\) de valeurs dans la liste \(L\), notons les \((\tau_k)_{k\in[1,t]}\). Si l'algorithme est correct, la liste finale est triée, il s'agit donc de la permutation identique. On vient de mon­trer que \begin{align*} \tau_t\tau_{t-1}\ldots\tau_2\tau_1\sigma &= \text{Id},\\ \sigma &= \text{Id}.(\tau_t\tau_{t-1}\ldots\tau_2\tau_1)^{-1},\\ \sigma &= \tau_1\tau_2\ldots\tau_{t-1}\tau_t \quad\text{car}\ \tau_i=\tau_i^{-1}. \end{align*} Et nous venons donc de décomposer la permutation \(\sigma\) en produit de transpositions. Chaque algo­ri­thme de tri comparatif est donc une preuve constructive que toute permutation se décompose en produit de transpositions. Et on comprend mieux à présent que cette décomposition n'a rien d'uni­que vu la diversité des algorithmes de tris comparatifs.

L'algorithme du tri par propagation appelé également tri à bulles réalise le tri d'une liste uniquement avec des échanges du type \(i\rightleftharpoons i+1\). Le principe est simple, on part de \(i\leftarrow 1\) et on fait l'échange \(i\rightleftharpoons j\) si \(L[i] \succ L[i+1]\) et on recommence en incrémentant \(i\) jusqu'à la valeur \(n-1\). On montre aisément qu'à l'issu de ces \(n-1\) comparaisons, la valeur maximale de la liste est en position \(n\). Il suffit de recommencer sur la sous-liste \(L[1:n-1]\) puis la sous-liste \(L[1:n-2]\) et ainsi de suite jusqu'à la sous-liste \(L[1:2]\), la sous-liste \(L[1:1]\) étant triée.

La grande variété des preuves/algorithmes de tris est due à la recherche d'une décomposition en pro­duit de transpositions qui minimise le nombre de comparaisons entre éléments de la liste.

Signature

Dans la suite \(X\) désigne un ensemble fini de cardinal \(n\).

On appelle signature d'une permutation \(\sigma\in\Sn(X)\) l'entier \(\epsilon(\sigma):=(-1)^{n-m}\) où \(m\) est le nombre d'orbites suivant \(\sigma\). Si \(\epsilon(\sigma)=+1\) (resp. \(\epsilon(\sigma)=-1\)), on dit que \(\sigma\) est une per­mu­ta­tion paire (resp. per­mu­ta­tion im­pai­re).

La permutation identité génère \(n\) orbites (tous les points sont fixes), donc \(\epsilon(\text{Id}_X)=n-n=0\). Une transposition \(\tau\) laisse \(n-2\) points fixes et crée une orbite de cardinal \(2\), il y a donc au total \(n-1\) or­bi­tes, d'où \(\epsilon(\tau)=(-1)^{n-(n-1)}=-1\). Un \(p\)-cycle \(\sigma\) laisse \(n-p\) points fixes et crée une unique orbite de taille \(p\), il y a donc \(n-p+1\) orbites, donc \(\epsilon(\sigma)=(-1)^{n-(n-p+1)}=(-1)^{p-1}\).

Soient \(\sigma\) une permutation et \(\tau\) une transposition sur un ensemble fini \(X.\) Alors \begin{equation} \epsilon(\sigma\,\tau)=-\epsilon(\sigma). \end{equation}
Notons \(\tau_{a,b}\) cette transposition et \(\sigma':=\sigma\tau_{a,b}\). On cherche à savoir comment les orbites suivant \(\sigma\) vont être perturbées par la transposition \(\tau_{a,b}\). La restriction de \(\tau_{a,b}\) aux orbites qui ne contiennent ni \(a\) ni \(b\) est l'identité, les seules orbites qui sont perturbées par \(\tau_{a,b}\) sont donc uniquement celles qui contiennent \(a\) ou \(b\). Deux cas de figure se présentent, soient \(a\) et \(b\) sont sur la même orbite \(\orb\), soit sur deux orbites distinctes \(\orb\) et \(\orb'\) puisque les orbites suivant \(\sigma\) constituent une partition de l'ensemble \(X\) :
     
À gauche : \(a\) et \(b\) sont sur la même orbite \(\orb\). À droite : \(a\) et \(b\) sont sur deux orbites \(\orb\) et \(\orb'\) distinctes.

Supposons dans un premier temps que \(\{a,b\}\subseteq\orb\) et notons \(p:=|\orb|\geq 2\). Dans ce cas \(a\) (et \(b\)) est un représentant de l'orbite \(\orb\) donc \[\orb=\orb(a)=\{a,\sigma(a),\ldots,\sigma^{p-1}(a)\}\quad\text{et}\ \ \sigma^p(a)=a. \] Puisque \(b\in\orb(a)\), \(b=\sigma^q(a)\) avec \(0 < q\leq p\). Calculons les itérés successifs de \(a\) par la permutation \(\sigma'\). On a \begin{align*} \sigma'(a) &=\sigma(\tau(a)),\\ &=\sigma(b),\\ &=\sigma^{q+1}(a). \end{align*} et \(\sigma'(\sigma^{q+1}(a))=\sigma(\tau(\sigma^{q+1}(a)))\), mais \(\sigma^{q+1}(a)\not\in\{a,b\}\), or la restriction de la transposition \(\tau_{a,b}\) à \(X\setminus\{a,b\}\) est l'identité, donc \[\sigma'(\sigma^{q+1}(a))=\sigma^{q+2}(a)\] et de proche en proche on obtient montre que l'orbite de \(a\) selon \(\sigma'\) est \[a,\;\sigma^{q+1}(a),\;\sigma^{q+2}(a),\;\ldots,\;\sigma^{p-2}(a),\;\sigma^{p-1}(a),\; a.\] Tandis que les itérés de \(b\) selon \(\sigma'\) sont \[b,\;\sigma(b),\;\sigma^2(b),\;\ldots,\;\sigma^{q-1}(b),\;b.\] Autrement dit, l'orbite \(\orb\) a été séparée en deux orbites.
s
Dans l'autre cas (à droite sur la figure), on a \begin{align*} \orb&=\{a,\sigma(a),\sigma^2(a),\ldots,\sigma^{p-1}(a)\},\\ \orb'&=\{b,\sigma(b),\sigma^2(b),\ldots,\sigma^{q-1}(b)\}.\\ \end{align*} Si on calcule les itérés de \(a\) pour \(\sigma'\), on obtient \[a,\;\sigma(b),\;\sigma^2(b),\;\ldots,\sigma^{q-1}(b),\;b,\;\sigma(a),\;\sigma^2(a),\;\ldots,\;\sigma^{p-1}(a),\;a.\] Autrement dit les orbites \(\orb\) et \(\orb'\) ont fusionné. Dans les deux cas le nombre d'orbites suivant \(\sigma'\) est différent du nombre d'orbites suivant \(\sigma\) d'une unité ce qui change donc le signe de la signature et permet de conclure.

Si \(\sigma\in\Sn(X)\) est le produit de \(k\) transpositions, alors \(\epsilon(\sigma)=(-1)^k\).
L'application signature \(\epsilon:\Sn(X)\rightarrow\{-1,1\}\) est un morphisme du groupe sy­mé­tri­que \((\Sn(X),\circ)\) dans le groupe multiplicatif \((\{-1,1\},\times)\).
Le noyau du morphisme \(\epsilon\) qui est un sous-groupe normal de \(\Sn(X)\) est ap­pe­lé groupe alterné et noté \(\def\A{\mathfrak A}\A(X)\).

Soit \(\tau\) une transposition. L'application définie par \(\sigma\mapsto\tau\sigma\) est une bijection de \(\A(X)\) dans \(\Sn(X)\setminus\A(X)\) et comme ces deux ensembles constituent une partition de \(\Sn(X)\) qui est de cardinal \(n!\), on a né­ces­sai­re­ment

\begin{equation} |\A(X)=|\Sn(X)\setminus\A_n|=\frac{n!}{2}. \end{equation}

Autrement dit il y a autant de permutations paires que que de permutations impaires. Dans le cas où \(\Sn(X)=\Sn_{n}\), le sous groupe alterné est noté \(\A_n\) et appelé groupe alterné de degré n.

Soit \(\sigma\in\Sn_n\). Démontrez que \begin{equation} \epsilon(\sigma)=\prod_{\{i,j\}\in {\mathscr P}_2([1,n])}\frac {\sigma (j)-\sigma (i)}{j-i} \end{equation} où \({\mathscr P}_2([1,n])\) désigne l'ensemble des paires d'éléments de \([1,n]\).

Indication : l'application définie par \(\{i,j\}\mapsto\{\sigma(i),\sigma(j)\}\) est une permutation sur \({\mathscr P}_2([1,n])\).
Écrivez en Python une fonction Signature(s) qui calcule la signature de la permutation s passée en paramètre.

Conjugaison

On rappelle que deux permutations \(\sigma\) et \(\sigma'\) sont conjuguées s'il existe une permutation \(\rho\) telle que \(\sigma'= \rho\,\sigma\,\rho^{-1}\). Cela signifie que l'on peut réaliser la permutation \(\sigma'\) à travers la permutation \(\sigma\) au prix d'une traduction. Métaphoriquement pour calculer \(\sigma'(x)\) on code \(x\) pour \(\sigma\) avec \(\rho^{-1}\), on fait le calcul avec \(\sigma\) et on décode le résultat avec \(\rho\). Nous savons qu'il s'agit d'une relation d'équivalence.

Montrez que la classe de conjugaison de la permutation identique \(\text{Id}\) est réduite à \(\text{Id}\) quel que soit le groupe symétrique.
Montrez que les transpositions \((1,2)\) et \((1,3)\) sont conjuguées dans \(\Sn_3\).
Soit \(X\) un ensemble fini et \(\sigma=(x_1,x_2,\ldots,x_p)\) un \(p\)-cycle. La permutation con­ju­guée \(\rho\,\sigma\,\rho^{-1}\) de \(\sigma\) est le \(p\)-cycle dit conjugué : \begin{equation} \label{eq:conjuguecycle} \rho(x_1,x_2,\ldots,x_p)\rho^{-1}=(\rho(x_1),\rho(x_2),\ldots,\rho(x_p)). \end{equation}
Calculons tout d'abord l'image des éléments \(\rho(x_i)\), \(i\in[1,p]\) par les deux permutations de part et d'au­tre de l'égalité \((\ref{eq:conjuguecycle})\) : \begin{align} \rho(x_1,x_2,\ldots,x_p)\rho^{-1}(\rho(x_i)) &=\rho(x_1,x_2,\ldots,x_p)(x_i)\\ &=\begin{cases} \rho(x_{i+1})&\text{si}\ i < p,\\ \rho(x_1)&\text{si}\ i = p. \end{cases} \end{align} D'autre part, \begin{align} (\rho(x_1),\rho(x_2),\ldots,\rho(x_p))(\rho(x_i)) &=\begin{cases} \rho(x_{i+1})&\text{si}\ i < p,\\ \rho(x_1)&\text{si}\ i = p. \end{cases} \end{align} On va faire de même avec \(x\in X\setminus Y\) où \(Y:=\{\rho(x_1),\ldots,\rho(x_p)\}\). On remarque que \(\forall i\in[1,p]\ \rho^{-1}(x)\not=x_i\) sans quoi \(x=\rho(x_i)\) ce qui contredit \(x\in X\setminus Y\), donc \(\rho^{-1}(x)\) n'appartient pas au support du cycle \((x_1,x_2,\ldots,x_p)\), il est donc un point fixe de ce cycle : \begin{align*} \rho(x_1,x_2,\ldots,x_p)\rho^{-1}(x) &=\rho(\rho^{-1}(x))\\ &=x. \end{align*} D'autre part \(x\) est fixe pour le cycle \((\rho(x_1),\rho(x_2),\ldots,\rho(x_p))\) puisque \(x\not\in Y\), donc \begin{align*} (\rho(x_1),\rho(x_2),\ldots,\rho(x_p))(x)=x \end{align*}
Soit \(X\) un ensemble fini et \(\sigma\) une permutation. La permutation conjuguée \(\rho\,\sigma\,\rho^{-1}\) de \(\sigma\) est le produit des cycles conjugués des cycles qui composent \(\sigma\).
En effet, notons \((c_i)_{i\in[1,k]}\) les \(k\) cycles de la décomposition de \(\sigma\). Alors \begin{align*} \rho\sigma\rho^{-1}&=\rho\,{\color{#88F}c_1\,c_2\,c_3\,\ldots\,c_{k-1}\,c_k}\,\rho^{-1}\\ &=\rho\,{\color{#88F}c_1}\,(\rho^{-1}\,\rho)\,{\color{#88F}c_2}\,(\rho^{-1}\,\rho)\,{\color{#88F}c_3}\,\rho^{-1}\ldots\rho\,{\color{#88F}c_{k-1}}\,(\rho^{-1}\,\rho)\,{\color{#88F}c_k}\,\rho^{-1}\\ &=(\rho\,{\color{#88F}c_1}\,\rho^{-1})\,(\rho\,{\color{#88F}c_2}\,\rho^{-1})\,(\rho\,{\color{#88F}c_3}\,\rho^{-1})\ldots(\rho\,{\color{#88F}c_{k-1}}\,\rho^{-1})\,(\rho\,{\color{#88F}c_k}\,\rho^{-1})\\ \end{align*}
Écrivez une fonction Python Conjuguer(s,r) qui calcule la conjuguée de la permutation \(s\) par \(r\).
Soit \(\sigma=c_1c_2\ldots c_k\) la décomposition en produit de cycles à supports disjoints ordonnés selon les longueurs croissantes \(p_i:=|c_i|\). On appelle type de la permutation \(\sigma\) le \(k\)-uplet \((p_1,p_2,\ldots,p_k)\).

Notons \(n_i\) le nombre d'orbites de cardinal \(i\in[1,n]\) suivant la permutation \(\sigma\in\Sn_n\). Les orbites for­mant une partition de \([1,n]\), la formule de sommation nous donne

\begin{equation} n=\sum_{i=1}^nn_i. \end{equation}

D'autre part, le type \((p_1,p_2,\ldots,p_k)\) de la permutation \(\sigma\) contient la taille de chaque orbite qui n'est pas réduite à un élément. Autrement dit le nombre \(n_1\) de points fixes de la permutation \(\sigma\), c'est-à-dire le nombre d'orbites réduites à un singleton est donné par

\begin{equation} n_1=n-\sum_{i=1}^k p_i. \end{equation}

Ceci justifie que le type d'une permutation se dispense de faire apparaître les longueurs 1 des orbites réduites à un élément.

Nous avons vu que la permutation conjuguée d'un cycle par une permutation \(\rho\) est le cycle constitué des images des éléments du cycle par \(\rho\), cf. \((\ref{eq:conjuguecycle})\). Par conséquent :

Deux permutations sont conjuguées si et seulement si elles ont même type.

On en déduit immédiatement que le nombre de types de permutations du groupe \(\Sn_n\) distincts est égal au nombre de façons possibles d'écrire l'entier \(n\) comme la somme d'une suite croissante d'en­tiers non-nuls. Une telle somme est qua­li­fiée de par­ti­tion d'un en­tier. Par exemple, pour \(n=4\), on vé­ri­fie aisément que l'on a exactement les \(5\) par­ti­tions suivantes :

\begin{align*} 4 &=1+1+1+1\quad\text{type vide}\ (\,)\\ &=1+1+2\quad\text{type}\ (2)\\ &=2+2\quad\text{type}\ (2,2)\\ &=1+3\quad\text{type}\ (3)\\ &=4\quad\text{type}\ (4) \end{align*}

Le type vide est celui de la permutation identité.

Combien y-a-t-il de partitions de l'entier \(n=5\) ?
Déterminez les classes de conjugaison des groupes \(\Sn_3\) et \(\Sn_4\).
Soit \(n\) et \(k\) deux entiers naturels non-nuls. Le nombre \(p(n,k)\) de par­ti­tions de l'entier \(n\) en \(k\) parties est \begin{equation} \label{rec:pnk} p(n,k):=\begin{cases} p(n–1, k–1) + p(n–k, k) &\text{si}\ 1 < k < n,\\ 1&\text{si}\ k=1\ \text{ou}\ k=n,\\ 0&\text{si}\ k > n. \end{cases} \end{equation}

En corollaire, on sait à présent que le nombre de partitions \(p(n)\) d'un entier \(n > 0\), c'est-à-dire le nombre de type différents de permutations est égal à \begin{equation} p(n)=\sum_{k=1}^np(n,k). \end{equation}

Écrivez un programme Python qui demande la saisie d'un entier \(N\) et affiche dans une table, à la ma­niè­re du triangle de Pascal, les différentes valeurs \(p(n,k),\) \(1 < k \leq n\) pour \(n\in[1,N].\) Les lignes du tableau sont indexées par \(n\) et les colonnes par \(k\).
On appelle inversion d'une permutation \(\sigma\in\Sn_n\) tout couple \((i,j)\in \N_n^2\) tel que \begin{equation} i < j\ \ \text{et}\ \ \sigma(i) > \sigma(j). \end{equation}
Le nombre total d'inversions du groupe \({\frak S}_n\) est égal à \begin{equation} n!\ \frac{n(n-1)}{4} \end{equation}
Si \(\sigma\) est une permutation de \({\frak S}_n\), on note \(\upsilon\) la permutation miroir de \(\sigma\) définie par \[ \forall i\in[1,n],\quad\upsilon(i):=\sigma(n-i). \] Il est clair que \((i,j)\) est une inversion de \(\sigma\) si et seulement si ce n'est pas une inversion de \(\upsilon\). Le nombre de couples \((i,j)\in[1,n]^2\) tels que \(i < j\) est égal à \(\frac{n(n-1)}{2}\) qui est donc la somme du nombre d'inversions de \(\sigma\) et de son miroir \(\upsilon\). En sommant sur tout le groupe symétrique, on compte deux fois chaque \(\sigma\), il y a donc \[n!\ \frac{n(n-1)}{4}\] inversions au total.

Ces résultats seront très utiles dans l'analyse de la complexité des algorithmes de tri en particulier.

Étude du taquin

Nous pouvons à présent étudier le problème du taquin et répondre à la question initiale. On nu­mé­ro­te les cases du taquin dans l'or­dre de lecture (cf. tableau à gauche ci-dessous), et on numérote éga­le­ment les 15 pièces du taquin de \(1\) à \(15\). Le numéro \(16\) est attribué à une pièce virtuelle, la pièce vide.

1234
5678
9101112
13141516
  
1234
5678
9101112
131514
À gauche : numérotation des cases du taquin. À droi­te : positions des pièces en configuration de Loyd.

En associant à chaque numéro de case du taquin le numéro de la pièce qui y est placée, la disposition des \(16\) pièces sur le taquin définit une permutation \(\sigma\in\Sn_{16}\). On l'appelera dans la suite la con­fi­gu­ra­tion du taquin. La con­fi­gu­ra­tion du taquin proposée par Loyd est la permutation :

\begin{equation} \sigma=\begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&11&12&13&\color{#88F}14&\color{#88F}15&16\\ 1&2&3&4&5&6&7&8&9&10&11&12&13&\color{#88F}15&\color{#88F}14&16\\ \end{pmatrix} \end{equation}

Elle ne contient qu'un seul cycle d'ordre 2, c'est la transposition \({\color{#88F}(14,15)}\).

Comment se traduit le déplacement d'une pièce \(k\) sur le taquin ? Compte tenu de la règle du jeu, on ne peut échanger la pièce \(k\) qu'avec la pièce vide numérotée \(16\), autrement dit un mouvement, quand il est possible, est nécessairement une transposition de la forme \((k,16)\). La condition n'est bien sûr pas suffisante, pour qu'une transposition \((k,16)\) soit possible, il faut que les pièces \(k\) et \(16\) soient ad­ja­cen­tes, i.e. qu'elles aient un côté com­mun.

Soit \(\sigma\) la permutation associée à une configuration du taquin. Nous dirons qu'une transposition \(\tau\) est compatible avec la configuration \(\sigma\) si et seulement si elle est de la forme \(\tau=(16,k)\) et que les pièces \(k\) et \(16\) sont ad­ja­cen­tes sur le taquin. Dans ce cas, \(\tau\sigma\) est une nouvelle configuration du taquin, on dira donc plus généralement qu'une permutation \(\pi\) est com­pa­ti­ble avec la configuration \(\sigma\) si \(\pi\) est dé­com­po­sa­ble en un produit de \(n\) transpositions \[\pi=\tau_{n}\,\tau_{n-1}\,\ldots\tau_2\,\tau_1.\] telles que \(\forall i\in[1,n]\), \(\tau_i\) est compatible la permutation \[\tau_{i-1}\tau_{i-2}\ldots\tau_{2}\tau_{1}\sigma.\] Ce qui signifie ni plus ni moins qu'en partant de la configuration \(\sigma\), les transpositions \(\tau_1,\tau_2,\ldots,\tau_n\) sont réalisables successivement.

Pour résoudre une configuration \(\sigma\) du taquin, et celle de Loyd en particulier, il faut donc remettre toutes les pièces dans l'ordre, c'est-à-dire trouver une suite finie \(({\color{#FF0}\tau_i})_{i\in[1,n]}\) de trans­po­si­tions com­pa­ti­bles avec \(\sigma\) telle que son produit à gauche avec \(\sigma\) est la permutation iden­ti­té, soit :

\begin{equation} \label{eq:sigmataquin} {\color{#FF0}\tau_n\,\tau_{n-1}\,\ldots\,\tau_2\,\tau_1}\sigma=\text{Id}. \end{equation}

Isolons \(\sigma\) dans l'équation \((\ref{eq:sigmataquin})\). L'inverse d'un produit de bijections est le produit inverse des bi­jec­tions réciproques (cf. exercice) et toute transposition \(\tau\) est une involution donc \(\tau^{-1}=\tau\), d'où \begin{equation} \label{eq:isolesigma} \sigma={\color{#FF0}\tau_1\,\tau_{2}\,\ldots\,\tau_{n-1}\,\tau_n}. \end{equation}

Nous dirons donc dans la suite qu'une configuration \(\sigma\) du taquin est résoluble s'il existe un produit de transpositions compatibles avec \(\sigma\) satisfaisant \((\ref{eq:isolesigma})\), insoluble sinon. Si une configuration est ré­so­lu­ble, les mouvements à réaliser effectivement sur le taquin sont les transpositions \(\tau_i\) dans l'ordre croissant des indices. Si un tel produit existe, sa signature doit bien sûr être égale à celle de \(\sigma\) :

\begin{align} \notag\epsilon(\sigma)&=\epsilon({\color{#FF0}\tau_1\,\tau_{2}\,\ldots\,\tau_{n-1}\,\tau_n}),\\ \notag\epsilon(\sigma)&=\prod_{i=1}^n\epsilon({\color{#FF0}\tau_i}),\\ \label{eq:lastloyd}\epsilon(\sigma)&=(-1)^n. \end{align}

Ces deux dernière égalités sont justifiées par le fait que la signature d'une transposition est égale à \(-1\) et que la signature d'un produit de permutations est égal au produit des signatures de ces permutations (cf. corollaire).

La signature de la configuration de Loyd \(\sigma=(14,15)\) est égale à \(-1\) puisqu'il s'agit d'une trans­po­si­tion. On déduit de \((\ref{eq:lastloyd})\) que l'on doit avoir \(-1=(-1)^n,\) autrement dit que le nombre \(n\) de trans­po­si­tions dans le produit \(\color{#FF0}\pi\) doit être impair. Colorions les cases du taquin pour en faire un damier noir et blanc. La con­fi­gu­ra­tion initiale de Loyd est :

1234
5678
9101112
131514
Configuration de Loyd sur un taquin en damier.

Une transposition de la forme \((16,k)\) fait passer alternativement la pièce vide d'une case noire à une case blanche. Pour que la pièce vide retrouve sa position initiale 16 sur le damier, le produit \({\color{#FF0}\pi}\) doit donc nécessairement contenir un nombre pair de transpositions, la configuration de Loyd est par conséquent insoluble. Nous venons de démontrer le théorème suivant :

Une configuration du taquin \(\sigma\) résoluble est paire.

Une condition nécessaire pour que taquin soit résoluble est que la configuration ini­tia­le définisse une permutation \(\sigma\) du groupe alterné \(\A_{15}\), si l'on suppose que la pièce vide est en position \(16\).

Cette condition est-elle suffisante ? Il faut garder à l'esprit que pour résoudre le taquin, il faut disposer d'un produit de transpositions compatible avec la permutation \(\sigma\) associée à la configuration initiale du taquin. Par exemple, seules les transpositions \((16,12)\) et \((16,15)\) sont compatibles avec la configuration de Loyd.

Nous allons montrer dans un premier temps que le groupe alterné \(\A_n\) est engendré par les \(3\)-cycles du type \((1,2,s)\) et dans un deuxième temps que tous les trois cycles de ce type sont décomposables en produit de trans­po­si­tions compatibles avec l'identité.

Le groupe alterné \(\A_n\) est engendré par les \(3\)-cycles.
Montrons que le sous-groupe \(G\) de \(\Sn_n\) engendré par les \(3\)-cycles est contenu dans \(\A_n\). Soit \((x,y,z)\) un \(3\)-cycle, on peut le décomposer en le produit des deux transpositions \((x,y)(y,z)\). Sa signature est donc \(+1\), il appartient bien à \(\A_n\). Évidemment la composition de \(3\)-cycles conserve la parité, le groupe \(G\) est donc un sous-groupe de \(\A_n\). Réciproquement, montrons que tout élément de \(\A_n\) appartient à \(G.\) Soit \(\sigma\in\A_n\), elle admet une décomposition en un produit de \(2k\) transpositions \((\tau_i)_{i\in[1,2k]}\) que l'on peut apparier comme suit : \[ \sigma=(\tau_1\tau_2)\,(\tau_3\tau_4)\,\ldots\,(\tau_{2k-1}\tau_{2k}). \] Observons un seul appariement \(\tau_i\tau_{i+1}\), il y a quatre situations possibles :
  1. \((i,j)\,(i,j)=\text{Id}\),
  2. \((i,j)\,(i,k)=(i,k,j)\),
  3. \((i,j)\,(j,k)=(i,j,k)\),
  4. \((i,j)\,(k,l)=(i,j)\,{\color{#88F}(j,k)\,(j,k)}\,(k,l)=(i,j,k)\,(j,k,l)\).
et dans tous les cas, on peut l'écrire comme un produit de \(3\)-cycles.
Le groupe alterné \(\A_n\) est engendré par les \(3\)-cycles de la forme \((1,2,s)\) avec \(s\in[3,n]\).
D'après le théorème précédent, il suffit de montrer que tout \(3\)-cycle \((i,j,k)\) peut se décomposer en produit de \(3\)-cycles de la forme \((1,2,r)\). Puisque \((i,j,k)=(j,k,i)=(k,i,j)\), on peut toujours supposer que \(i\) est le plus petit des trois. Il y quatre cas de figure : \begin{align*} (1,j,2) &= (1,2,j)^{-1},\\ (1,j,k) &= (1,2,k)\;(1,2,j)^{-1},\\ (2,j,k) &= (1,2,k)^{-1}\;(1,2,j),\\ (i,j,k) &= (1,2,k)\;(1,2,j)^{-1}\;(1,2,i)\;(1,2,k)^{-1}. \end{align*}

Les \(3\)-cycles du type \((1,2,s)\) pour \(\A_{15}\) sont au nombre de \(13\) :

\begin{equation} \label{troiscycles} (1,2,{\color{#88F}3}),\ (1,2,{\color{#88F}4}),\ (1,2,{\color{#88F}5}),\ldots,\ (1,2,{\color{#88F}14}),\ \text{et}\ (1,2,{\color{#88F}15}). \end{equation}

Et nous allons prouver que l'on peut réaliser n'importe lequel de ces \(3\)-cycles sur le taquin.

Soit \(k\in\N\) tel que \(k\geq 2\). On ap­pel­le circuit de longueur \(k\) toute séquence \((c_i)_{i\in[1,k]}\) de cases distinctes du taquin telles que deux cases con­sé­cu­ti­ves de cette suite sont toujours adjacentes et telle que \(\def\vide{{\color{#C22}16}}c_k\) est adjacente à \(c_1\). La suite des cases numéro 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, ma­té­ria­li­sée en rouge dans le taquin ci-dessous est un circuit de longueur \(12\) :

1234
5678
9101112
13141516
Un circuit de longueur 12 dans le taquin.
Démontrez qu'en coloriant les cases du taquin en damier, deux cases adjacentes d'un circuit sont de couleurs différentes. Démontrez que la longueur d'un cir­cuit est toujours paire. Quelle est la longueur des circuits les plus courts ?

Dorénavant nous noterons \(\def\tua{{\color{#F44}\tau}}\tua_i:=(16,i)\), \(i\in[1,15]\) les 15 transpositions possibles sur le taquin. Soit \(\sigma\) la permutation associée à une configuration du taquin. Si on note \(p_i\) les pièces qui sont placées sur les cases \(c_i\) d'un circuit \((c_i)_{i\in[1,\,k]}\) respectivement, on a donc \[\forall i\in[1,\,k]\quad \sigma(c_i)=p_i.\]

Soit \(\sigma\) une configuration du taquin et \((c_i)_{i\in[1,\,k+1]}\) un circuit de longueur \(k+1\) contenant res­pec­ti­ve­ment les pièces \(p_i\) avec \(p_{k+1}=16\) la pièce vide. Alors le produit des \(k+1\) transpositions \begin{equation} \label{eq:permcirc} \pi:=\tua_{p_1}\;\tua_{p_k}\;\tua_{p_{k-1}}\;\ldots\;\tua_{p_3}\;\tua_{p_2}\;\tua_{p_1}\; \end{equation} est compatible avec \(\sigma\). D'autre part, \(\pi\,\sigma\) réalise un décalage circulaire des éléments \(p_i\) dans les \(k\) pre­miè­res cases du circuit \(c_i\).
Dans les grandes lignes : il faut généraliser l'exemple qui suit en partant d'un circuit quelconque et montrer que le contenu d'une case n'est modifié que par une seule trans­po­si­tion (ce qui explique la définition d'un circuit ici qui ne repasse jamais deux fois par la même case, le vocabulaire de la théorie des graphes parle de circuit hamiltonien) et que ce contenu après la transposition est bien le contenu de la case adjacente avant la transposition.

Exemple. On considère une configuration \(\sigma\) du taquin et le circuit \(c:=(2,3,7,11,10,9,5,1)\) de lon­gueur 8 sur lequel sont placées les pièces \(a,\) \(b,\) \(c,\) \(d,\) \(e,\) \(f,\) \(g\) et \(\vide\) respectivement. Calculons \(\pi\sigma\) avec le produit \(\pi\) défini par \[\pi:=\tua_a\,\tua_g\,\tua_f\,\tua_e\,\tua_d\,\tua_c\,\tua_b\,\tua_a.\] La pièce vide et la pièce adjacente \(k\) de la trans­po­si­tion \(\tau_k\) ont leur côté commun en poin­til­lés :

 
\(a\)\(b\)
\(g\)\(c\)
\(f\)\(e\)\(d\)
 
\(\tua_{a}\)
\(a\)\(b\)
\(g\)\(c\)
\(f\)\(e\)\(d\)
 
\(\tua_{b}\)
\(a\)\(b\)
\(g\)\(c\)
\(f\)\(e\)\(d\)
 
\(\tua_{c}\)
\(a\)\(b\)\(c\)
\(g\)
\(f\)\(e\)\(d\)
 
\(\tua_{d}\)
\(a\)\(b\)\(c\)
\(g\)\(d\)
\(f\)\(e\)
\(\tua_{e}\)
\(a\)\(b\)\(c\)
\(g\)\(d\)
\(f\)\(e\)
 
\(\tua_{f}\)
\(a\)\(b\)\(c\)
\(g\)\(d\)
\(f\)\(e\)
 
\(\tua_{g}\)
\(a\)\(b\)\(c\)
\(d\)
\(g\)\(f\)\(e\)
 
\(\tua_{a}\)
\(b\)\(c\)
\(a\)\(d\)
\(g\)\(f\)\(e\)
Rotation des pièces autour d'un circuit sur le taquin.

On a montré que le produit \(\pi:=\tua_a\,\tua_g\,\tua_f\,\tua_e\,\tua_d\,\tua_c\,\tua_b\,\tua_a\) est compatible avec la permutation \(\sigma\) et en cal­cu­lant \(\pi\,\sigma\), on a remplacé la séquence \(\color{#AAF}(a,b,c,d,e,f,g)\) par la séquence \(\color{#AAF}(b,c,d,e,f,g,a)\) sur ce circuit et il suffit d'itérer \(\pi\) pour faire tourner ces pièces autour du circuit en laissant toutes les autres fixes.

Dans le cas particulier où le circuit est un carré \(2\times 2\), on a le produit suivant (on ne représente plus les autres pièces qui sont fixes) :

 
\(a\)
\(c\)\(b\)
 
\(\tua_{a}\)
\(a\)
\(c\)\(b\)
 
\(\tua_{b}\)
\(a\)\(b\)
\(c\)
 
\(\tua_{c}\)
\(a\)\(b\)
\(c\)
 
\(\tua_{a}\)
\(b\)
\(a\)\(c\)
Création d'un \(3\)-cycle sur le taquin.

Ce qui réalise une rotation des trois valeurs \(\color{#AAF}(a,b,c)\). Par exemple, en partant de la configuration iden­ti­té \(\sigma:=\text{Id}\), on obtient le \(3\)-cycle \((11,12,15)\) à l'aide des quatre transpositions : \[\tua_{15}\,\tua_{12}\,\tua_{11}\,\tua_{15}.\]

1234
5678
9101112
131415
  
1234
5678
9101215
131411
Création du \(3\)-cycle \((11,12,15)\) sur le taquin.

Mais nous cherchons à construire les \(3\)-cycles particuliers de \((\ref{troiscycles})\) pour en­gen­drer le groupe \(\A_{15}\). Le lemme suivant est évident mais important.

On peut déplacer la pièce vide sur n'importe quelle case \(i\in[1,16]\) du taquin et il faut au plus \(6\) transpositions \(\tua_{k}\) pour ce faire.
Quelle que soit la position initiale de la pièce vide sur le taquin, il y a au plus trois colonnes et trois lignes à parcourir pour arriver à la case \(i\).

Nous allons montrer comment obtenir le cycle \(\color{#AAF}(9,10,13)\) avec les techniques de trans­po­si­tion pré­sen­tées. On note \(\sigma:=\tua_{14}\tua_{15}\) la permutation qui déplace la pièce vide à la case 14. On fait alors tourner \(9,\) \(10\) et \(13\) autour du circuit grâce au produit \(\tua_{13}\,\tua_{10}\,\tua_{9}\,\tua_{13}\) et on ramène la pièce vide en case 16 :

 
1234
5678
9101112
131415
 
\(\sigma\)
1234
5678
9101112
131415
 
\(\tua_{13}\,\tua_{9}\,\tua_{10}\,\tua_{13}\)
1234
5678
10131112
91415
   
\(\sigma^{-1}\)
1234
5678
10131112
91415
Réalisation du \(3\)-cycle \((9,10,13)\) sur le taquin.

On a donc montré à l'aide d'une conjugaison que : \begin{align*} (9,10,13)&=\sigma^{-1}\,\tua_{13}\,\tua_{9}\,\tua_{10}\,\tua_{13}\,\sigma,\\ &=(\tua_{15}\,\tua_{14})\,\tua_{13}\,\tua_{9}\,\tua_{10}\,\tua_{13}\,(\tua_{14}\,\tua_{15}). \end{align*}

Le programme que vous avez pu utiliser en début de chapitre et qui résout le problème du taquin dans le cas où la permutation \(\sigma\in\A_{16}\) applique exactement la stratégie que nous venons de déployer. Résumons :

  1. On décompose \(\sigma\) en produit de cycles (cf. théorème),
  2. On décompose chaque cycle du produit en produit de transpositions (cf. théorème),
  3. On construit un produit de \(3\)-cycles en appariant ces transpositions (cf. théorème),
  4. On décompose ces \(3\)-cycles en \(3\)-cycles du type \((1,2,s)\) (cf. proposition),
  5. On calcule l'inverse de ce produit,
  6. Pour chaque élément du produit inverse, on exécute la séquence de déplacements appropriés sur le taquin.

Vous pouvez voir ces étapes en faisant apparaître la console javascript dans votre na­vi­ga­teur (sous Chromium, il suffit de cliquer sur \(\boldsymbol\vdots\) en haut à droite, puis de sélectionner "Plus d'outils" et "Outils de développement").

Vous avez pu constater que le nombre de mouvements pour remettre les pièces dans l'ordre est con­sé­quent, quel est le nombre minimum de déplacements nécessaires pour résoudre une configuration ? Peut-on simplifier les produits de \(3\)-cycles ?

Construisez le \(3\)-cycle \((1,2,3)\) à l'aide de transpositions compatibles. Indication : considérez le circuit formé par les \(12\) cases en bordure du taquin en configuration identité et faites tourner les \(11\) pièces autres que la pièce vide d'une position dans le sens anti-horaire. Déplacez la pièce vide sur la case numéro \(6\) et faites tourner les pièces \((1,2,3)\) puis ramenez la pièce vide en position \(16\). Vérifiez que \((1,2,4)\) est le conjugué de \((1,2,3)\) par \((3,4,8,12,15,11,7)\).
En vous inspirant de cet exemple, construisez les \(3\)-cycles suivants  \begin{align*} &(1,2,5),&\quad&(6,11,7),&\quad&(3,6,7),\\ &(5,9,6),&\quad&(6,10,7),&\quad&(3,8,4),\\ &(11,15,12),&\quad&(10,14,11),&\quad&(9,13,10).\\ \end{align*} Calculer le conjugué de \((1,6,2)\) avec \((5,9,6)\). Avec d'autres conjugaisons, trouvez tous les \(3\)-cycles man­quants.