Permutations contenues, pt de vue de Knuth

$\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)$.

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)$.

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)$)

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.