Lemmino utile sulle permutazioni

[edriv]

Sia $ ~ S=\{1,2,\ldots,n\} $ e $ ~ f: S \rightarrow S $ una permutazione.

Uno scambio (x,y) di elementi di S si dice "inversione di f" se $ ~ (x-y)(f(x) - f(y)) < 0 $ (ovvero x,y e le loro immagini non sono ordinate allo stesso modo).

Date due permutazioni $ ~ \sigma, \tau $ diciamo che $ ~ \sigma \succeq \tau $ se possiamo ottenere $ ~ \tau $ da $ ~ \sigma $ facendo una successione di inversioni (ciascuna è un'inversione della permutazione precedente).

Dimostrare che $ ~ \succeq $ è effettivamente una relazione d'ordine, cioè soddisfa:
- $ ~ a \succeq a $
- $ ~ a \succeq b \land b \succeq a \Rightarrow a=b $
- $ ~ a \succeq b \land b \succeq c \Rightarrow a \succeq c $
Dimostrare anche che quest'ordine ha un massimo e un minimo, e dire quali.

Per giusticare l'utile, due applicazioni: (saran biunivoche!?)
- la disuguaglianza di Chebyshev
- il fatto che, nel problema delle arance e delle mele del wc, il caso peggiore è proprio peggiore. [vedi qui]

[modificato un po' in seguito alle osservazioni di Marco]

[Marco]

Date due permutazioni $ ~ \sigma, \tau $ diciamo che $ ~ \sigma \succeq \tau $ se possiamo ottenere $ ~ \tau $ da $ ~ \sigma $ facendo soltanto delle inversioni.

Temo di non aver capito la definizione. Io interpreto che, fissata $ f $, alcune (ma non tutte le) permutazioni sono inversioni. "Passare da sigma a tau con inversioni" lo interpreto come "posso ottenere tau applicando una sequenza di inversioni a sigma".

Ma allora la relazione d'ordine che definisci e' simmetrica, e quindi è un'equivalenza, altro che ordine!...

- il fatto che, nel problema delle arance e delle mele del wc, il caso peggiore è proprio peggiore...

Questo non e' carino: c'e' gente che al WC non c'era. Se proponi un problema, almeno riporta l'enunciato.

[edriv]

Riscrivo la definizione:
$ ~ \sigma \succeq \tau $ se e soltanto se esistono delle permutazioni
$ ~ \sigma = \sigma_1, \sigma_2,\ldots, \sigma_n = \tau $ tali che, per ogni $ ~ i = 1\ldots n-1 $, $ ~ \sigma_{i+1} $ si ottiene da $ ~ \sigma_i $ applicando un'inversione di $ ~ \sigma_i $.

[Marco]

Got it! Grazie per i chiarimenti.
----

Simmetria e transitività sono ovvie dalla definizione.

Un modo carino per farlo è con il seguente

Lemma. Se due permutazioni hanno lo stesso insieme di inversioni, allora sono la stessa permutazione.

[N.B.: la corrispondenza non è biunivoca: dato un arbitrario insieme di trasposizioni, non è detto che sia possibile costruire una permutazione con quel dato insieme di inversioni]

Lemma. Applicando ad una permutazione una propria inversione, l'insieme delle inversioni decresce strettamente (rispetto all'inclusione). L'inversione applicata è uno (ma non necessariamente l'unico) elemento che scompare dall'insieme delle inversioni

Corollario. La relazione di edriv è antisimmetrica, quindi è un ordine.

L'identità e è chiaramente un elemento minimale, mentre la permutazione r che ribalta l'ordine è un elemento massimale.

e è un minimo: sia f una permutazione arbitraria. Se f ha un'inversione, la applico, e ottengo un elemento strettamente minore. Continuo finché restano inversioni. Alla fine mi fermo quando non ci sono più inversioni, ma allora per il primo lemma sono arrivato a e. Quindi f > e

r è un massimo: data f, basta esibire una sequenza di inversioni che passi da r a f. Basta sistemare il primo elemento di f, poi il secondo, ecc...