Cycles et nombres de Stirling

Notations et définitions

Dans tout le problème, {n\geq2} est un entier naturel et {E_n=\{1,2,\ldots,n\}}. On note {\mathcal B_n} l’ensemble des bijections de {E_n} sur lui-même.

Une bijection {f} est représentée par le tableau :
{\begin{pmatrix}1&2&\cdots&n-1&n\\[4pt]f(1)&f(2)&\cdots&f(n-1)&f(n)\end{pmatrix}}Les entiers de {1} à {n} figurent chacun une fois sur la deuxième ligne. Par exemple, {\begin{pmatrix}1&2&3&4&5\\[4pt]3&4&5&2&1\end{pmatrix}} signifie {f(1)=3}, {f(2)=4}, {f(3)=5}, {f(4)=2} et {f(5)=1}.

On définit {f^0=\operatorname{Id}}, {f^{k+1}=f\circ f^k} pour {k\in\mathbb N}, puis {f^{-p}=(f^{-1})^p=(f^p)^{-1}} pour {p\geq1}. Ainsi {f^{-3}} est à la fois l’inverse de {f^3} et la troisième puissance de {f^{-1}}.

On admet les égalités {f^m\circ f^p=f^p\circ f^m=f^{m+p}} pour tous {m,p\in\mathbb Z}.

Une application {f:E_n\to E_n} est un cycle s’il existe {2\leq p\leq n} et un arrangement {(a_0,\ldots,a_{p-1})} d’éléments distincts tels que {f(a_0)=a_1,\ldots,f(a_{p-2})=a_{p-1}}, {f(a_{p-1})=a_0}, et {f(x)=x} hors de {S_f=\{a_0,\ldots,a_{p-1}\}}.

On écrit alors {f=(a_0,\ldots,a_{p-1})} ; {p} est sa longueur et {S_f} son support. L’ordre n’importe pas dans l’ensemble {S_f}, mais il importe dans l’écriture du cycle.

Les indices peuvent être lus modulo {p}, avec {a_p=a_0} : on a alors {f(a_k)=a_{k+1}}. Les écritures obtenues par rotation des indices représentent le même cycle, par exemple {(a_1,\ldots,a_{p-1},a_0)}.

La restriction de {f} à {S_f} est une bijection de cet ensemble. Aucun élément du support n’est fixe ; tous ceux de son complémentaire sont fixes. On ne demande pas de justifier ces observations.

I. Généralités sur les cycles de {\{1,2,\ldots,n\}}

Dans la question 1 uniquement, {n=9}.

1. (a) Montrer que {f=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\[4pt]8&7&3&4&1&6&5&2&9\end{pmatrix}}est un cycle de {E_9}, dont on précisera la longueur et le support, et qu’on écrira sous forme cyclique.

1. (b) Préciser {f^{-1},f^2,f^3,f^4,f^5,f^6,f^{2005}}. Pour chacune, indiquer s’il s’agit d’un cycle, et sa longueur et son support éventuels.

1. (c) Reprendre les deux questions précédentes avec {f=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\[4pt]7&2&9&6&5&1&3&8&4\end{pmatrix}}

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