Devoir à la maison : permutations

Contenu

Devoir à la maison : permutations#

Consignes#

Ce devoir est à rendre pour le jeudi 30 avril 2026, dernier délai, par email à julien.lavauzelle@univ-paris8.fr.
Vous devez rendre votre travail sous le format suivant :

un document au format .ipynb correspondant à cette page, que vous téléchargez puis remplissez ;
si vous en avez besoin, un autre document au format .pdf qui contient des réponses ou commentaires additionnels.

Sauf exception, le travail doit être effectué par groupe de deux. Vous devez m’envoyer votre composition de binôme par email avant le dimanche 19 avril, dernier délai.
Important : une fois votre travail rendu, chacun des membres du binôme doit être capable d’expliquer précisément chacune des lignes des réponses que vous avez rendues. Vous serez convoqué·es pour expliquer votre travail lors d’une séance le jeudi 07 mai 2026.

Partie A : représentations de permutations#

Soit \(n \ge 1\). Pour rappel, on appelle permutation de \(\{0, \dots, n-1\}\) une application bijective \(\sigma : \{0, \dots, n-1\} \to \{0, \dots, n-1\}\). On note \(S_n\) l’ensemble de ces permutations.

En informatique, une permutation \(\sigma \in S_n\) peut être représentée par la liste de ses images, c’est-à-dire par la liste \([\, \sigma(0), \sigma(1), \dots, \sigma(n-1)\, ]\). Mais toutes les listes de longueur \(n\) ne correspondent pas à une permutation ! En effet, une liste L de longueur \(n\) correspond à une permutation si et seulement si elle contient exactement une fois tous les entiers compris entre \(0\) et \(n-1\).

Question 1. Écrire une fonction est_une_permutation(L) qui prend en entrée une liste d’entiers L, et qui teste si cette liste représente une permutation au sens défini plus haut. La fonction retournera la valeur booléenne du test. Puis, afficher l’exécution de la fonction sur deux listes de longueur \(n = 6\) : l’une pour lequel la liste représente bien une permutation, l’autre non.

# Votre réponse ici

L’application identité, qui laisse invariant tous les éléménts de \(\{0, \dots, n-1 \}\), est une permutation. Elle est notée \({\rm id} \in S_n\).

Question 2. Écrire une fonction permutation_identite(n) qui retourne la permutation identité de \(S_n\). Puis, afficher la permuation identité de \(S_6\).

# Votre réponse ici

Toute permutation est inversible pour la composition : si \(\sigma \in S_n\), alors il existe \(\psi \in S_n\) telle que \(\sigma \circ \psi = \psi \circ \sigma = {\rm id}\). La permutation \(\psi\) est alors la seule à vérifier cette propriété, et elle est notée \(\sigma^{-1}\). On a ainsi :

\[ \forall (i,j) \in \{0, \dots, n-1\}, \sigma(i) = j \iff \sigma^{-1}(j) = i\,. \]

Question 3. Écrire une fonction inverse_permutation(L) qui prend en entrée une permutation représentée par une liste L, et qui retourne la liste correspondant à son inverse. Puis, afficher la permutation inverse de la permutation représentée par [0, 3, 2, 5, 1, 4], et vérifier à la main que l’on obtient bien le bon résultat.

# Votre réponse ici

L’ensemble des permutations de \(S_n\) est munie d’une loi de composition notée \(\circ\), et définie comme la composition des permutations. Autrement dit, pour tout \((\sigma, \phi) \in S_n^2\) et pour tout \(i \in \{0, \dots, n-1\}\), on a \((\sigma \circ \phi)(i) := \sigma(\phi(i))\). On parle aussi parfois du produit des permutations \(\sigma\) et \(\phi\), même si cette opération n’est pas commutative a priori.

Question 4. Écrire une fonction produit_permutation(L, M) qui prend en entrée deux permutations \(f\) et \(g\) représentées par deux listes L et M, et qui retourne la liste correspondant à leur composition \(f \circ g\). Puis, afficher le produit de la permutation de la question 3 et de son inverse, et vérifier que l’on obtient bien l’identité.

# Votre réponse ici

Question 5. Écrire une fonction permutation_aleatoire(n) qui prend en entrée un entier \(n\), et retourne une permutation de \(\{0, \dots, n-1\}\) tirée uniformément. Puis, tirer uniformément deux permutations aléatoires (pour \(n=10\)) et en faire le produit. Vérifier à la main le résultat.

# Votre réponse ici

Soit \(\sigma \in S_n\) une permutation. La matrice \(M := {\rm Mat}(\sigma)\) associée à \(\sigma\) est la matrice à coefficients dans \(\{0, 1\}\), de taille \(n \times n\), telle que pour tout \(v = (v_0, \dots, v_{n-1}) \in \mathbb{R}^n\), le vecteur \(u = M v\) a pour coordonnées

\[ u_i = v_{\sigma(i)}, \quad \forall i \in \{ 0, \dots, n-1 \} \]

Autrement dit, c’est la matrice \(M\) telle que pour tout \((i,j) \in \{0, \dots, n-1\}\), on a :

\[\begin{split} M_{i,j} = \left\{ \begin{array}{ll} 1 &\text{ si } i = \sigma(j)\\ 0 & \text{ sinon.} \end{array}\right. \end{split}\]

Question 6. Écrire une fonction matrice_permutation(L) qui prend en entrée une permutation de \(\{0, \dots, n-1\}\) représentée sous forme d’une liste L, et qui retourne la matrice qui la représente. Puis, construire une permutation de longueur \(6\), sa matrice de permutation \(M\), et le vecteur \({\bf v} = (1, 2, 3, 4, 5, 6)\), et vérifier que \(M {\bf v}\) est un bien le vecteur issu de \({\bf v}\) dont on a permuté les coordonnées.

# Votre réponse ici

Question 7. Vérifier que la représentation matricielle respecte bien le produit et l’inverse déjà implémentés. C’est-à-dire, vérifier que le produit de deux matrices de permutation est égal à la matrice de la composition de deux permutations, puis que l’inverse d’une matrice de permutation est bien la matrice de l’inverse de la permutation.

# Votre réponse ici

Question 8. Écrire une fonction permutation_par_matrice(M), qui est la fonction réciproque de matrice_permutation(L). C’est-à-dire, cette fonction doit prendre en entrée une matrice M (que l’on supposera correspondre à une permutation \(\sigma \in S_n\)), et retourner la représentain sous forme de liste L de la permutation \(\sigma\). Tester la fonction sur un exemple.

# Votre réponse ici

Partie B : propriétés et décompositions#

Soit \(\sigma \in S_n\). Une inversion pour \(\sigma\) est un couple \((i, j) \in \{0, \dots, n-1\}\), avec \(i < j\), tel que \(\sigma(i) > \sigma(j)\). La signature de \(\sigma\), souvent notée \(\varepsilon(\sigma)\), est égale \((-1)^k\) où \(k\) est le nombre d’inversions de \(\sigma\). Autrement dit, \(\varepsilon(\sigma) = 1\) si ce nombre est pair, et \(-1\) sinon.

Question 9. Écrire une fonction signature(L) qui calcule la signature d’une permutation représentée par une liste L, en comptant le nombre d’inversions. Tester la fonction sur L = [0, 2, 4, 3, 1] (de signature \(1\)), L = [1, 2, 3, 0] (de signature \(-1\)) et sur la permutation identité.

# Votre réponse ici

Question 10. Écrire une fonction signature2(L) qui calcule la valeur de

\[ \prod_{0 \le i < j \le n-1} \frac{\sigma(j)-\sigma(i)}{j-i} \]

pour la signature représentée par L. Puis, vérifier sur une centaine d’exemples tirés aléatoirement que la valeur obtenue est la même que celle de signature(L).

# Votre réponse ici

Question 11. Vérifier sur un exemple que la signature d’un produit de signature est le produit des signatures, et que la signature de l’inverse d’une permutation est égale à celle de la permutation.

# Votre réponse ici

Partie C : polynômes de Dickson#

Avec Sagemath, l’anneau \(\mathbb{Z}/n\mathbb{Z}\) des entiers réduits modulo \(n\) peut être construit via l’instruction Zmod(n).

Question 12. Pour l’entier \(n = 13\), construire l’anneau \(\mathbb{Z}/n\mathbb{Z}\), puis l’anneau des polynômes à une variable et à coefficients dans \(\mathbb{Z}/n\mathbb{Z}\). Enfin, construire la variable \(X\) correspondant à cet anneau de polynômes.

# Votre réponse ici

Les polynômes de Dickson sont des polynômes qui peuvent être définis sur \(\mathbb{Z}/n\mathbb{Z}\), avec \(n\) un nombre premier, et qui fournissent des permutations de \(\mathbb{Z}/n\mathbb{Z} \simeq \{0, \dots, n-1\}\). Ces polynômes sont paramétrés par un entier \(k \ge 0\) appelé ordre, et par un élément \(a \in \mathbb{Z}/n\mathbb{Z}\), et sont ainsi notés \(D_{k,a}(X)\). Il sont définis par récurrence, pour tout \(a \in \mathbb{Z}/n\mathbb{Z}\), par \(D_{0,a}(X) = 2\), \(D_{1,a}(X) = X\) et pour tout \(k \ge 0\) :

\[ D_{k+2,a}(X) = X D_{k+1,a}(X) - a D_{k,a}(X) \]

Question 13. Écrire une fonction dickson(k, a) qui, étant donné \(a \in \mathbb{Z}/n\mathbb{Z}\) et \(k \ge 0\), calcule le polynôme de Dickson \(D_{k,a}(X)\) suivant la relation de récurrence donnée plus haut. Puis, vérifier pour un \(a\) choisi arbitrairement que \(D_{2,a}(X) = X^2 -2a\), \(D_{5,a}(X) = X^5 - 5a X^3 + 5a^2 X\).

Indication : pour que votre implémentation s’exécute pour de grandes valeurs de \(k\), il es conseillé d’employer une méthode itérative plutôt que récursive.

# Votre réponse ici

On peut démontrer que la forme explicite d’un polynôme de Dickson est :

\[ D_{k,a}(X) = \sum_{i=0}^{\lceil k/2 \rceil} \frac{k}{k-i} \binom{k-i}{i} (-a)^i X^{k-2i} \]

Question 14. Écrire une fonction dickson_bis(n, a) qui, étant donné \(a \in \mathbb{Z}/n\mathbb{Z}\) et \(k \ge 0\), calcule le polynôme de Dickson \(D_k(X, a)\) suivant la formule explicite donnée plus haut. Vérifier également que \(D_{2,a}(X) = X^2 -2a\) et \(D_{5,a}(X) = X^5 - 5a X^3 + 5a^2 X\).

# Votre réponse ici

Question 15. Pour \(n=13\) et pour tout \(a \in \mathbb{Z}/n\mathbb{Z}\), vérifier que pour toutes les valeurs \(k\) allant de \(1\) à \(100\), les polynômes de Dickson vérifient les propriétés suivantes :

le degré de \(D_{k,a}(X)\) est \(k\)
\(D_{k,a}(X)\) satisfait l’équation différentielle :

\[ (X^2 - 4 a) D_{k,a}''(X) + X D_{k,a}'(X) - k^2 D_{k,a}(X) = 0 \]

si \(k = r s\) avec \(r \ge 1\) et \(s \ge 1\), alors

\[ D_{rs,a}(X) = D_{r,a^s}(D_{s,a}(X)) \]

# Votre réponse ici

Pour \(n\) un nombre premier, \(a \ne 0\) et \(k \ge 1\), on énonce la propriété suivante : « le polynôme de Dickson \(D_{k,a}(X)\) induit une permutation de \(\mathbb{Z}/n\mathbb{Z}\) si et seulement si \(k\) est premier avec \(n^2-1\) ».

Question 16. Pour \(n=13\) et par tests exhaustifs, vérifier que la propriété énoncée est vraie pour tous les entiers \(1 \le k \le 12\) et tous les \(a \in \mathbb{Z}/n\mathbb{Z}\) non nuls.

# Votre réponse ici