
\documentclass[11pt]{amsart}
\mathsurround=0.5 pt
\pagestyle{plain}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\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
 
 
\setlength{\topmargin}{0cm}
\setlength{\textheight}{23.6cm}
\setlength{\oddsidemargin}{1cm}
\setlength{\evensidemargin}{1cm}
\setlength{\textwidth}{15cm}
 
 
 
\parindent=0.5cm
                                                             
%\title{Pr{\'e}paration au CAPES de math{\'e}matiques.}
 
%\author{Test d'Alg{\`e}bre du mercredi 18 oct 2006}

%\address{E.F.~: Institut Fourier, BP 74, 38402 St Martin d'H{\`e}res Cedex, France.}                           
                          
 
%\email{emmanuel.ferrand@ujf-grenoble.fr}
\parindent=0cm
%\subjclass{53D10}
%\keywords{contact topology, Morse theory}
%\date{First version}
 
\begin{document}

%\maketitle

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

\centerline{\bf TD d'Alg{\`e}bre du mercredi 18 octobre 2006}

\bigskip


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

\section{} Montrer que tout groupe fini est isomorphe {\`a} un sous-groupe
d'un groupe de permutations.

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

\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 $G$
qui laissent $x$ invariant. 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{Formule de Cauchy} On veut 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
Autrement dit: $$|\frac{X}{G}|=\frac{1}{G}\sum_{g \in G} |X^g|.$$

\subsubsection{} Montrer que la formule de Lagrange est un cas
particulier de cette relation.

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

\subsubsection{} Montrer la formule de Cauchy.

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

\subsubsection{} D{\'e}terminer le nombre de colliers de perles distincts,
ayant $6$ perles, chaque perle ayant $3$ couleurs possibles.


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

\section{Encore des 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 $C_n$, le groupe
 groupe cyclique {\`a} $n$ {\'e}l{\'e}ments, agissant par permutations circulaires
 sur les mots {\`a} $n$ lettres. Notons $a(n,k)$ le nombre de ces orbites.

\medskip

\subsection{} Soit $g \in C_n$ le d{\'e}calage circulaire de 1 cran vers
la droite, de sorte que $C_n=\{e,g,g^2,\dots,g^{n-1}\}$.  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$. D{\'e}terminer le nombre de cycles
dans la d{\'e}composition en cycles de la permutation $g^i$.

\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}((p-1)k+k^p)$.

\subsection{} Pour tout entier $m$, notons $\phi(m)$ le nombre
d'entiers compris entre 1 et $m$ et premiers {\`a} $m$.
Calculer $\phi(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 $C_n$
est {\'e}gal {\`a} $\phi(d)$

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


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

\subsection{Th{\'e}or{\`e}me de Polya} 
On conserve les notations de l'exercice pr{\'e}c{\'e}dent.
A toute permutation $g$, on associe $c_i(g)$, le nombre 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 $|A|=n$. Consid{\'e}rons
$$Z_G(X_1,\dots,X_n)=\frac{1}{|G|} \sum_{g \in
  G}X_1^{c_1(g)}X_2^{c_2(g)} \dots X_n^{c_n(g)}.$$

\medskip

Soit $B$ un ensemble fini. Monter que $G$ agit naturellement sur
l'ensemble des fonctions de $A$ dans $B$, et montrer que le nombre
d'orbites de cette action est $Z_G(|B|,|B|,\dots,|B|)$.
 


 
 
 


\end{document}