Itérations dans un ensemble fini

Notations

Dans tout le problème, {n} désigne un entier naturel non nul. On note {E_n=\{1,2,\ldots,n\}} l’ensemble des {n} premiers entiers naturels non nuls. Dans certaines questions, on sera peut-être amené à donner une valeur particulière à {n}.

On note {\mathcal F_n} l’ensemble de toutes les applications de {E_n} dans lui-même. Pour désigner un élément {f} de {\mathcal F_n}, on utilisera le tableau :
{\begin{pmatrix}1&2&\cdots&n-1&n\\[4pt]f(1)&f(2)&\cdots&f(n-1)&f(n)\end{pmatrix}}Par exemple, {\begin{pmatrix}1&2&3&4&5\\[4pt]3&3&1&3&5\end{pmatrix}} désigne l’application de {E_5} dans lui-même définie par {f(1)=3}, {f(2)=3}, {f(3)=1}, {f(4)=3} et {f(5)=5}.

Pour tout {f\in \mathcal F_n}, on définit les puissances itérées par :
{f^0=\operatorname{Id},\quad f^{k+1}=f\circ f^k\quad(k\in\mathbb N)}Ainsi {f^1=f}, {f^2=f\circ f}, {f^3=f\circ f\circ f}, etc. Il est clair qu’avec cette définition :
{f^m\circ f^p=f^p\circ f^m=f^{m+p}\quad(m,p\in\mathbb N)}

Première partie : étude de trois exemples

Dans cette partie, et dans cette partie seulement, on fixe {n=10}. On définit les trois applications suivantes :

{f=\begin{pmatrix}1&2&3&4&5&6&7&8&9&10\\[4pt]3&10&7&6&4&4&9&8&3&7\end{pmatrix}}{g=\begin{pmatrix}1&2&3&4&5&6&7&8&9&10\\[4pt]5&10&6&4&8&3&9&3&2&6\end{pmatrix}}{h=\begin{pmatrix}1&2&3&4&5&6&7&8&9&10\\[4pt]5&10&4&7&9&6&3&2&1&8\end{pmatrix}}

1. Les applications {f,g,h} sont-elles bijectives ?
Dans l’affirmative, précisez leur bijection réciproque.

2. Calculer (directement sous la forme de tableaux {2\times10}, et sans justifications intermédiaires) les applications {f^k}, avec {2\leq k\leq8}. On constatera notamment que {f^8=f^2}.

3. Montrer que {f^{k+6}=f^k} pour tout entier {k\geq2} (autrement dit la suite des puissances itérées de {f} est périodique de période {6} à partir de {f^2}) et que l’ensemble {\{f^k:k\in\mathbb N\}} se réduit aux huit applications, toutes distinctes, {\{\operatorname{Id},f,f^2,f^3,f^4,f^5,f^6,f^7\}}.

On exprimera cette situation en disant que {f} est de délai {2} et de période {6}.

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :