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}.
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres