Numero di inversioni per ogni trasposizione in $S_n$

[complesso]

Buongiorno,
ho trovato che per ogni trasposizione $(i, j)$ con $i < j$ si ha \(\displaystyle \text{inv}((i, j)) = 2(j - i - 1) + 1 \).
Non capisco come va letta: $(i, j)$ è un'inversione di $\sigma \in S_n$ se $1 \leq i < j \leq n$ e $\sigma(i) > \sigma(j)$. Il numero \(\displaystyle \text{inv}((i, j)) \) di inversioni di $(i, j) \in S_n$ con $i < j$ non dovrebbe essere $0$ se $\sigma(i)<\sigma(j)$ o $1$ se $\sigma(i)>\sigma(j)$?
Potreste per favore aiutarmi a capire?

[Martino]

Un'inversione di $sigma=(i,j)$ (con $i<j$) è del tipo $(a,b)$ con $a<b$ e $sigma(a)>sigma(b)$, in particolare uno tra $a$ e $b$ è uguale a uno tra $i$ e $j$ (altrimenti si avrebbe $sigma(a)=a$ e $sigma(b)=b$). La stessa $(i,j)$ è un'inversione di se stessa, ora supponiamo che $(a,b) ne (i,j)$, cioè che $a ne i$ oppure $b ne j$. Se $a=i$ allora $b ne j$ quindi $sigma(b)=b$ e ottieni la condizione $j = sigma(a) > sigma(b) = b$ quindi hai $i < b < j$ cioè $j-i-1$ scelte per $b$. Sai continuare?

Se la cosa ti crea confusione in generale un'ottima tecnica è considerare valori piccoli, per esempio conta le inversioni di $(1,3)$ in $S_4$.

[complesso]

Grazie Martino per la risposta,
ho un po' di problemi a capire la definizione e avrei bisogno di chiarimenti.

1) Nell'esempio che ho letto in one-line notation $\sigma = 314265$ ha 4 inversioni: $(1, 2), (1, 4), (3, 4), (5, 6)$ e disegnando la treccia mi sembra ovvio. Quindi direi che \(\displaystyle \text{inv}(\sigma)=4 \). Se seguo lo stesso criterio e scrivo $\sigma = (1, 3)$ scritto così intendo che $1$ va in $3$ e $3$ va in $1$, e quindi $\sigma(1)=3$ e $\sigma(3)=1$, ma in questo modo l'inversione sarebbe solo $(1, 3)$. Da come mi dici a questo punto sto interpretando male. Che cosa significa in pratica $\sigma = (1, 3)$?

2) Cercando di capire la definizione che mi hai dato, penso che \(\displaystyle \text{inv}((1, 3))=3 \): $\sigma_1 = 231$, $\sigma_2 = 321$, $\sigma_3 = 312$, anche se non mi convince: quello che ti sto dicendo non sono il numero di inversioni di una permutazione come in 1), ma il numero di permutazioni $\sigma_i \in S_3$ che hanno l'inversione $(1, 3)$.

[Martino]

Osserva che quando parli di matematica è fondamentale chiarire le notazioni, per esempio qui stai parlando di una certa funzione che hai chiamato "inv" che però, dal tuo ultimo messaggio, si deduce che non ti sia del tutto chiara.

In realtà la definizione di "inv" l'hai data tu stesso qui (e hai fatto benissimo a darla perché chi ti legge non può sapere cosa significa "inv" se tu non glielo spieghi):

$(i, j)$ è un'inversione di $\sigma \in S_n$ se $1 \leq i < j \leq n$ e $\sigma(i) > \sigma(j)$. Il numero \(\displaystyle \text{inv}((i, j)) \) di inversioni di $(i, j) \in S_n$ con $i < j$ [...]

(E mi sono basato su questa definizione nella mia risposta precedente.) In altre parole, data una permutazione $sigma$, una sua inversione è una trasposizione $(i,j)$ con $i<j$ tale che $sigma(i) > sigma(j)$, e il numero di inversioni di $sigma$ viene indicato con \( \displaystyle \mbox{inv}(\sigma) \) .

1) Nell'esempio che ho letto in one-line notation $\sigma = 314265$ ha 4 inversioni: $(1, 2), (1, 4), (3, 4), (5, 6)$ e disegnando la treccia mi sembra ovvio. Quindi direi che \(\displaystyle \text{inv}(\sigma)=4 \).

Perfetto, mi torna (ed è coerente con la definizione che hai dato di "inv" e che ho ripetuto sopra).

Se seguo lo stesso criterio e scrivo $\sigma = (1, 3)$ scritto così intendo che $1$ va in $3$ e $3$ va in $1$, e quindi $\sigma(1)=3$ e $\sigma(3)=1$, ma in questo modo l'inversione sarebbe solo $(1, 3)$. Da come mi dici a questo punto sto interpretando male. Che cosa significa in pratica $\sigma = (1, 3)$?

Qui non ti seguo più. Nella "one-line notation" lo scambio $(1,3)$ in $S_4$ è dato da $3214$ (cioè $1,3$ sono scambiati di posto mentre $2$ e $4$ sono fissati!), e applicando il conteggio che tu stesso hai fatto per $314265$, a me risulta che $3214$ abbia $3$ inversioni, che sono $(1,2)$, $(1,3)$, $(2,3)$ (quindi non solo $(1,3)$).

2) Cercando di capire la definizione che mi hai dato, penso che \(\displaystyle \text{inv}((1, 3))=3 \): $\sigma_1 = 231$, $\sigma_2 = 321$, $\sigma_3 = 312$, anche se non mi convince: quello che ti sto dicendo non sono il numero di inversioni di una permutazione come in 1), ma il numero di permutazioni $\sigma_i \in S_3$ che hanno l'inversione $(1, 3)$.

Occhio, qui rischiamo di perderci: una cosa è contare il numero di inversioni di una data permutazione, un'altra cosa (del tutto diversa) è, data una trasposizione $(i,j)$, contare il numero di permutazioni che hanno $(i,j)$ come inversione. Sono due cose totalmente diverse.

Dalla definizione che hai dato di \( \displaystyle \mbox{inv}(\sigma) \) , deduco che quello che devi fare per calcolare \( \displaystyle \mbox{inv}(\sigma) \) è proprio contare le inversioni di $sigma$. Quello che secondo me ti confonde è che, quando scrivi \( \displaystyle \mbox{inv}((i,j)) \) , tu pensi a $(i,j)$ come a un'inversione, ma in questo caso devi pensare a $(i,j)$ come a una semplice permutazione $sigma$, di cui poi conti le inversioni. Cioè $(i,j)$ è una certa permutazione (quella che scambia $i,j$ e fissa gli altri punti) e ha senso chiedersi quante inversioni ha, cioè ha senso chiedere quanto vale \( \displaystyle \mbox{inv}((i,j)) \) . Facendo questo conto, si ottiene esattamente $2(j-i-1)+1$, e nel precedente messaggio ti ho indicato come arrivare a questo risultato.

[complesso]

Grazie Martino,
ora ho capito come funziona.

Un'inversione di $ sigma=(i,j) $ (con $ i<j$) è del tipo $ (a,b) $ con $ a < b$ e $ sigma(a)>sigma(b) $, in particolare uno tra $ a $ e $ b $ è uguale a uno tra $ i $ e $ j $ (altrimenti si avrebbe $ sigma(a)=a $ e $ sigma(b)=b $). La stessa $ (i,j) $ è un'inversione di se stessa, ora supponiamo che $ (a,b) ne (i,j) $, cioè che $ a ne i $ oppure $ b ne j $. Se $ a=i $ allora $ b ne j $ quindi $ sigma(b)=b $ e ottieni la condizione $ j = sigma(a) > sigma(b) = b $ quindi hai $ i < b < j $ cioè $ j-i-1 $ scelte per $ b $. Sai continuare?

In pratica abbiamo:
se \(\displaystyle a \neq i \land b \neq j \implies \) nessuna inversione;
se \(\displaystyle a \neq i \land b = j \implies \)$ j-i-1$ scelte per a;
se \(\displaystyle a = i \land b \neq j \implies \) $j-i-1$ scelte per b;
se \(\displaystyle a = i \land b = j \implies \) $1$ inversione.
Totale scelte: $2(j-i-1) + 1$.

[Martino]

Sì esatto.

[complesso]

Grazie mille Martino.