Nombre d'inversions d'une permutation
Bonsoir
b) En déduire que si $(i_1, \cdots, i_l)$ est une famille d'éléments de $\{1,\cdots,n -1 \}$ alors $ inv \left( \displaystyle\prod_{j=1}^l (i_j \ i_{j+1} ) \right) \leq l$.
c) Soit $\sigma \ne id$. Montrer qu'il existe $i_1 \in \{1, \cdots, n-1 \}$ tel que $\sigma(i_1) > \sigma(i_1+1)$.
d) En déduire qu'il existe une famille $(i_1, \cdots, i_{inv \ \sigma})$ d'éléments de $\{1, \cdots, n-1 \}$ telle que : $\displaystyle\prod_{j=1}^{inv \ \sigma} (i_j \ i_{j+1} )= \sigma$.
e) Conclure.
Je bloque totalement à la première question et regarder le début du corrigé ne m'a pas aidé, je ne comprends pas l'idée.
Soit $n>1$ et $\sigma \in \mathfrak{S}_n$.
Le but de l'exercice est de montrer que le nombre d'inversions $inv(\sigma)$ est le nombre minimal $l(\sigma)$ de transpositions du type $(i \ i+1)$ utilisées pour écrire $\sigma$ comme produit de transpositions de ce type.
a) Soit $i \in \{1, \cdots, n-1 \}$. Montrer que : $inv( \sigma \circ (i \ i+1) )=\begin{cases} inv \ \sigma+1 \ \text{si} \ \sigma(i) < \sigma(i+1) \\ inv \ \sigma-1 \ \text{si} \ \sigma(i)> \sigma(i+1) \end{cases}$.Le but de l'exercice est de montrer que le nombre d'inversions $inv(\sigma)$ est le nombre minimal $l(\sigma)$ de transpositions du type $(i \ i+1)$ utilisées pour écrire $\sigma$ comme produit de transpositions de ce type.
b) En déduire que si $(i_1, \cdots, i_l)$ est une famille d'éléments de $\{1,\cdots,n -1 \}$ alors $ inv \left( \displaystyle\prod_{j=1}^l (i_j \ i_{j+1} ) \right) \leq l$.
c) Soit $\sigma \ne id$. Montrer qu'il existe $i_1 \in \{1, \cdots, n-1 \}$ tel que $\sigma(i_1) > \sigma(i_1+1)$.
d) En déduire qu'il existe une famille $(i_1, \cdots, i_{inv \ \sigma})$ d'éléments de $\{1, \cdots, n-1 \}$ telle que : $\displaystyle\prod_{j=1}^{inv \ \sigma} (i_j \ i_{j+1} )= \sigma$.
e) Conclure.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
1) c'est quoi $\mathfrak{S}_n$ ?
2) c'est quoi une inversion dans ce contexte ?
3) c'est quoi une transposition dans ce contexte ? C'est quoi une transposition du type $(i i+1)$ ? Et une transposition de type $(i i-1)$, ça existe ?
4) $\sigma$ peut être construit comme un produit de transpositions de ce type $(i i+1)$ , ah ? C'était évident ?
A priori, comme tu ne poses pas de questions sur tout ça, tu sais répondre aisément à toutes ces questions. Mais mon petit doigt me dit que non. Tu essaies de nous faire croire que tu sais répondre à ces questions, c'est différent.
1) L'ensemble des permutation de $[|1,n|]$ dans lui-même.
2) Un inversion est un couple $(i,j) \in [|1,n|]^2$ tel que $i<j$ et $\sigma(i) > \sigma(j)$.
3) Une transposition est un 2-cycle. $(i \ i+1)$ échange $i$ et $i+1$. $(i \ i-1)$ existe si $i \geq 2$.
4) Il suffit de voir que $(x_1 \ x_2 \ x_3)=(x_1 \ x_2)(x_2 \ x_3)$.
Je ne comprends pas pourquoi on prend un couple $(j,k)$, je ne comprends pas le passage en rouge et je ne vois pas de $inv \ \sigma +1$ ni de $inv \ \sigma-1$ pourtant c'est ce qu'il faut montrer.
Je n'ai pas compris pourquoi on regarde que $\rho(j)$ et $\rho(k)$.
Je ne comprends pas comment on démontre cette égalité.
Je crois que c'est inutile que je lise le corrigé car je ne comprends pas l'idée.
Merci j'ai réussi à comprendre, finalement, c'est long et rébarbatif mais pas si difficile.
@JLapin
Merci l'exemple suivant m'a permis de comprendre.
Soit $\sigma= (1 \ 2 \ 3 )$ et $(i \ i+1)= (2 \ 3)$ avec $n=5$. $\rho =\sigma (2 \ 3)$.
Par contre je me demande une chose, ayant fait un dessin, le corrigé a oublié de dire que quand on regarde le couple $(i,k)$ on prend $i<k<k+1$.
Pourquoi le corrigé ne traite pas le cas $(k,i+1)$ avec $k<i+1$ ? C'est le seul détail que je n'ai pas compris.
D'ailleurs le corrigé de cette question est rédigé de façon remarquable, c'est très détaillé.
Je vais maintenant essayer de traiter la deuxième question.
Car je ne vois pas comment démontrer la formule dans ce cas.
Si $\sigma(i) < \sigma(i+1)$, comment comparer $\rho(j)$ et $\rho(k)$ ? Comment comparer $\sigma(j)$ et $\sigma(k)$ pour montrer que $\rho$ a une inversion de plus que $\sigma$ ?
Pour les autres cas, j'ai bien compris en refaisant les calculs du corrigé et en distinguant les cas $\sigma(i) < \sigma(i+1)$ et $\sigma(i+1) > \sigma(i)$.
Ensuite, on distingue bien les cas $\sigma(i) < \sigma(i+1)$ et $\sigma(i+1) > \sigma(i)$.
Prenons le cas $\sigma(i) < \sigma(i+1)$.
Par exemple, si $(j,k)=(i,i+1)$.
On a $\rho(j)=\rho(i)=\sigma(i+1)$ et $\rho(k)=\rho(i+1)=\sigma(i)$.
$\sigma$ n'est pas inversé car on a $j<k \implies \sigma(j) < \sigma(k)$.
Mais $\rho$ est inversé car $j<k \implies \rho(j) > \rho(k)$.
Et à la fin j'ai compté le nombre d'inversion en m'aidant d'un tableau.
Pour la question $b$, elle semble plus facile, mais je ne suis pas sûr d'avoir compris pourquoi on a le droit d'utiliser la question $1$ pour $(i_j \ i_{j+1})$ alors que dans Q1, on a des transposition de la forme $(i \ i+1)$.
La question $c$ semble difficile.
Pour le début de la $c$, je ne comprends pas pourquoi on a le droit de prendre $\sigma(i+1) > \sigma(i)$... Pour moi $\sigma$ est fixé dans cette question.
Je ne sais pas faire cette question. C'est le genre de question ou je n'arrive pas à écrire une seule ligne.
En d'autres mots, si la question avait été : Si $\sigma \neq Id$, peut on affirmer qu'il existe forcément $i_1$ tel que $\sigma(i_1+1) < \sigma(i_1)$ ?, tu aurais répondu quoi à cette question ?
Edit. J'ajoute un point. Tu as répondu (a priori correctement) aux 4 questions que je posais. Bien, je n'y croyais pas. Je pense vraiment que pour ton image (et pas que pour ton image), si tu commençais chacun de tes messages en résumant les 4 ou 5 définitions utiles à l'exercice, plutôt que seulement dire que tu ne comprends rien, tu y gagnerais beaucoup.
Cet exercice fait travailler mon point faible en maths, les questions qui se résolvent avec des algorithmes.
Déjà dans la b, je bloque sur la récurrence, dans le corrigé on utilise la question $a$ pour $(i_j \ i_{j+1})$ alors que la question $a$ est valable pour des transposition du type $(i \ i+1)$.
Pour la question $c$ le résultat ne semble pas intuitif du tout pour moi. Mais j'ai finalement compris à l'aide d'un exemple simple.
Corrigé de Qc :
Soit $\sigma \ne id$. Alors il existe un couple $(i,j)$ qui est inversé par $\sigma$ c'est-à-dire tel que $i<j$ et $\sigma(i) > \sigma(j)$.
Si $j>i+1$ et $\sigma(i+1)> \sigma(i)$ alors $\sigma(i+1) > \sigma(j)$ ainsi le couple $(i+1,j)$ est aussi inversé.
On recommence avec $i+1$ à la place de $i$. Si $j \ne i+2$ alors $(i+1 \ i+2)$ ou $(i+2,j)$ est inversé.
Le processus s'arrête au plus tard pour $j-1$. Ainsi, on a trouvé un couple $(i_1 \ i_{1}+1)$ avec $i \leq k < k+1 \leq j$ qui est inversé.
Soit $\sigma=(1 \ 4)(2 \ 6) \in \mathfrak{S}_6$.
On a bien $\sigma \ne id$.
Posons $i=1$ et $j=4$.
$(1,4)$ est inversé par $\sigma$ car $1<4$ et $\sigma(1)=4> \sigma(4)=1$.
- $j =4 \ne i+2=3$. On a $4 > i+2$ et $\sigma(i+2)=\sigma(3)=3> \sigma(i+1)=\sigma(2)=6$.
Le couple $(2,3)$ est inversé et le processus s'arrête à $j-1=4-1=3$.On a bien trouvé un couple $(i_1 \ i_1 +1)$ inversé par $\sigma$, on a $i_1 =2$.
Puis on écrit en dessous les mêmes nombres de $1$ à $n$, dans un autre ordre. En dessous du nombre $i$, on a $\sigma(i)$
L'ordre de la 2ème ligne est différent de l'ordre de la première ligne, sinon notre fonction $\sigma$ serait l'identité.
Du coup, dans la 2ème ligne, les nombres ne seraient pas en ordre croissant. L'ordre croissant nous donnerait l'identité.
Et comme les nombres de la 2ème ligne ne sont pas en ordre croissant, il y a un endroit où on a $\sigma(i+1) < \sigma(i)$
Le résultat à démontrer est 'vrai, évident'. Reste à formaliser une démonstration bien rédigée.
Quand on te demande de démontrer telle propriété, il est toujours utile de se dire : cette propriété, est-ce que j'aurais pu la deviner par moi-même, est-ce qu'elle est vraie. Avant même de vouloir la démontrer !
Ca te permet de comprendre la 'ligne directrice de l'exercice', et non de subir chaque question comme un coup de poing que tu reçois.
Et surtout, ça te permet de consolider tes intuitions, en vue d'autres exercices. Et c'est ça qui est utile.
Merci très intéressant ça a l'air tellement simple avec ta méthode.
En effet, ce genre de question il faut d'abord la traiter sur une exemple pour bien voir les choses.
Mais ici je n'ai pas pensé à écrire la permutation avec deux lignes pour bien voir les choses.