Introduction, le taquin

Le but du jeu est de ranger les 15 pièces dans l'ordre croissant de \(1\) à \(15\) en faisant coulisser les pièces le long des lignes et des colonnes. 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.

Nous avons étudié aux chapitres précédents, les ensembles puis 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

On équipe à présent les ensembles de lois de composition et on en étudie leurs propriétés. Il s'agit de généraliser à des ensembles quelconques les opérations usuelles sur les ensembles de nombres (addition, multiplication, etc.) en mettant l'accent sur les propriétés qu'elles partagent plutôt que leurs particularités, et d'en tirer des résultats universels susceptibles d'être appliqués à toutes sortes de situations.

Lois de composition internes, magmas

On note généralement une loi de composition de manière infixe, soit \(x\;{\color{#FF8}\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 \(\N\) au cha­pi­tre Combinatoire sont donc des lois de com­po­si­tion internes faisant de \((\N,+)\) et \((\N,\times)\) deux magmas. La réunion \(\cup\) et l'intersection \(\cap\) sur \({\mathscr P}(X)\) l'ensemble des parties d'un ensemble \(X\) sont des lois de composition internes faisant de \(({\mathscr P}(X),\cup)\) et \(({\mathscr P}(X),\cap)\) deux magmas. 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\) faisant de \((X^X,\circ)\) un magma. La concaténation \(\cdot\) est une loi de composition interne sur l'ensemble \(\Sigma^*\) des mots définis sur un alphabet fini \(\Sigma\) faisant de \((\Sigma^+,\cdot)\) un magma.

Dans la suite, \((X,\diamond)\) désignera un magma.

Dans ce cas, la restriction de la loi de com­po­si­tion \(\diamond\) aux éléments de \(A\times 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 \(2\,\N\) des entiers pairs est une partie stable pour la loi d'addition \(+\) sur l'ensemble des entiers naturels \(\N\) faisant de \((2\,\N,+)\) un magma. L'ensemble \(S(X)\) des bijections d'un ensemble \(X\) sur lui-même est une partie stable de \(X^X\) pour la loi de composition des applications \(\circ\).

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

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). La loi puissance est bien une loi de composition interne sur \(\N\), mais n'est pas associative, par exemple \(2^{(2^3)}=256\) alors que \((2^2)^3=64\).

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

On appelle centre d'un magma, le sous-ensemble \(Z_X\) des éléments de \(X\) qui commutent avec n'im­por­te quel élément de \(X\). Si \(Z_X=X\), le magma est dit magma commutatif, c'est le cas de l'ensemble \(\N\) pour la loi additive ainsi que pour la loi multiplicative. En revanche la loi de composition des applications \(\circ\) n'est en gé­né­ral pas com­mu­ta­ti­ve pour le magma \((X^X,\circ)\), on peut s'en convaincre en composant 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

S'il existe un élément neutre, celui-ci 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 \({\Id}_X\).

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

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.\)

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\) et réciproquement : \begin{align*} \forall (A,B,C)\in{\mathscr P}(X)^3\quad A\cap(B\cup C)&=(A\cap B)\cup(A\cap C),\\ \forall (A,B,C)\in{\mathscr P}(X)^3\quad A\cup(B\cap C)&=(A\cup B)\cap(A\cup C). \end{align*}

É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

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

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.

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 in­for­ma­ti­que. Un magma associatif est appelé un semi-groupe. Un semi-groupe unifère est appelé un mo­noï­de, c'est donc un magma associatif muni d'un élément neutre. Un monoïde dont tous les éléments sont symétrisables est appelé un groupe et nous y reviendrons plus loin tant cette structure est importante.

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 symétrisables à gauche (resp. à droite) du magma \((X^X,\circ)\) sont les injections (resp. surjections). Les éléments sy­mé­tri­sa­bles du magma \((X^X,\circ)\) pour la loi de composition des ap­pli­ca­tions \(\circ\) sont donc les bijections.

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

Si \(a\) admet un symétrique à gauche \(a'\), alors il existe une unique solution. En effet en composant \(a'\) aux membres gauches et droits de l'identité \((\ref{eq:eqmonoide})\), on a :

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

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:eqmonoide}).\) L'étude est symétrique pour l'équation \(x\diamond a=b\) pour laquelle \(b\diamond a'\) est l'unique solution.

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 très utiles 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 externes

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

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 monoïde \((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

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 composition externes dans les prochains chapitres.

Morphismes

Nous avons déjà rencontré un morphisme au chapitre Combinatoire. Une application croissante en­tre 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 le morphisme

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).\text{exp}(y)\).

Vocabulaire. Si \(f:X\rightarrow Y\) est un morphisme injectif, on dit que c'est mo­no­mor­phis­me, s'il est surjectif on dit que c'est un épi­mor­phis­me. Si \(Y=X\), on dit que \(f\) est un en­do­mor­phis­me. Si \(f\) est bijective et que la bijection ré­ci­pro­que \(f^{-1}\) est encore un mor­phis­me on dit que \(f\) est un iso­mor­phis­me. Un isomorphisme de \(X\) dans lui-même est appelé un au­to­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.

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 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').\]

Compatibilité. Si plusieurs structures équipent un même ensemble, il est naturel de s'intéresser à leur cohabitation. L'omniprésence des relations d'équivalence et des lois de composition sur les ensembles justifie que l'on se questionne sur l'articulation d'une relation d'équivalence avec une loi de composition interne \(\diamond\) d'un magma \((X,\diamond)\).

Si l'on dispose d'une relation d'équivalence \(\rel\) et d'une loi de composition interne \(\diamond\) sur un ensemble \(X,\) on souhaite pouvoir équiper l'ensemble quotient \(X/\rel\) d'une loi de composition \(\overline{\diamond}\) héritée de \(\diamond\). Plus précisément, si \(A\) et \(B\) désignent deux classes d'équivalence pour \(\rel\), on veut définir la composition \(A\overline{\diamond} B\) comme la classe d'équi­va­len­ce de \(a\diamond b\) si \(a\) et \(b\) désignent des représentants quel­con­ques de \(A\) et de \(B\) respectivement. Ceci n'est possible bien sûr que si \(\overline{a\diamond b}\) ne dépend pas du choix des représentants \(a\) et \(b\), ce qui va imposer certaines conditions sur la relation \(\rel\). C'est l'objectif qu'il faut garder à l'esprit pour ne pas se perdre dans les méandres des cons­truc­tions algébriques qui vont suivre.

Trivialement, si la loi \(\diamond\) est commutative, la compatibilité à gauche est équivalente à la compatibilité à droite.

Supposons que \({\rel}\) soit compatible avec \(\diamond\) et soit \((\overline{a},\overline{b})\in (X/{\rel})^2\). Montrons que si \(a_1\) et \(a_2\) (resp. \(b_1\) et \(b_2\)) sont deux représentants quelconques de la classe \(\overline{a}\) (resp. de la classe \(\overline{b}\)), alors \(\overline{a_1\diamond b_1}=\overline{a_2\diamond b_2}.\) On a d'une part \begin{align*} a_1&{\rel}a_2,\\ b_1&{\rel}b_2. \end{align*} et la compatibilité à droite et à gauche de \(\rel\) sur \(\diamond\) permet d'en déduire que \begin{align*} (a_1\diamond{\color{blue}b_1})&{\rel}(a_2\diamond{\color{blue}b_1})\\ ({\color{#FF8}a_2}\diamond b_1)&{\rel}({\color{#FF8}a_2}\diamond b_2). \end{align*} La transitivité de \(\rel\) nous donne \((a_1\diamond{\color{blue}b_1}){\rel}({\color{#FF8}a_2}\diamond b_2)\) soit \(\overline{a_1\diamond b_1}=\overline{a_2\diamond b_2}\) d'après cet exercice. La loi de composition sur le quotient peut donc être définie par \begin{equation} \label{eq:loiquotient} \overline{a}\overline{\diamond}\overline{b}:=\overline{a\diamond b}. \end{equation} puisqu'elle ne dépend pas du choix des représentants \(a\) et \(b\) des classes \(\overline{a}\) et \(\overline{b}\). Grâce à la compatibilité de \({\rel}\) avec \(\diamond\), le quotient \(X/{\rel}\) peut donc hériter de la même loi que celle qui équipe \(X\) :

Par abus de langage, la loi quotient sur l'ensemble quotient est généralement notée comme la loi qui équipe l'ensemble sous-jacent.

La construction abstraite de l'ensemble \(\Z\) des entiers relatifs dans la section suivante est une occasion d'appliquer ces différents résultats et de mieux les com­pren­dre.

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 qu'une équation du type \((\ref{eq:eqmonoide})\) admette une solution.

Considérons le monoïde \((\N,+)\). Il est commutatif par définition de l'addition dans \(\N\), la réunion ensembliste étant commutative. Soit \((n,m)\) un couple d'entiers naturels, l'équation

n'admet de solution dans \(\N\) que si \(m\geq n\). Le cas échéant, on a bien sûr envie d'écrire que cette solution est égale à \(m-n\), mais nous n'avons pas encore défini la loi soustractive \(-\), c'est précisément l'objet de cette construction. Soit \(x\) une solution de \((\ref{eq:symetrisation})\), quand elle existe. Dans ce cas, pour tout \({\color{#FF8}k}\in\N\), \(x\) est également so­lu­tion de l'équation

Ainsi, pour \(n\) et \(m\) fixés, tous les couples de la forme \((n+{\color{#FF8}k},m+{\color{#FF8}k})\) définissent des équations \((\ref{eq:symetrisation})\) qui admettent la même solution. Il est tentant de définir la relation qui lie tous ces couples par la proposition \((n,m){{\rel}}(n',m')\Leftrightarrow n-n'=m-m'\), mais il faut l'écrire sans soustraction :

On définit alors l'addition sur \(\N\times\N\) qui est une loi de composition interne en conservant la même notation que pour l'addition dans \(\N\) :

On définit \(\Z:=(\N\times\N)\,/{\rel}\) qui, d'après le théorème sur la loi quotient, est muni de la loi additive quotient puisque la relation est compatible. On montre facilement que \((0,0)\) est l'élément neutre pour cette loi et qu'elle est associative et commutative. D'autre part, tout couple \((n,m)\) admet un symétrique, il s'agit du couple \((m,n)\), en effet

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 ces couples représentent toutes les classes. D'autre part les classes \((0,n)\) sont les classes opposées des classes \((n,0)\) pour l'addition définie ci-dessus. On montre que le sous-ensemble de \((\Z,+)\) 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]\).

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}\). 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

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 omniprésents en mathématiques et 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.

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é, en­tre autres, que l'on ne pou­vait 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.

Soit \((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.

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

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

L'ensemble des entiers relatifs \(\Z\) est un groupe commutatif pour l'addition, et \(\Z\setminus\{0\}\) 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 commutatif pour la multiplication.

Sous-groupes

Le sous-ensemble \(\{-1,1\}\) de \(\Z\) muni de la multiplication induite est un sous-groupe de \((\Z,\times)\). L'ensemble \(3\Z:=\{3k\mid k\in\Z\}\) des multiples de \(3\) muni de l'addition 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\) ce qui prouve la proposition suivante :

Le théorème suivant est particulièrement utile, il fournit plusieurs caractérisations d'un sous-groupe, soit autant de pistes pour démontrer qu'un sous-ensemble \(H\subseteq G\) muni de la loi induite par celle du groupe \((G,\diamond)\) est bien un de ses sous-groupes.

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\).

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\).

On admettra le théorème suivant :

L'image et le noyau d'un morphisme fournissent des critères simples pour décider s'il est surjectif ou injectif, ce qui s'avère très utile en pratique :

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.

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

Sous-groupes normaux

Soit \(G\) un groupe, \(a\in G\) et \(H\) et \(H'\) deux sous-groupes de \(G\). On dit que \(H\) et \(H'\) sont conjugués par \(a\) si et seulement si \(H'=aHa^{-1}\).

Autrement dit, un sous-groupe est normal s'il est égal à tous ses conjugués. Si \((G,\diamond)\) est un groupe d'élément neutre \(e\), alors \((\{e\},\diamond)\) et \((G,\diamond)\) sont deux sous-groupes normaux de \((G,\diamond)\), dits triviaux et s'il n'y en a pas d'autres, alors \((G,\diamond)\) est appelé un groupe simple. Les groupes simples et finis jouent un rôle majeur dans l'étude générale des groupes finis, car ces derniers sont tous construits à partir de ces groupes simples. Leur très difficile classification a demandé des dizaines d'années de recherche et s'est achevée au début des années 1980.

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 sait déjà que l'image ou l'image réciproque d'un sous-groupe par un morphisme de groupe est un sous-groupe et on peut montrer que l'image et l'image réciproque d'un sous-groupe normal par un morphisme de groupe sont des sous-groupes normaux. 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'équivalence qui sont compatibles avec une loi de groupe. En effet, il faut se souvenir que l'on ne peut transporter la loi de composition qui équipe l'ensemble sur ll'ensemble quotient, qu'à la condition que la relation d'équivalence soit com­pa­tib­le avec sa loi de composition. Dans le cas particulier où le magma est un groupe, les seules relations d'équivalence compatibles avec sa loi sont en­tiè­re­ment ca­rac­té­ri­sées par les sous-groupes normaux de \(G\).

Les classes d'équivalence des relations \(\color{orange}{\mathscr R}_g\) et \(\color{lightblue}{\mathscr R}_d\) définies en \((\ref{eq:rgrd})\) sont respectivement les ensembles \begin{equation} a\diamond H:=\{a\diamond h\mid h\in H\}\quad\text{et}\quad H\diamond a:=\{h\diamond a\mid h\in H\}, \end{equation} appelés classes à gauche et classes à droite suivant \(H\). L'application \(x\mapsto x^{-1}\) de \(G\) dans \(G\) définit une bijection entre \(a\diamond H\) et \(H\diamond a^{-1}\), autrement dit l'ensemble des inverses des éléments de \(a\diamond H\) est l'ensemble \(H\diamond a^{-1}\). Par conséquent, les deux ensembles quotients \(G/{\mathscr R}_g\) et \(G/{\mathscr R}_d\) sont équipotents et s'ils sont finis leur cardinal est appelé indice de \(H\) dans \(G\), on le note \((G:H)\) ou \([G:H]\) ou encore \(|G:H|\). Le théorème de Lagrange qui va suivre est un résultat fondamental, il est omniprésent dans les raisonnements qui concernent les groupes finis.

Soit \({\rel}\) 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}}y\) si et seulement si \(y\in x\diamond H\) et \(y\in H\diamond x\), soit

soit \(H\trianglelefteq G\). Réciproquement si \(H\trianglelefteq G\), la relation \({\rel}\) définie par \(x{{\rel}}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\). Par conséquent :

Puisque les relations d'équivalence compatibles avec une loi de groupe sont complètement caractérisées par les sous-groupes normaux du groupe, le groupe quotient est noté \(G\,/\,H\) plutôt que \(G\,/\,{\rel}\). D'autre part, 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'équivalence compatibles avec l'addition sur \(\Z\) sont donc du type \[x{{\rel}}y\Leftrightarrow y-x\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.

Le groupe symétrique

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 avoir pour autant étudié le groupe symétrique.

Si deux ensembles \(X\) et \(Y\) sont équipotents, étudier le groupe symétrique de l'un est équivalent à étudier celui de l'autre. En effet si \(f:X\rightarrow Y\) est une bijection alors l'application \(\varphi:{S}(X)\rightarrow{S}(Y)\) définie par \(\sigma\mapsto f\circ \sigma\circ f^{-1}\) est un iso­mor­phis­me de groupes. En particulier, si un ensemble est fini de cardinal \(n\), l'étude de son groupe symétrique peut toujours se ramener à l'étude du groupe symétrique \(S_n\) de degré \(n\). Ceci montre que l'étude du groupe symétrique \({S}_n\) de degré \(n\) ne se limite pas à l'étude des permutations des éléments de l'ensemble \(\llbracket 1,\,n\rrbracket \) mais concerne tous les ensembles finis de car­di­nal \(n\).

Le théorème de Cayley ci-dessous va plus loin et affirme que n'importe quel groupe peut être assimilé à un sous-groupe du groupe symétrique, justifiant l'intérêt que l'on accorde à ce groupe.

Nous allons 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{S}_n\) sous la forme d'une matrice de 2 lignes de \(n\) entiers dont la première ligne contient tous les entiers de \(1\) à \(n\) dans l'ordre croissant et la seconde leurs images en vis-à-vis :

C'est un résultat à ne pas perdre de vue. 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 tous les groupes.

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\).

Orbites

Soit \(k\in\N\). Si \(k\geq 0\), la notation \(\sigma^k\) désigne la \(k\)-ème itérée de \(\sigma\), i.e. la composition de \(k\) termes \(\sigma\) et la notation \(\sigma^{-k}\) la \(k\)-ème itérée de la permutation inverse \(\sigma^{-1}\).

La proposition suivante va nous permettre d'élaborer un algorithme pour construire l'orbite \(\orb_\sigma(x)\) d'un élément \(x\) de \(\llbracket 1,\,n\rrbracket \) suivant une permutation \(\sigma\in\Sn_n\).

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 par exemple la permutation \(\sigma\in\Sn_{9}\) sui­van­te :

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

La représentation sagittale du graphe de cette permutation permet de mieux visualiser les différentes orbites et l'origine du vocabulaire employé :

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

Cycles

La permutation \(\sigma\) définie \((\ref{def:perm1})\) contient donc un \(4\)-cycle et un \(3\)-cycle mais aucune transposition.

À 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

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\)-uplet \[(x_1,x_2,\ldots,x_p)\] qui le caractérise puisque \(\sigma(x_i)=x_{i+1}\) pour \(i\in\ab{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}\).

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

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 la liste des images \(\sigma(i),\ i\in\llbracket 1,\,n\rrbracket \) d'une permutation \(\sigma\) de votre choix dans l'ordre crois­sant des valeurs de \(i\) en les séparant par un espace puis en validant. La signature, l'ordre et le type de la permutation \(\sigma\) sont étudiés un peu plus bas mais sont affichés ici pour regrouper toutes les informations sur \(\sigma\).

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.

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 appliquant le lemme ci-dessus pour un cycle quelconque, on obtient la décomposition en produit de transpositions suivante :

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 encore y arriver si ces deux livres sont toujours côte à côte.

Permutations et tris

Pour écrire un algorithme basé sur des comparaisons entre éléments de \(X\), on peut toujours supposer que \(X=\ab{1}{n}\) et qu'il est muni de l'ordre naturel \(\leq\). En effet, l'ordre sur \(X\) étant total, on peut toujours numéroter les \(n\) éléments \(x_1,x_2,\ldots,x_n\) de la liste \(L\) de sorte que \[ \forall (i,j)\in\ab{1}{n}^2 \quad (i \leq j)\ \then\ (x_i \preceq x_j). \] ce qui définit un mor­phis­me d'ensembles ordonnés entre \((\ab{1}{n} ,\leq)\) et \((L(\ab{1}{n}),\preceq)\) où \(L(\ab{1}{n})\) est l'ensemble des valeurs de la liste \(L\) (l'image de l'application \(L\)). En triant les valeurs entières, on trie donc les éléments de la liste.

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

où \(L[i]\) désigne la \(i\)-ème valeur dans la liste. Pour trier \(L\), on dispose d'une opération notée \(i\overset{L}{\rightleftharpoons} j\) qui échange le contenu des cellules d'indices \(i\) et \(j\) de la liste \(L\). 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

On connaît évidemment le résultat des courses puisque la liste triée est la liste \([1,2,\ldots,n]\), c'est-à-dire la permutation identité. Mais ce n'est pas tant le résultat du tri qui nous motive que la manière de le réaliser. L'échange \(i\overset{L}{\rightleftharpoons} j\) définit implicitement la transposition \((L[i],L[j])\) et un algorithme de tri comparatif opère en une suite finie d'échanges. Notons \((\tau_k)_{k\in\ab{1}{t}}\) les \(t\) échanges réalisés pour trier la liste \(L\). On vient de mon­trer que \begin{align*} \tau_t\,\tau_{t-1}\,\ldots\,\tau_2\,\tau_1\, L &= {\Id},\\ L &= {\Id}\,(\tau_t\,\tau_{t-1}\,\ldots\,\tau_2\,\tau_1)^{-1},\\ L &= \tau_1\,\tau_2\,\ldots\,\tau_{t-1}\,\tau_t \quad\text{car}\ (s\,t)^{-1}=t^{-1}\,s^{-1}\ \text{et}\ \tau_i=\tau_i^{-1}. \end{align*} Et nous venons donc de décomposer la permutation \(L\) en produit de transpositions. Chaque algo­ri­thme de tri comparatif in situ*(^*) qui échan­ge les va­leurs dans la liste est donc une preuve constructive que toute permutation se dé­com­po­se en produit de transpositions. Et on comprend mieux à présent pourquoi la décomposition d'une permutation en produit de transpositions n'a rien d'uni­que vu la diversité des algorithmes de tris com­pa­ra­tifs.

L'algorithme du tri par propagation également appelé tri à bulles, réalise le tri d'une liste uniquement avec des échanges du type \(i\rightleftharpoons i+1\). Le principe est simple, pour toutes les valeurs \(k\) allant de \(n\) à \(2\), on balaie la liste \(L\) de \(i\leftarrow 1\) à \(k\) en faisant l'échange \(i\rightleftharpoons i+1\) si \(L[i+1] \preceq L[i]\).

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 et/ou d'échanges entre éléments de la liste.

Signature

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

La permutation identité génère \(n\) orbites puisque tous les points sont fixes, donc \(\epsilon({\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}\).

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.

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.

Il faut donc déduire de ce corollaire que la signature d'un produit (au sens de la composition des applications) de permutations est le produit (au sens des nombres entiers) de leurs signatures.

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

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

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.

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

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

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 :

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 sui­van­tes :

Le type vide est celui de la permutation identité.

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}

Ces résultats seront 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.

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 :

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)\) mais cette condition n'est pas suffisante. Pour qu'une transposition \((k,16)\) soit possible, il faut également que les pièces \(k\) et \(16\) soient ad­ja­cen­tes, c'est-à-dire 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\ab{1}{n} \), \(\tau_i\) est compatible avec le produit \[\tau_{i-1}\tau_{i-2}\ldots\tau_{1}\sigma.\] Ce qui signifie ni plus ni moins qu'en partant de la configuration \(\sigma\), les transpositions \(\tau_1\) puis \(\tau_2\), etc. sont possibles dans cet ordre.

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{#FF8}\tau_i})_{i\in\ab{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 :

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{#FF8}\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\) :

Ces deux dernières é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 per­mu­ta­tions (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{#FF8}\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 :

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{#FF8}\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 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é.

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

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\llbracket 1,\,k\rrbracket }\) 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\) :

Dorénavant nous noterons \(\def\tua{{\color{#F44}\tau}}\tua_i:=(16,i)\), \(i\in\ab{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\ab{1}{k}}\) respectivement, on a donc \[\forall i\in\ab{1}{k}\quad \sigma(c_i)=p_i.\]

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 :

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) :

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:={\Id}\), on obtient le \(3\)-cycle \((11,12,15)\) à l'aide des quatre transpositions : \[\tua_{15}\,\tua_{12}\,\tua_{11}\,\tua_{15}.\]

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.

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 :

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 ?

Travaux pratiques

En séance

Dans toute la suite, une permutation \(\sigma\) de \({S}_n\) est codée par le \(n\)-uplet \((\sigma(1),\sigma(2),\ldots,\sigma(n))\) sous forme de tuple Python. Comme les indices des types énumérés commencent à 0 et pas à 1 on décrémentera la valeur des images. Autrement dit la permutation \begin{pmatrix} 1&2&3&4\\ \color{#FF8}3&\color{#FF8}2&\color{#FF8}1&\color{#FF8}4 \end{pmatrix} sera codée par le tuple (2,1,0,3). La saisie d'une permutation et son affichage resteront en revanche conformes aux notations mathématiques usuelles. Ainsi, pour lire et afficher une permutation, vous utiliserez la fonction et la procédure suivantes, la première renvoie un tuple de valeurs entières à partir de la chaîne de caractère correspondante lue au clavier :

def Lire():
   chaine = input("Permutation = ")
   return tuple([int(x)-1 for x in chaine.split()])

def Ecrire(s):
   for i in s:
      print(i + 1,end='')
   print()

Compléments hors séance

Après avoir étudié le chapitre sur l'arithmétique, démontrez que le plus petit commun multiple des deux entiers naturels \(a\) et \(b\) (noté \([a,b]\)) est égal au quotient

où \((a,b)\) désigne le pgcd de \(a\) et \(b\). Soit \(n\) un entier \(n\geq 3\). Démontrez par récurrence que pour une séquence d'entiers naturels \(a_1,a_2,\ldots, a_n\) on a