Permutations contenues, pt de vue de Knuth — Les-mathematiques.net The most powerful custom community solution in the world

Permutations contenues, pt de vue de Knuth

Bonjour à toutes et à tous,

au détour de l'excellent livre d'Etienne Ghys "a singular promenade" je suis tombé sur le passage joint: on définit une permutation contenue $\sigma$ dans une autre $\pi$ si le support de $\sigma = \mathcal F$ est invariant par $\pi$ et la permutation induite, $\sigma$, est alors contenue dans $\pi$. On obtient alors une relation d'ordre (partielle) sur les permutations qui permet de démontrer un fort joli théorème que je laisserai les plus curieux d'entre vous aller chercher dans la référence (téléchargeable gratuitement dans le catalogue ENS Editions).

Problème: le petit exercice en marge "montrer que (2,1) est contenue dans toute permutation qui n'est pas l'identité"? Ah?
Donc (1,2,4,3) est l'identité puisque (2,1) n'est clairement pas contenue dedans... J'ai dû merder une définition quelque part (mon anglais se rouille malgré tout).

Amicalement,

F.D.

PS: ici les ordres << et <<< utilisés par Etienne Ghys sont deux ordres sur l'ensemble fini $\{1,\dots,n\}$ pour définir une permutation "à la façon des" informaticiens (il cite explicitement Donald Knuth).120562

Réponses

  • $\pi$ est définie par l'ordre $<<$, $1<<2<<3<<4$, et l'ordre $<<<$, $1<<<2<<<4<<<3$.
    Soit $F=\{4,3\}$, la restriction de $<<$ à $F$ est $3<<4$, et la restriction de $<<<$ à $F$ est $4<<<3$. Cela définit une permutation de $F$, qui est $(4,3)$. Comme $F$ a deux éléments, si on rapporte cette permutation à l'ensemble à deux éléments $\{1,2\}$, c'est bien $(2,1)$.

    Dit autrement, on considère une injection $i$ de $G=\{1,2\}$ dans $\{1,2,3,4\}$, et on considère $<<'$ défini sur $G$ par $x<<'y$ ssi $i(x)<<i(y)$ , et de même pour $<<<'$. Soit $i$ définie par $i(1)=3$, $i(2)=4$. Alors $<<'$ et $<<<'$ définissent bien la permutation de $\{1,2\}$ qui est $(2,1)$.
  • Merci de ta réponse!

    Je viens de la lire 3 fois et je crois que tu m'as fait comprendre: toute transposition peut s'écrire (2,1), c'est ça?
    Petit souci: comment fait-on avec 4<<3<<2<<1 qui donne le 4-cycle (4,3,2,1)?

    Je crois qu'en fait je me suis attaché à une notation au lieu de chercher le sens,

    merci encore,

    F.D.
  • Oui, c'est aussi que dans toute permutation $\pi$ différente de l'identité, il existe deux éléments $i$ et $j$ avec $i<<j$ tels que $\pi(i)>> \pi(j)$.
  • Pour associer à deux ordres $<<$ et $<<<$ totaux sur $E=\{1,2,\dots, n\}$, une permutation $\pi$, on associe au minimum de $<<$ le minimum de $<<<$. Au deuxième élément pour l'ordre $<<$, le deuxième élément pour l'ordre $<<<$, etc.
    C'est-à-dire que $\pi$ est un "morphisme" de $(E,<<)$ dans $(E,<<<)$.
    Ainsi, si l'ordre $<<$ est $1<<2<<3<<4$, et l'ordre $<<<$ quelconque, la permutation $\pi$ associée sera telle que $\pi(1)<<<\pi(2)<<<\pi(3)<<< \pi(4)$.
  • Il y a trois possibilités. Peut-être, c'est la même chose:
    1) $\sigma$ est contenue dans $\pi$ si il existe une partie $F$ de $E$ telle que le $\sigma(i)$-ème plus petit élément de $F$ pour $<<$ est le $i$-ème plus petit élément de $F$ pour $<<<$.
    2) $\sigma$, une permutation d'un ensemble à $p$ éléments $\{1,2,\dots,p\}$ , est contenue dans $\pi$ une permutation d'un ensemble à $n$ éléments $\{1,\dots,n\}$ avec $p\leq n$, ssi il existe $i_1<i_2<\dots<i_p$ des éléments de $\{1, \dots,n\}$ tels que $\pi(i_{\sigma(1)})<\pi ( i_{\sigma(2)}) < \dots < \pi (i_{\sigma(p)})$.
    3) $\sigma$, une permutation d'un ensemble à $p$ éléments $\{1,2,\dots,p\}$ , est contenue dans $\pi$ une permutation d'un ensemble à $n$ éléments $\{1,\dots,n\}$ avec $p\leq n$, ssi il existe $i_1<i_2<\dots<i_p$ des éléments de $\{1, \dots,n\}$ tels que $\pi^{-1}(i_{\sigma(1)})<\pi^{-1} ( i_{\sigma(2)}) < \dots < \pi^{-1} (i_{\sigma(p)})$.

    Je ne sais pas...

    Ce n'est pas la 2), car cela voudrait dire que $\pi^{-1}$ est contenue dans $\pi$, cela serait paradoxal.
    Le 1) et le 3) sont la même définition (en supposant pour l'équivalence entre 1) et 3) que $<<$ est l'ordre habituel $<$, et que $<<<$ est donné par $\pi(1)<<< \pi(2)<<< \dots <<< \pi(n)$)
  • Bonsoir,

    merci de t'être autant pris la tête pour moi :-) ton 1er message m'avait convaincu: dès lors que $\pi$ n'est pas 1 alors il y a un échange. Il me semblait qu'il y avait une question de support qui soit celle de ta première définition.
    En fait, il restreint l'ordre à la partie $\mathcal F$ considérée.
    Je reste dubitatif sur l'idée d'écrire (2,1) pour une transposition générique ou alors je ne comprends rien.

    Merci encore,
    F.D.
  • En résumé, soit $<<$ et $<<<$ deux ordres totaux sur $E=\{1,\dots,n\}$. On suppose pour simplifier que $1<<2<<3<<\dots<<n$. Ils définissent une permutation $\pi$ par $\pi(1) <<< \pi(2) <<< \dots <<< \pi(n)$.
    Alors $\sigma$ permutation de $\{1,\dots,p\}$ est contenue dans $\pi$ ssi il existe $i_1<<i_2<<\dots <<i_p$ appartenant à $E$, tels que $i_{\sigma(1)} <<< i_{\sigma(2)}<<< \dots <<<i_{\sigma(p)}$.

    Edit: je n'avais pas vu ton précédent message.
  • Merci pour toutes tes explications, il me reste à réfléchir :-)
    F.D.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!