Forum de mathématiques - Bibm@th.net

Le raisonnement par récurrence est complètement lié au procédé de comptage des inversions suivant pour une permutation de {1,...,n} :
compter les entiers écrits après n, effacer n ;
compter les entiers écrits après n-1 et ajouter au total précédent, effacer n-1 ;
etc.
Là, on descend ;)

Si, c'est impossible : pour toute permutation $\sigma$, il est très facile de donner un exemple de permutation $\gamma$ telle que $\text{Card}(\text{Inv}(\sigma) \bigtriangleup \text{Inv}(\gamma) ) =1$.

Bonjour,

Je tape une réponse possible, au cas où la question vous aurait intéressé ( moi c'est surtout Latex qui est -un peu - galère).
On pressent ce résultat quand on pense aux transpositions ( avec quelques connaissances sur $\mathfrak{S}_n$ ), encore faut-il trouver une preuve complète.

Le sens $\sigma = \gamma  \Rightarrow Inv(\sigma) = Inv(\gamma)$ est clair.
Montrons le sens contraire.

Supposons donc maintenant que $Inv(\sigma) = Inv(\gamma)$.
Notons $\mathcal{I}(\sigma) = Card( Inv(\sigma))$ pour une permutation $\sigma$  quelconque.

L'idée est d'abaisser conjointement $\mathcal{I}$ pour $\sigma $ et $\gamma$ afin d'arriver à 0, tout en préservant l'égalité de leurs ensembles d'inversions.
En effet $\mathcal{I}(\sigma) = 0 \Rightarrow \sigma= Id$ ( résultat facile car Id est la seule $\sigma$ à vérifier $\sigma(1) < \sigma(2) < ... < \sigma(n)$.

- si $\mathcal{I}(\sigma) = 0 = \mathcal{I}(\gamma)$ , il n'y a rien à faire vu qu'elles sont égales à l'identité.
- sinon il existe un couple $ ( i, i+1) \in  Inv(\sigma) = Inv(\gamma)$.

Alors on remarque, d'une part, que pour $\sigma o (i,i+1) $ et $\gamma o (i,i+1) $ ,  $\mathcal{I}$  diminue d'une unité.
D'autre part un calcul facile montre que $Inv(\sigma o (i,i+1)) = Inv(\gamma o (i,i+1))$.

On peut donc itérer  le procédé tant que l'on n'atteint pas 0.
Quand on obtient 0 après quelques étapes, on a donc  $\sigma o (i,i+1)o (u,u+1) o ...o(z,z+1) = \gamma o (i,i+1)o (u,u+1) o ...o(z,z+1) = id$.

Il suffit de composer à droite Id par $(z,z+1) o ....o(u,u+1)o(i,i+1)$ pour voir l'égalité de $\sigma$ et $\gamma$
Voilà, en fait plus lourd à rédiger qu'autre chose (en espérant ne pas avoir fait d'erreurs).

Il n'est pas impossible qu'on puisse affaiblir l'hypothèse, par exemple avec $Card ( Inv(\sigma) \Delta Inv(\gamma) ) $ suffisamment petit, donc les deux ensembles d'inversion presque égaux, notamment pour des grandes valeurs de n.

A.