
\documentclass[12pt]{amsart}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\usepackage[frenchb]{babel}
\input{epsf}
 
\def \shar{{= \hskip-4mm / \hskip-1mm / \hskip-4mm =}}
 
\def \RM{\mathbb{R}}%        corps des reels
\def \NM{\mathbb{N}}%        entiers naturels
\def \ZM{\mathbb{Z}}%        entiers relatifs
\def \CM{\mathbb{C}}%        nombres complexes
\def \QM{\mathbb{Q}}%        nombres rationnels
\def \PM{\mathbb{P}}%        la droite projective
\def \UM{\mathbb{U}}%        groupe unitaire
 
 
\hoffset -1in
\advance\hoffset 3cm
\voffset -1in
\advance\voffset 3cm
\oddsidemargin 0pt
\evensidemargin 0pt
\topmargin -42pt
\headheight 28pt
\headsep 14pt
\textheight 23.7cm
\textwidth 15cm
\footskip 28pt
\paperheight 29.7cm
\paperwidth 21cm

\mathsurround 0pt
\parindent 0pt

\pagestyle{empty}
\thispagestyle{empty}

 
\begin{document}

\everymath={\displaystyle}

{\bf Pr{\'e}pa CAPES UPMC 2006} \hfill Emmanuel FERRAND, Laurent KOELBLEN.
\bigskip

\centerline{\bf TD d'Alg{\`e}bre du mercredi 17 octobre 2007}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{} Soit $X$ un ensemble fini, et $G$ un groupe fini agissant sur $X$. 
Pour tout $x \in X$ on note $Gx$ l'orbite de $x$ sous l'action de $G$,
$G_x$ le stabilisateur de $x$, et $X^g$ l'ensemble des {\'e}l{\'e}ments de $X$
qui sont laiss{\'e}s invariants par $g$. Le cardinal d'un ensemble $E$ est not{\'e}
$|E|$. L'ensemble des orbites de $G$ dans $X$ est not{\'e} $\frac{X}{G}$

\subsection{} Montrer que $|G/G_x|=|Gx|$.

\subsection{} Montrer que $\sum_{g \in G} |X^g|=\sum_{x \in X} |G_x|$.

\subsection{} Montrer que $\sum_{y \in G_x} \frac{1}{|Gy|} = 1$.

\subsection{Formule de Cauchy} Montrer que le nombre d'orbites de l'action de $G$ sur
$X$ est {\'e}gal {\`a} la moyenne pour $g \in G$ des cardinaux des ensembles
$X^g$.
Autrement dit: $$\left|\frac{X}{G}\right|=\frac{1}{|G|}\sum_{g \in G} |X^g|.$$

\subsection{} Déduire le th{\'e}or{\`e}me de Lagrange de cette relation.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Sym{\'e}tries et coloriages du cube.}

\subsection{} On consid{\`e}re les sous-groupe $H$ des isom{\'e}tries directes
de $\RM^3$ qui pr{\'e}servent le cube. 
D{\'e}terminer l'orbite d'un sommet, et le stabilisateur d'un
sommet. En d{\'e}duire le cardinal de $H$.

\subsection{} L'action de $H$ sur les grandes diagonales d{\'e}termine un
morphisme de $H$ vers $S_4$. D{\'e}terminer son noyau.

\subsection{} D{\'e}crire explicitement les {\'e}l{\'e}ments de $H$, et pour
chacun d'eux le nombre de cycles de la permutation induite sur
l'ensemble des faces.

\subsection{} D{\'e}terminer le nombre de coloriages des faces du  cube par trois
couleurs,  qui ne sont pas {\'e}quivalents {\`a} rotation pr{\`e}s.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Colliers.}
On appelle {\em collier} {\`a} $n$ perles et $k$ couleurs une classe
d'{\'e}quivalence de mots de longueur $n$ dans un alphabet {\`a} $k$ lettres,
deux mots {\'e}tant {\'e}quivalents si et seulement si on peut obtenir l'un de
l'autre par permutation circulaire.


Autrement dit, un collier est une orbite de l'action de $\ZM / n\ZM$, le groupe
 groupe cyclique {\`a} $n$ {\'e}l{\'e}ments, agissant par permutations
 circulaires sur l'ensemble $X=\{1,2,\dots,k\}^n$ des mots {\`a} $n$ lettres {\'e}crit dans un alphabet {\`a} $k$ lettres.
On identifie  $\ZM / n\ZM$ {\`a} $\{e,g,g^2,\dots,g^{n-1}\}$
o{\`u} $g$ est un g{\'e}n{\'e}rateur de  $\ZM / n\ZM$.
Pour $i \in \{0,\dots,n-1\}$, l'{\'e}l{\'e}ment $g^i$ du groupe agit par permutation circulaire de $i$ crans vers la droite. 
Notons $a(n,k)$ le nombre d'orbites de cette action.

\medskip
\subsection{} On consid{\`e}re le cas $n=6$. D{\'e}terminer le nombre de cycle
de chacune des $6$ permutations induites sur $X$. 
En d{\'e}duire le nombre $a(6,3)$ de colliers de $6$ perles {\`a} $3$ couleurs.

\subsection{} Pour tout $i \in \{0,\dots,n-1\}$, d{\'e}terminer l'ordre de $g^i$ en fonction du pgcd
de $i$ et de $n$. 

\subsection{} Soit $\sigma_i$ la permutation de $X$ induite par
$g^i$. Montrer que tous les cycles de $\sigma_i$ ont la m{\^e}me longueur. En
d{\'e}duire que le nombre de cycles de $\sigma_i$ est {\'e}gal {\`a} au pgcd de $i$ et de $n$.

\subsection{} Pour tout $i \in \{0,\dots,n-1\}$, d{\'e}terminer
$|X^{g^i}|$ puis $a(n,k)$.

\subsection{} Montrer que si $n=p$ est premier, alors
$a(p,k)=\frac{1}{p}\bigl((p-1)k+k^p\bigr)$. 

\subsection{} En d{\'e}duire le petit th{\'e}or{\`e}me de Fermat.

\subsection{} Pour tout entier $m$, on note $\varphi(m)$ le nombre
d'entiers compris entre 1 et $m$ et premiers {\`a} $m$.
Calculer $\varphi(x)$ pour $x=1,\dots,12$.

\subsection{} Soit $d$ un diviseur de $n$.
Montrer que le nombre d'{\'e}l{\'e}ments d'ordre $d$ dans $\ZM/n\ZM$
est {\'e}gal {\`a} $\varphi(d)$.

\subsection{} Montrer que $a(n,k)=\frac{1}{n}
\sum_{d|n}\varphi(d)k^{n/d}$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Th{\'e}or{\`e}me de Polya} 
A toute permutation $g$, on associe le nombre $c_i(g)$ de cycles de
longueur $i$ dans la d{\'e}composition de $g$.

\medskip

Soit $G$ un groupe fini agissant par permutation sur un ensemble fini
$A$ de cardinal $n$. On consid{\`e}re
$$Z_G(X_1,\dots,X_n)=\frac{1}{|G|} \sum_{g \in
  G}X_1^{c_1(g)}X_2^{c_2(g)} \ldots X_n^{c_n(g)}.$$

\medskip

Soit $B$ un ensemble fini. Montrer que $G$ agit naturellement sur
l'ensemble des fonctions de $A$ dans $B$, et que le nombre
d'orbites de cette action est $Z_G(|B|,|B|,\ldots,|B|)$.
 
\end{document}