\input{../.headers/cours.tex}
\renewcommand{\epsilon}{\eps}

\baselineskip15pt

\begin{center}
\shadowbox{\LARGE \bf
\begin{tabular}{c}
\textsc{\semisupline Groupe sym\'etrique.\subline}
\end{tabular}}
\end{center}

\section*{Motivation}

\underline{Rappel}~:\\\\[0.2cm]
$\dect{cc}{a_{1,1}&a_{1,2}\\a_{2,1}&a_{2,2}} = \underbrace{a_{1, 1}a_{2,2} }_{\id} - \underbrace{a_{2,1}a_{1,2} }_{\tau_{1,2}} $\\\\\\
$\dect{ccc}{a_{1,1}&a_{1,2}&a_{1,3}\\a_{2,1}&a_{2,2}&a_{2,3}\\a_{3,1}&a_{3,2}&a_{3,3}} = \underbrace{a_{11} a_{22} a_{33}}_{\id} + \underbrace{a_{21} a_{32} a_{13} }_{c} + \underbrace{a_{31} a_{12} a_{23}}_{c^{-1}} - \underbrace{a_{21} a_{12} a_{33} }_{\tau_{1,2}} - \underbrace{a_{31}a_{22}a_{13}}_{\tau_{1,3}} - \underbrace{a_{11} a_{32} a_{23}}_{\tau_{2,3}} $\\\\

On verra dans le prochain chapitre~:~$\dect{ccc}{a_{1,1}&\ldots&a_{1,n}\\\vdots&&\vdots\\a_{n,1}&\ldots&a_{n,n}}~~= \sum_{\sigma \in S_n} \epsilon(\sigma) a_{\sigma(1), 1}\cdots a_{\sigma(n),n}  $\\\\

\underline{\textbf{Objectif principal}} de ce chapitre~: comprendre ce qu'est $\eps$.

\medskip


%\section{Pr\'eliminaires sur les groupes}
%
%\ \\[-1cm]
%
%\subsection{Ordre d'un \'el\'ement}
%
%\ \\[-1cm]
%
%\dfn
%Soit $(G,*)$ un groupe et $g\in G$.\\[0.2cm]
%On appelle \newdef{ordre de $g$} le plus petit entier $p$ strictement positif, {\bf s'il existe}, tel que $g^p=\underbrace{g*g*\cdots*g}_{\mathversion{normal} p \; \text{fois}}=e$.
%\nfd
%
%\rmq
%Si la loi est not\'ee $+$, l'\'egalit\'e s'\'ecrit $p.g = 0$.
%\qmr
%
%\exs
%\begin{enumerate}
%\item L'ordre de $-1$ dans $(\R^\times,\times)$ est ...... En effet~:\\
%\uneligne\\
%\uneligne\\
%\item L'ordre de $\matdd{0}{-1}{1}{0}$ dans $(GL_2(\K),\times)$ est ...... En effet~:\\
%\quatrelignes
%\end{enumerate}
%\sxe

%%%\ \\
%%%
%%%\underline{Exercice~:} d\'eterminer l'ordre de tous les \'el\'ements de $\U_6=\{1,-\overline{j},j,-1,\overline{j},-j\}$.\\
%%%\quatrelignes\\
%%%\uneligne\\
%%%\uneligne\\\\
%%%
%%%\attention{L'existence n'est pas assur\'ee~!}
%%%
%%%\ \\\\
%%%
%%%\exs
%%%\begin{enumerate}
%%%\item Dans $(\R^\times,\times)$, $-2$ n'a pas d'ordre. En effet~:\\
%%%\uneligne
%%%\item Dans $(GL_2(\K),\times)$, $\matdd{1}{2}{3}{4}$ n'a pas d'ordre. En effet~:\\
%%%\quatrelignes
%%%\end{enumerate}
%%%\sxe
%%%
%%%\ \\[-1cm]

%\subsection{Sous-groupes engendr\'es}
%
%\ \\[-1cm]
%
%\dfn
%Soit $(G,*)$ un groupe et $P\subset G$.\\[0.2cm]
%Pour $H\subset G$, les propositions suivantes sont \'equivalentes~:\\
%\begin{enumerate}[i.]
%\item $H$ est le plus petit sous-groupe de $G$ contenant $P$~;\\
%\item \unepetiteligne\\
%\item \unepetiteligne\\
%\end{enumerate}
%On dit alors que $H$ est le \newdef{sous-groupe engendr\'e par $G$}.
%\nfd
%
%
%\exs
%\begin{enumerate}
%\item Pour $(G,*)=(\R^\times,\times)$.
%\begin{itemize}
%\item Le sous-groupe engendr\'e par $\{2\}$ est ..............................................
%\item Le sous-groupe engendr\'e par $\{2,3\}$ est ................................................. 
%\end{itemize}
%\item Pour $(G,*)=(\Z,+)$.
%\begin{itemize}
%\item Le sous-groupe engendr\'e par $\{2\}$ est ..............................................
%\item Le sous-groupe engendr\'e par $\{2,3\}$ est ......................................................................\subline\\
%D'apr\`es le th\'eor\`eme de ............................
%\end{itemize}
%\end{enumerate}
%\sxe

%%%\ \\

%%%\underline{Exercice~:} d\'eterminer le sous-groupe engend\'e par $j$ dans $\U_6$.\\
%%%\uneligne\\
%%%\uneligne\\

%%%\rmq
%%%L'existence est assur\'ee (par la troisi\`eme caract\'erisation).
%%%\qmr

%\ \\[-1cm]

\section{Rappels sur $S_n$}

\medskip

%\ \\[-1.3cm]

\subsection{D\'efinition}

%\ \\[-1cm]

\underline{Rappel}~:
\begin{enumerate}
\item $S_n$ est l'ensemble des bijections de $\{1,2,\ldots,n\}$ dans $\{1,2,\ldots,n\}$.
\item $(S_n,\circ)$ forme un groupe.
\item $\left|S_n\right|=n!$.
\end{enumerate}

%\lilbound

\exs
\begin{enumerate}
\item Pour $n=0$, $S_0=\{\id\} $.
\item Pour $n=1$, $S_1=\{\id\} $.
\item Pour $n=2$, $S_2=\{\id, \tau_{12}\} $.
\item Pour $n=3$, $S_3=\{\id, c, c^{-1}, \tau_{12}, \tau_{13}, \tau_{23}\} $.
\end{enumerate}
\sxe

\exx Si $1\leq i\neq j\leq n$ on peut consid\'erer la permutation $\tau_{i,j} \in S_n$ suivante, appel\'ee \newdef{transposition}~:\break $\tau_{i,j} : \defapp{\{1,\ldots,n\}}{\{1,\ldots,n\}}{k}{\lect{j \text{ si }k=i\\i \text{ si }k=j\\k \text{ sinon}}}$.
\xxe

\underline{Notation~:}
Une permutation $\sigma$ de $S_n$ pourra \^etre not\'ee $\left(\begin{array}{cccc}1 & 2 & \cdots & n\\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{array}\right)$.\\

\ex
Pour $n=4$, la permuation $\tau_{1,2} \circ \tau_{3,4}$ peut s'\'ecrire~:
\begin{align*}
	\tau_{12}\circ \tau_{34} &= \begin{pmatrix} 1&2&3&4 \\ 2&1&4&3 \end{pmatrix}  \\
\end{align*}
\xe

\dfn
On appelle \newdef{support} d'une permutation $\sigma$ l'ensemble des \'el\'ements de $\{1,\hdots,n\}$ qui ne sont pas fix\'es par $\sigma$.\\[0.15cm]
(Le support est "l\`a o\`u il se passe quelque chose".)
\nfd

\ex
Supports de $\tau_{1,2}$, $\tau_{3,4}$ et $\tau_{1,2} \circ \tau_{3,4}$ dans $S_n$~?
\begin{description}
	\item[$\tau_{12}$] $\{1, 2\} $
	 \item[$\tau_{34}$] $\{3, 4\} $
	 \item[$\tau_{12}\circ\tau_{34}$] $\{1, 2, 3, 4\} $
\end{description}
\xe

\dfn
\'Etant donn\'e %une permutation
 $\sigma\in S_n$ on appelle \newdef{inversion} de $\sigma$ un couple $(i,j) \in \{1,2,\ldots,n\}$ tel que $i<j$ et $\sigma(i)>\sigma(j)$
\nfd

\exs
\begin{enumerate}
\item L'identit\'e a 0 inversion(s).
\item Dans $S_3$, la transposition $\tau_{1,2}$ a 1 inversion: $\{(1, 2)\} $.
\item Dans $S_3$, la transposition $\tau_{1,3}$ a 3 inversion(s): $\{(1, 3), (2, 3), (1, 2)\} $.
\item Dans $S_3$, le cycle $c = \permut{ccc}{1&2&3\\2&3&1}$ a $\{(1, 3), (2, 3)\} $ inversion(s).
\end{enumerate}
\sxe


\subsection{Repr\'esentation sch\'ematique}

On peut repr\'esenter une permutation par un graphe orient\'e dont les sommets sont les \'el\'ements de $\{1,2,\ldots,n\}$ et pour lequel il existe un arc de $i$ vers $j$ \ssi $\sigma(i)=j$.\\

\exs\ \\[-0.2cm]
Dans $S_3$ puis $S_6$
\begin{center}
\begin{tikzpicture}[scale=0.2]
\tikzstyle{every node}+=[inner sep=0pt]
\draw [black] (12.7,-25.9) circle (3);
\draw (12.7,-25.9) node {$1$};
\draw [black] (32.7,-26.3) circle (3);
\draw (32.7,-26.3) node {$2$};
\draw [black] (56.1,-25.9) circle (3);
\draw (56.1,-25.9) node {$3$};
\draw [black] (5.7,-47.2) circle (3);
\draw (5.7,-47.2) node {$1$};
\draw [black] (18.4,-46.5) circle (3);
\draw (18.4,-46.5) node {$2$};
\draw [black] (30.7,-47.4) circle (3);
\draw (30.7,-47.4) node {$3$};
\draw [black] (47.1,-47.4) circle (3);
\draw (47.1,-47.4) node {$4$};
\draw [black] (59.2,-46.5) circle (3);
\draw (59.2,-46.5) node {$5$};
\draw [black] (73.7,-47.4) circle (3);
\draw (73.7,-47.4) node {$6$};
\draw [black] (14.415,-23.449) arc (137.30547:40.403:11.139);
\fill [black] (31.08,-23.78) -- (30.95,-22.85) -- (30.19,-23.5);
\draw [black] (30.666,-28.495) arc (-49.88521:-132.40632:12.15);
\fill [black] (14.64,-28.17) -- (14.9,-29.08) -- (15.57,-28.35);
\draw [black] (55.329,-23.013) arc (222.69007:-65.30993:2.25);
\fill [black] (57.92,-23.53) -- (58.85,-23.36) -- (58.17,-22.62);
\draw [black] (44.918,-49.457) arc (-49.69633:-130.85725:28.483);
\fill [black] (7.86,-49.28) -- (8.14,-50.18) -- (8.79,-49.42);
\draw [black] (28.298,-49.193) arc (-57.84295:-123.07376:18.763);
\fill [black] (28.3,-49.19) -- (27.36,-49.2) -- (27.89,-50.04);
\draw [black] (21.147,-45.295) arc (112.32106:65.81414:63.137);
\fill [black] (21.15,-45.3) -- (22.08,-45.45) -- (21.7,-44.53);
\draw [black] (58.49,-43.597) arc (221.47119:-66.52881:2.25);
\fill [black] (61.07,-44.17) -- (62,-44.02) -- (61.34,-43.27);
\draw [black] (44.638,-49.102) arc (-62.30629:-117.69371:12.347);
\fill [black] (44.64,-49.1) -- (43.7,-49.03) -- (44.16,-49.92);
\end{tikzpicture}
\end{center}
\sxe

\ \\[-1cm]

\subsection{Transpositions}

\ \\[-1cm]

\underline{Rappel}~:%\\[-0.8cm]
\begin{enumerate}
\item Une \newdef{transposition} est une permutation de la forme $\tau_{i,j}$ (voir plus haut).% : \defapp{\{1,\ldots,n\}}{\{1,\ldots,n\}}{k}{\lect{j \text{ si }k=i\\i \text{ si }k=j\\k \text{ sinon}}}$.
\item $\tau_{i,j}^{-1}=\tau_{ij}$ \cad $\tau_{i,j}^2=\id$. On dit qu'une transposition est une permutation d'ordre $2$.\megasubline
\item $\tau_{j,i}=\tau_{i,j}$.
\end{enumerate}

\col[du troisi\`eme point]
\ \\Il y a $\begin{pmatrix} n\\2 \end{pmatrix} = \frac{n(n-1)}{2} $ transpositions.
\loc

\ \\[-0.4cm]

\subsection{Structure}

\ \\[-1cm]

\underline{Rappel}~: Pour $n\leq m$ toute permutation de $S_n$ peut \^etre vue comme une permutation de $S_m$\\
\textcolor{white}{\underline{Rappel}~:} (qui laisse fixe les \'el\'ements $\{n+1,\cdots,m\}$).

\thm[Rappel]
\ \\[-0.9cm]
\begin{enumerate}
\item $S_0\simeq S_1 \simeq \{e\}$ (le groupe trivial)
\item $S_2 \simeq \Z/2\Z$
\item pour $n\geq 3$, $S_n$ est non commutatif car $\tau_{12}\circ\tau_{23} = c^{-1} \neq c = \tau_{23}\circ\tau_{12}$
\end{enumerate}
\mht

Par commodit\'e, on parlera de \newdef{multiplication} et de \newdef{produit} pour la composition des permutations et la compos\'ee de permutations. On s'autorisera aussi \`a noter $\sigma \sigma'$ pour $\sigma \circ \sigma'$.\\

\rmq
Pour tout $\sigma\in S_n$, il existe un plus petit entier $p>0$ tel que $\sigma^p=\id$. Cet entier $p$ est appel\'e l'ordre de la permutation.
%On dit que toute permutation a un ordre.
\qmr

\demo 
Par l'absurde:

$\{\sigma, \sigma^2, \ldots, \sigma^i, \ldots, \sigma^{j}\}$ est fini donc il existe $i<j$ tel que $\sigma^i = \sigma^{j}$ d'où $\id = \sigma^{j-i}$
\cqfd

\ex
La permutation $c_1 = \left ( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1\end{array} \right )$ est d'ordre 3
En effet~: $c^2=c^{-1}; c ^3=\id$
\xe
%
%\demo
%\unepetiteligne
%\cqfd

%\ \\[-1cm]
\medskip

\section{Parit\'e d'une permutation}

%\ \\[-1.2cm]
\medskip

\subsection{D\'ecomposition en transpositions}

\ \\[-0.8cm]

\rmq
On peut d\'ecomposer $c_1 = \left ( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1\end{array} \right )$ en produit de transpositions~: $c_1=\tau_{2,3}\circ \tau_{1,3} = \tau_{1,2}\circ\tau_{2,3}$.
\qmr

\ \\[-0.2cm]

\ex %Autre exemple~:\\
Pour $n=2k$, la permutation $\sigma = \left ( \begin{array}{ccccccc} 1 & 2 & \cdots & k & k+1 & \cdots & n \\ n & n-1 & \cdots & k+1 & k & \cdots & 1\end{array} \right )$ peut se d\'ecomposer~:\\[0.66cm]
$\sigma = \bigcirc_{i=0}^k \tau_{i,i+1}$.
\xe

\ \\[-0.5cm]

Les optionnaires info connaissent bien le {\bf tri par s\'election} (et pour les autres, c'est au programme en seconde ann\'ee). Pour trier une liste Python $L$ de longueur $n$~:
\begin{enumerate}[$\bullet$]
\item On d\'etermine l'\'el\'ement maximal parmi L[0], ..., L[n-1]~;
\item On permute cet \'el\'ement avec L[n-1] (sauf si c'est L[n-1])~;
\item On recommence sur L[0], ..., L[n-2]~; etc.
\end{enumerate}
\`A la fin, on obtient une liste tri\'ee. Ceci peut se reformuler de la fa\c{c}on suivante sur les permutations~:

\thm
Toute permutation peut se d\'ecomposer comme produit de transpositions.\\[0.2cm]
On dit que les transpositions engendrent $S_n$.%, \cad que le sous-groupe engendr\'e par l'ensemble des transpositions est $S_n$.
\mht

\demo %\unepetiteligne\\
%\quatrelignes\\
%\quatrelignes\\
%\quatrelignes\\
%\uneligne
En notant $L_k$ la liste Python obtenue \`a l'issue de la $k^e$ it\'eration de boucle, un invariant de boucle est clairement "les \'el\'ements de $L_k$ sont les \'el\'ements de $L$ et $L_k[0], \cdots, L_k[n-k]\leq L_k[n-k+1]\leq\cdots\leq L_k[n]$".\\
Ceci montre que le tri par s\'election est correct. Par ailleurs il est clair qu'il termine (on imbrique simplement deux boucles for).\\
Le rapport~? En notant $\tau_{i_1,j_1}$, $\tau_{i_2,j_2}$, $\ldots$, $\tau_{i_k,j_k}$ les permutations effectu\'ees au cours de l'algorithme ($k\leq n-1$), on a $\id = {}_{..................................................}$ \textbf{et donc} $\sigma = {}_{...............................................}$.
\cqfd

%\ \\[-0.5cm]
%\newpage

\rmq
Cette d\'emonstration est constructive, elle donne un mode d'emploi pour trouver {\bf une} d\'ecomposition d'une permutation~!
\qmr

\ex
D\'ecomposons $\left ( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1\end{array} \right )$

\begin{align*}
	\sigma &= \begin{pmatrix} 1&2&3&4&5 \\ 4&3&2&5&1 \end{pmatrix}  \\
	\sigma\circ \tau_{45} &= \begin{pmatrix}1&2&3&4&5 \\ 4&3&2&1&5 \end{pmatrix}  \\
	\sigma\circ \tau_{45} \circ \tau_{14}&= \begin{pmatrix}1&2&3&4&5 \\  1&3&2&4&5 \end{pmatrix}  \\
	\sigma\circ \tau_{45} \circ \tau_{14}\circ\tau_{23} &= \begin{pmatrix}1&2&3&4&5 \\  1&2&3&4&5 \end{pmatrix} = \id  \\
\end{align*}
\xe

%\quatrelignes\\
%\quatrelignes\\
%\uneligne\\
%\uneligne\\
%\uneligne

\exo Pour les option info~: quel %(super int\'eressant)
 \'enonc\'e math\'ematique tirer de la terminaison et correction du tri \`a bulles~?\\
(%Pour l
Les autres~: vous le ferez quand m\^eme en TD, vous ne saurez simplement pas qu'il s'agit d'un corollaire du tri \`a bulles.)

\ \\[-0.8cm]


\subsection{Parit\'e d'une permutation}


\attention{La d\'ecomposition n'est jamais unique pour $n\geq 2$~! ~~~~~~~~~~~~~~~~~~~~~~~~~ Par contre~: il y en a au plus $n-1$}



\thm[(admis)]
La parit\'e du nombre de transpositions dans une d\'ecomposition est toujours la m\^eme.
\mht

Id\'ee d'une d\'emonstration possible~:
\begin{enumerate}
%\item On d\'efinit une \newdef{inversion} de $\sigma$ comme un couple $(i,j)$ tel que $i<j$ et $\sigma(i)>\sigma(j)$.
\item On montre que la parit\'e du nombre d'inversions change lorsqu'on compose une permutation par une transposition.
\item On d\'eduit facilement le r\'esultat par l'absurde.
\end{enumerate}

\ \\[-0.6cm]

\dfn
Une permutation est dite \newdef{paire} lorsqu'elle peut s'\'ecrire comme produit d'un nombre pair de transpositions. Elle est dite \newdef{impaire} sinon.
\nfd

\exs
\begin{enumerate}
\item La permutation $c_1 = \left ( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1\end{array} \right )$ est paire car il y a deux permutations
\item Une transposition $\tau_{i,j}$ est toujours impaire
\item L'identit\'e est toujours paire
\end{enumerate}
\sxe

\ \\[-0.6cm]

\dfn[signature]
Soit $\sigma \in S_n$. On appelle \newdef{signature} de $\sigma$ le nombre .
\begin{align*}
	\eps(\sigma) &= \lect{1 \text{ si }\sigma\text{ est paire}\\-1 \text{ si }\sigma\text{ est impaire}} \\ &= (-1)^{\text{nombre de permutations dans la décomposition}}
\end{align*}
\nfd

\ex
La signature de $\sigma = \left ( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\end{array} \right )$ est $\eps(\sigma)=(-1)^3=-1$
\xe


\section{Orbites. Cycles}

\medskip

\subsection{Orbites\subline}

\dfn
Soit $\sigma \in S_n$ et $k\in\{1,2,\cdots,n\}$.\\[0.1cm]
On appelle \newdef{orbite de $k$ sous $\sigma$} (ou simplement \newdef{orbite de $k$} lorsque le contexte le permet) l'ensemble\\[-0.25cm] $$O_\sigma(k) = \{k,\sigma(k),\cdots,\sigma^n(k),\cdots\}\subset\{1,2,\cdots,n\}$$
\nfd

\exs
\begin{enumerate}
\item Pour $\sigma = \left ( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\end{array} \right ) \in S_5$, les orbites sont~:
\begin{center}
\begin{tikzpicture}[scale=0.2]
\tikzstyle{every node}+=[inner sep=0pt]
\draw [black] (9.9,-16.2) circle (3);
\draw (9.9,-16.2) node {$1$};
\draw [black] (23.1,-16.2) circle (3);
\draw (23.1,-16.2) node {$2$};
\draw [black] (36.2,-16.2) circle (3);
\draw (36.2,-16.2) node {$3$};
\draw [black] (50,-16.2) circle (3);
\draw (50,-16.2) node {$4$};
\draw [black] (65.6,-16.2) circle (3);
\draw (65.6,-16.2) node {$5$};
\draw [black] (10.826,-13.374) arc (148.88298:31.11702:6.627);
\fill [black] (22.17,-13.37) -- (22.19,-12.43) -- (21.33,-12.95);
\draw [black] (24.529,-13.568) arc (145.60376:34.39624:14.568);
\fill [black] (48.57,-13.57) -- (48.53,-12.63) -- (47.71,-13.19);
\draw [black] (34.877,-13.52) arc (234:-54:2.25);
\fill [black] (37.52,-13.52) -- (38.4,-13.17) -- (37.59,-12.58);
\draw [black] (51.524,-13.635) arc (138.94971:41.05029:8.322);
\fill [black] (64.08,-13.63) -- (63.93,-12.7) -- (63.17,-13.36);
\draw [black] (63.043,-17.767) arc (-60.1858:-119.8142:50.871);
\fill [black] (12.46,-17.77) -- (12.9,-18.6) -- (13.4,-17.73);
\end{tikzpicture}
\end{center}
\begin{align*}
	O(1) = \{1, 2, 4, 5\} = O(2) = O(4) = O(5) \\
	O(3) = \{3\} 
\end{align*}
%\quatrelignes
\item Pour $\sigma = \left ( \begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 6 & 4 & 1 & 5 & 2 \end{array} \right ) \in S_6$, les orbites sont~:\\\\\\\\
\begin{align*}
	%TODO
\end{align*}
%\quatrelignes
\end{enumerate}
\sxe

\ \\[-0.7cm]

\rmq
On a d\'ej\`a vu que, d'apr\`es le principe des tiroirs, la suite $\left(\sigma^i(k)\right)_{i\in\N}$ est p\'eriodique. Toute orbite est donc de la forme $O_\sigma(k) = \{k,\sigma(k),\cdots,\sigma^{n_k}(k)\}$.
\qmr

\ \\[-0.7cm]

\thm
Les orbites sous $\sigma$ forment toujours une partition de $\{1,2,\cdots,n\}$.
\mht

\demo 
D'après la propriété fondamentale sur les relations d'équivalences, il suffit de montrer que la relation "être dans la même orbite que" est une relation d'équivalence.

Tout est évident.
\cqfd


\subsection{Cycles}

%\ \\[-0.7cm]

\ex
Dans $S_n$ avec $n\geq 3$, $c_1 = \left ( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1\end{array} \right )$ et $c_2 = c_1^2 = c_1^{-1} = \left ( \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2\end{array} \right )$ sont des $3$-cycles.
\xe

%\ \\[-0.4cm]

\dfn\ \\[-0.9cm]
\begin{enumerate}
\item Une permuation $\sigma$ est appel\'ee un cycle lorsqu'elle a exactement une orbite non r\'eduite \`a un \'el\'ement.
\item Un $p$-cycle est un cycle d'ordre $p$.
\end{enumerate}
\nfd

%\ \\[-0.4cm]

\ex
Illustrons l'exemple pr\'ec\'edent dans les cas $n=3$ et $n=5$.\\[0.1cm]
\begin{enumerate}
\item Dans $S_3$~: une seule orbite $\{1, 2, 3\} $
\item Dans $S_5$~: trois orbites $\{1, 2, 3\} $, $\{4\} $ et $\{5\} $ mais une seule non réduite à un seul élément.
\end{enumerate}
On a bien une seule orbite {\bf non r\'eduite \`a un seul \'el\'ement}.
\xe

%\ \\

\ex
Dans $S_4$, $\tau_{1,2}\circ\tau_{3,4}$ n'est pas un cycle.

Il y a deux orbites: $\{1, 2\} $ et $\{3, 4\} $
\xe

%\ \\[-2cm]

\attention{$\id$ n'est pas un cycle car il y deux orbites non-réduites a un élément }\\

\rmq
Le support d'un cycle (rappel : "l\`a o\`u il se passe quelque chose") est donc son unique orbite non r\'eduite \`a un \'el\'ement.
\qmr

\pro
Le support d'un $p$-cycle est de cardinal $p$.
\orp

\thm
La signature d'un $p$-cycle est $(-1)^{p-1}$.
\mht

\demo
$(i_1 i_2 i_3 \ldots i_p) := 
\begin{pmatrix} \ldots& i_1 \ldots& i_2 \ldots& i_{p-1} \ldots& i_p \ldots& \\ \ldots& i_2 \ldots& i_3 \ldots& i_p \ldots& i_1 \ldots& \end{pmatrix} $

$\tau_{ij} = (ij)$

\begin{align*}
	(i_1 i_2\ldots i_p) &= \tau_{p-1, p} \circ \cdots \circ \tau_{i_2 i_p} \circ \tau_{i_1 i_p} \\
\end{align*}
\cqfd

%\ \\[-0.8cm]

\subsection{D\'ecomposition en cycles}

%\ \\[-0.8cm]

\rmq
Deux cycles \`a supports disjoints commutent.
\qmr

%\ \\[-0.5cm]

\thm
Toute permutation peut s'\'ecrire comme produit de cycles \`a support disjoints, et cette d\'ecomposition est unique \`a l'ordre des facteurs pr\`es.
\mht

\demo
C'est une reformulation du fait que les orbites forment une partiton de $\{1, \ldots, n\} $ 
\cqfd

%\newpage

\exs
\begin{enumerate}
\begin{center}
\begin{tikzpicture}[scale=0.2]
\tikzstyle{every node}+=[inner sep=0pt]
\draw [black] (6.6,-8.6) circle (3);
\draw (6.6,-8.6) node {$1$};
\draw [black] (15.4,-14.7) circle (3);
\draw (15.4,-14.7) node {$2$};
\draw [black] (23.4,-20.7) circle (3);
\draw (23.4,-20.7) node {$3$};
\draw [black] (30.2,-25.2) circle (3);
\draw (30.2,-25.2) node {$4$};
\draw [black] (38.5,-28.9) circle (3);
\draw (38.5,-28.9) node {$5$};
\draw [black] (46.2,-32.8) circle (3);
\draw (46.2,-32.8) node {$6$};
\draw [black] (56.5,-37.7) circle (3);
\draw (56.5,-37.7) node {$7$};
\draw [black] (62.5,-42) circle (3);
\draw (62.5,-42) node {$8$};
\draw [black] (69.5,-47.1) circle (3);
\draw (69.5,-47.1) node {$9$};
\draw [black] (76.3,-55) circle (3);
\draw (76.3,-55) node {$10$};
\draw [black] (22.077,-18.02) arc (234:-54:2.25);
\fill [black] (24.72,-18.02) -- (25.6,-17.67) -- (24.79,-17.08);
\draw [black] (9.539,-8.154) arc (85.19762:25.34439:6.399);
\fill [black] (14.79,-11.79) -- (14.9,-10.85) -- (13.99,-11.28);
\draw [black] (17.625,-12.708) arc (122.38089:-13.0892:9.089);
\fill [black] (31.35,-22.44) -- (32.01,-21.78) -- (31.04,-21.55);
\draw [black] (27.511,-26.52) arc (-69.32783:-180.9165:15.703);
\fill [black] (6.27,-11.58) -- (5.75,-12.37) -- (6.75,-12.38);
\draw [black] (41.248,-27.703) arc (109.48748:9.6784:21.191);
\fill [black] (69.21,-44.12) -- (69.56,-43.24) -- (68.58,-43.41);
\draw [black] (54.447,-39.84) arc (-58.85766:-172.02584:5.713);
\fill [black] (54.45,-39.84) -- (53.5,-39.83) -- (54.02,-40.68);
\draw [black] (48.701,-31.2) arc (108.24808:20.86842:5.982);
\fill [black] (48.7,-31.2) -- (49.62,-31.42) -- (49.3,-30.47);
\draw [black] (73.397,-55.715) arc (-84.40694:-182.17343:10.429);
\fill [black] (73.4,-55.71) -- (72.55,-55.3) -- (72.65,-56.29);
\end{tikzpicture}
$\sigma = (1\ 2\ 4) \circ (5\ 9) \circ (6\ 7) \circ (8\ 10)$
\\[2cm]
\end{center}
\item D\'ecomposons en cycles la permutation
	$\sigma_1=\permut{ccccccccc}{1&2&3&4&5&6&7&8&9\\4&7&2&5&1&8&9&3&6}=(1\ 4\ 5)\circ(2\ 7\ 9\ 6\ 8\ 3)$.

\item D\'ecomposons en cycles la permutation $\sigma_2=\permut{ccccccccc}{1&2&3&4&5&6&7&8&9\\5&1&4&3&2&9&7&6&8}=(1\ 5\ 2)\circ(3\ 4)\circ(6\ 9\ 8)$.

\end{enumerate}
\sxe

%\ \\[-0.8cm]
\subsection{Calcul de l'ordre d'une permutation}

%\ \\[-0.8cm]

\ex
Calculons l'ordre de $\sigma=\permut{ccccc}{1&2&3&4&5\\2&4&5&1&3}$.
\paragraph{On décompose en produit de cycles}

\begin{align*}
	\sigma &= (1\ 2\ 4) \circ (3\ 5) \\
\end{align*}

\begin{table}[h]
	\centering
	\caption{Autocompositions de $\sigma$}
	\begin{tabular}{c|c}
		$\sigma$ & $(1\ 2\ 4)\circ(3\ 5)$ \\
		$\sigma^2$ & $(1\ 4\ 2)\circ \id = (1\ 4\ 2)$ \\
		$\sigma^3$ & $\id \circ (3\ 5)$ \\
		$\sigma^4$ & $(1\ 2\ 4)\circ\id=(1\ 2\ 4)$ \\ 
		$\sigma^5$ & $(1\ 2\ 4)\circ(3\ 5)$\\
		$\sigma^6$ & $\id\circ\id=\id$\\
	\end{tabular}
\end{table}

\xe

\ \\[-0.4cm]

\pro
Si $c_1$ et $c_2$ sont deux cycles \`a supports disjoints, alors l'ordre de $c_1 \circ c_2$ est le PPCM des ordres
\orp


%\ \\[-0.4cm]

\underline{\textbf{M\'ethode g\'en\'erale pour le calcul d'un ordre}}~:
\begin{enumerate}
\item D\'ecomposer $\sigma$ en produit de cycles \`a support disjoints.
\item D\'eterminer l'ordre de chaque cycle \`a l'aide du support.
\item Utiliser la proposition pr\'ec\'edente.
\end{enumerate}

%\ \\[-0.8cm]

\section{Compl\'ements sur la signature}

%\ \\[-1.2cm]

\subsection{Calcul pratique d'une signature}

%\ \\[-0.8cm]

\thm
$\eps : \defapp{(S_n,\circ)}{(\{\pm1\},\times)}{\sigma}{\eps(\sigma)}$ est un morphisme de groupe.
\mht

Rappel~: cela signifie
%\uneligne\\
%\uneligne\\
%\uneligne

\demo
\begin{align*}
	\text{pair}+\text{pair} &= \text{impair}+\text{impair}&= \text{pair} \\
	\text{pair}+\text{impair}&= \text{impair}+\text{pair}&= \text{pair} \\
\end{align*}
\cqfd

\underline{\textbf{M\'ethode pratique pour calculer la signature d'une permutation $\sigma$}}~:
\begin{enumerate}
\item On d\'ecompose $\sigma$ en produit de cycles disjoints.
\item On utilise que $\eps$ est un morphisme de groupe.
\item On utilise le r\'esultat sur la signature d'un $p$-cycle.
\end{enumerate}

%\ \\[-0.8cm]

\exs %\textcolor{white}{.}~~~~~~~~~~~~~~~~~
~~~~Reprenons les exemples pr\'ec\'edents~:\\
\begin{enumerate}
	\item $\sigma_1=\permut{ccccccccc}{1&2&3&4&5&6&7&8&9\\4&7&2&5&1&8&9&3&6}$
		\begin{align*}
			\epsilon(\sigma) &= \epsilon((1\ 5\ 2)) \epsilon((3\ 4)) \epsilon((6\ 9\ 8)) \\
			&= 1  \cdot -1 \cdot 1 \\
			&= -1 \\
		\end{align*}
\item $\sigma_2=\permut{ccccccccc}{1&2&3&4&5&6&7&8&9\\5&1&4&3&2&9&7&6&8}$\\
	\begin{align*}
		\epsilon(\sigma) &= \epsilon((1\ 4\ 5)) \cdot \epsilon((2\ 7\ 9\ 8\ 6\ 3)) \\
		&= 1 \cdot -1 \\
		&= -1 \\
	\end{align*}
\end{enumerate}
\sxe

%\ \\[-0.4cm]

\rmq
%Il existe 
On a exactement deux morphismes de groupe %de $(S_n,\circ)$ dans $(\{\pm1\},\times)$~:
 $(S_n,\circ)\too(\{\pm1\},\times)$~: la signature et le \newdef{morphisme trivial} $1 : \defapp{S_n}{\{\pm1\}}{\sigma}{1.}$
\qmr

\demo Exercice du TD~! \cqfd

%\ \\[-0.8cm]

\subsection{Expressions \'equivalentes}

%\ \\[-0.8cm]

\pro
On dispose des trois caract\'erisations \'equivalentes suivantes de la signature~:
\begin{enumerate}
\item $\eps(\sigma)=(-1)^{\left|\big\{(i,j),~i<j\text{ et }\sigma(i)>\sigma(j)\big\}\right|}$.
\item $\eps(\sigma) = \dsp{\prod_{i<j} \dfrac{i-j}{\sigma(i)-\sigma(j)} = \prod_{i<j} \dfrac{\sigma(i)-\sigma(j)}{i-j}}$.
\item $\eps(\sigma) = (-1)^{n-m}$ o\`u $\lect{n\text{ est l'indice de }S_n\\m \text{ est le nombre d'orbites de }\sigma.}$
\end{enumerate}
\orp

\demo Exercice, pas facile. \cqfd
%\ \\[-0.3cm]

%\underline{Exercice}~: v\'erifier les trois points pour $\sigma=\tau_{1,2}$.

%\newpage
\subsection{Groupe altern\'e}

\prd
L'ensemble des permutations paires forment un sous-groupe de $S_n$.\\[0.15cm]
On l'appelle \newdef{groupe altern\'e} et on le note $\ac_n$ ou $\uc_n$.
\drp

\demo
$\uc_n = \Ker(\epsilon)$
\cqfd

\exs
\begin{enumerate}
\item Pour $n=0$ et $n=1$, on a $\uc_3 = \{\id, c, c^{-1}\} $
\item Pour $n=2$, on a ........................................................
\item Pour $n=3$, on a ........................................................
\end{enumerate}
\sxe

%\ \\[-0.4cm]

\ex
D\'ecrivons $S_4$ en d\'etails pour obtenir $\uc_4$.
\xe

\ \\\\\\\\\\\\\\\\\\\\\\\\\\\\

%\newpage

\thm
Pour $n\geq 2$, on a $\big|\uc_n\big|=\dfrac{n!}{2}$.
\mht

\demo\ \\\\\\
% \unepetiteligne\\
%\quatrelignes\\
%\uneligne
\cqfd


%\vfill
%\begin{center}
% \shadowbox{The End.}
%\end{center}



\end{document}
