permutazioni pari dispari

[sgiangrag]

cosa sono le permutazioni pari e dispari?

[Nonno Bassotto]

Considera una permutazione di {1,..,n} data da a_1, ..., a_n. Definisci la parità della permutazione come
$ \varepsilon (a) = \prod_{1 \leq i<j \leq n} \frac{a_i-a_j}{i-j} $
Questo numero può essere 1 o -1, perché tutti i fattori, a meno del segno si cancellano. La permutazione si dice pari se $ \varepsilon(a) = 1 $ e dispari altrimenti. Le permutazioni sono particolari funzioni da {1,...,n} in {1,...,n}, quindi si possono comporre. Una proprietà utile è che la parità della composizione di due permutazioni è il prodotto delle parità delle due permutazioni. Ad esempio la composizione di permutazioni pari è sempre pari. Riesci a vedere da questo perché il gioco del 15 non è risolubile se si parte dalla configurazione con tutti i numeri ordinati tranne il 14 e il 15 scambiati?
Ciao

[hydro]

Una permutazione su n elementi si può scrivere come prodotto di scambi, ovvero elementi del gruppo simmetrico $ S_n $ che scambiano due elementi e lasciano "fermi" tutti gli altri (ovvero biiezioni del tipo $ a \rightarrow b, b\rightarrow a, x \rightarrow x \forall x \neq a,b $). Anche se non esiste sempre un unico modo di scrivere una permutazione come prodotto di scambi, si può dimostrare che la parità del numero di scambi in cui si decompone la permutazione è invariante. Pertanto una permutazione è pari (dispari) se si può scrivere come prodotto d un numero pari (dispari) di scambi.
Le permutazioni pari formano un sottogruppo di $ S_n $, detto sottogruppo alterno, che ha ordine $ =\frac{n!}{2} $

EDIT: scusa nonno bassotto, non avevo visto la risposta

[MindFlyer]

In QUESTO PAGINA c'è un esercizietto sulle permutazioni pari che proposi mesi fa e nessuno cagò.

[SkZ]

sbaglio nel sentirlo familiare per quanto riguarda i tensori antisimmetrici?


PS: mi unisco al cordoglio di Mindflyer per il suo esercizio.

[sgiangrag]

yla risposta di hydro mi sembra più chiara di quella di nonno bassotto tranne 1 cosa:

Le permutazioni pari formano un sottogruppo di Sn, detto sottogruppo alterno, che ha ordine n!/2

questo però se è dimostrato che vale vale per n>2

Considera una permutazione di {1,..,n} data da a_1, ..., a_n.

ma a_1...a_n sono numeri arbitrari?

Definisci la parità della permutazione come
$ \varepsilon (a) = \prod_{1 \leq i<j \leq n} \frac{a_i-a_j}{i-j} $
Questo numero può essere 1 o -1, perché tutti i fattori, a meno del segno si cancellano.

e perchè si annullano?

La permutazione si dice pari se $ \varepsilon(a) = 1 $ e dispari altrimenti.

non riesco a capire cosa c'entri il fatto che quella strana produttoria faccia 1 col fatto che i numero di scambi deve essere pari seguendo il discorso di hydro

Le permutazioni sono particolari funzioni da {1,...,n} in {1,...,n}

che significa questo? che il codominio è {1,...,n} e il dominio {1,...,n}?

quindi si possono comporre.

io so che comporre 2 funzioni significa fare f(g(n)) e quindi (n!)! ma non credo che c'entri col discorso che fai tu...

Riesci a vedere da questo perché il gioco del 15 non è risolubile se si parte dalla configurazione con tutti i numeri ordinati tranne il 14 e il 15 scambiati?

sinceramente no...se capissi meglio la spiegazione teorica magari..
grazie a Hydro e grazie a Nonno Bassotto per la pazienza e scusa la mia ignoranza in campo di teoria matematica...

[EvaristeG]

Allora, ci provo io.
Innanzitutto chiariamoci le idee sui nomi: una permutazione di un insieme A è una funzione bigettiva $ f:A\to A $. Perchè questa cosa "permuta" gli elementi di A? Beh, immaginiamo di aver messo in un qualche ordine tali elementi (e quindi fondamentalmente di averli numerati da 1 a n=|A|); allora la funzione f crea un secondo modo di ordinarli, ovvero mettiamo come primo elemento l'immagine sotto f di quello che all'inizio avevamo fissato come primo elemento, poi a seguire l'immagine sotto f di quello che all'inizio avevamo fissato come secondo eccetera.
In pratica, ponendo A={1,..,n}, otteniamo l'ordinamento {f(1), f(2), ... , f(n)}; questa è dunque la permutazione che manda $ 1\to f(1), 2\to f(2), \ldots, n\to f(n) $.
Ora, di solito una permutazione si scrive così
$ \left(\begin{array}{cccc}1&2&\ldots&n\\f(1)&f(2)&\ldots&f(n)\end{array}\right) $
e va letta in verticale (1 va in f(1) e così via).
Comporre due permutazioni significa considerare la permutazione indotta dalla composizione delle funzioni associate alle due permutazioni: se hai
(1) $ \left(\begin{array}{cccc}1&2&\ldots&n\\f(1)&f(2)&\ldots&f(n)\end{array}\right) $
e
(2) $ \left(\begin{array}{cccc}1&2&\ldots&n\\g(1)&g(2)&\ldots&g(n)\end{array}\right) $
con f e g funzioni bigettive di {1,..,n} in sè, potrai considerare le due permutazioni
$ \left(\begin{array}{cccc}1&2&\ldots&n\\f(g(1))&f(g(2))&\ldots&f(g(n))\end{array}\right) $
e
$ \left(\begin{array}{cccc}1&2&\ldots&n\\g(f(1))&g(f(2))&\ldots&g(f(n))\end{array}\right) $
che corrispondono rispettivamente ad applicare prima la permutazione (2) e poi la (1), oppure prima la (1) e poi la (2).

Prova a farti un esempio semplice con le due permutazioni
$ \left(\begin{array}{cccc}1&2&3&4\\2&4&1&3\end{array}\right) $ e $ \left(\begin{array}{cccc}1&2&3&4\\3&4&1&2\end{array}\right) $
scrivendo le funzioni che le inducono e componendole nei due modi.

Ora, il numero scritto da Nonno Bassotto è
$ \epsilon(f)=\displaystyle{\prod_{1\le i<j\le n}\dfrac{f(i)-f(j)}{i-j}} $
Se fissi i e j, ad esempio i=2 e j=7, di certo ci saranno un i' e un j' tali che f(i')=2 e f(j')=7 oppure tali che f(j')=2 e f(i')=7, perchè f è una bigezione. Quindi ad ogni differenza al denominatore del tipo i-j corrisponde una (ed una sola) differenza al numeratore del tipo f(i')-f(j') che differisce da i-j al più per il segno; per questo, si semplifica tutto e può rimanere solo 1 o -1.

Che cosa c'entra questo con gli scambi di hydro è una storia lunga, ma per dare l'idea, dovresti innanzitutto accorgerti che vale
$ \epsilon(f\circ g)=\epsilon(f)\epsilon(g) $
dove con $ f\circ g $ intendo la composizione di permutazioni di cui ho parlato prima. Ora, se accetti il fatto che ogni permutazione può essere descritta con una successione ordinata di scambi di coppie (ovvero di permutazioni che lasciano fermi tutti gli elementi tranne due che vengono scambiati di posto), ti accorgerai subito che se f è una permutazione che scambia una coppia e basta, $ \epsilon(f)=-1 $ e quindi se la nostra permutazione g si scrive come $ g=f_1\circ f_2\circ\ldots\circ f_n $ (dove $ f_i $ sono scambi), si ha $ \epsilon(g)=(-1)^n $.
Dunque le permutazioni pari sono quelle che si scrivono con un numero pari di scambi, quelle dispari le altre.

Ah, a proposito del sottogruppo alterno, non capisco cosa ti faccia problema per n=2 : in S_2 ci sono due permutazioni, una che non fa niente e l'altra che scambia due elementi; quella che non fa niente forma, da sola, un sottogruppo di ordine 1=(2!/2) che se vuoi puoi anche chiamare sottogruppo alterno di S_2 e indicare con A_2 ... piuttosto, è per n=1 che le cose non hanno senso ... ma lì non c'è molto da permutare.

[Nonno Bassotto]

Ok, scusa, forse sono stato troppo sintetico. Comunque spero che la discussione di Evariste ti abbia chiarito le idee. Non ho parlato della parità del numero di trasposizioni perché
1. ti avrei dovuto convincere che ogni permutazione è composizione di trasposizioni
2. comunque per far vedere che la parità non dipende dal particolare modo che hai scelto per scomporre la tue permutazione in trasposizioni devi introdurre l'altra definizione che ho dato io (o comunque questo è il modo più facile).

Se ci sono altri dubbi chiedi pure.
Ciao

[sgiangrag]

una funzione bigettiva è la stessa cosa di una funzione biiettiva? a parte questo credo di aver capito tutto...per esserne sicuro innanzitutto provo a risolvere l'esempio:
f(g(i)) diventa
$ \left(\begin{array}{cccc}1&2&3&4\\4&2&3&1\end{array}\right) $
mentre g(f(i)) diventa
$ \left(\begin{array}{cccc}1&2&3&4\\1&3&2&4\end{array}\right) $
per quanto riguarda il numero di nonno bassotto invece per vedere se ho capito: è vero che il numero dei prodotti in quella produttoria è il numero di combinazioni di n a 2 cioè n(n-1)/2?

Riesci a vedere da questo perché il gioco del 15 non è risolubile se si parte dalla configurazione con tutti i numeri ordinati tranne il 14 e il 15 scambiati?

vediamo se è così:inizialmente tutti i numeri stanno a posto tranne il 14 e il 15 scambiati tra loro quindi per ottenere la soluzione bisogna fare l'equivalente di 1 (dispari) scambio: scambiare il 14 col 15. E' impossibile scmbiare il 14 e il 15 senza coinvolgere gli altri numeri; dato che le permutazioni conservano la parità e la disparità per raggiungere la soluzione bisogna fare 1 numero dispari di scambi; supponiamo quindi di poterlo risolvere; consideriamo lo spazio vuoto:esso inizialmemente sta nell'angolo in basso a destra e alla fine della soluzione ritorna in questa casella originale, quindi in tutto avrà compiuto 1 numero pari mosse perchè se si sposta lungo 1 asse di 1 certo numro di posizioni le dovrà"recuperare". se lo spazio vuoto compie n mosse ci sono esattamente n-2 scambi: infatti la prima mossa sposta o il 12 o il 15 ma non li permuta, l'ultima serve solo a far venire lo spazio nell'angolo in basso a desta, tutte le altre mosse invece permutano una coppia di numeri. Quindi il numero di scambi dovrebbe essere sia pari che dispari ma ciò è impossibile. Tutto giusto?
In ogni caso il discorso di hydro mi sembra semplice mentre quello di nonno bassotto mi sembra un' inutile astrazione matematica che cerca di dire ciò che è in realtà semplice.
Grazie comunque a tutti e soprattutto a edriv che è riuscito a farmi conciliare i discorsi di hydro e nonno bassotto.
mi potreste riportare 1 dimostrazione che la parità e la disparità delle permutazioni sono invarianti e che il numero di permutazioni pari è uguale a quello di permutazioni dispari?

[Pigkappa]

una funzione bigettiva è la stessa cosa di una funzione biiettiva?

Dovrebbero essere sinonimi, come anche suriettiva/surgettiva

[Nonno Bassotto]

In ogni caso il discorso di hydro mi sembra semplice mentre quello di nonno bassotto mi sembra un' inutile astrazione matematica che cerca di dire ciò che è in realtà semplice.
mi potreste riportare 1 dimostrazione che la parità e la disparità delle permutazioni sono invarianti?

EDIT: ops, mi sono accorto che continuo a parlarti di trasposizioni senza avertele definite. Una trasposizione è una particolare permutazione che lascia fissi tutti gli elementi tranne due, che vengono scambiati fra loro.

Cosa intendi per invarianti? Intendi che la parità del numero di trasposizioni necessarie non dipende dalla particolare scomposizione in trasposizioni che scegli? Se sì, temo che dovremo passare per l'inutile astrazione matematica
Infatti la definizione che ho dato io non dipende da nessuna scomposizione: il numero che ti ho definito è 1 o -1 ed è completamente determinato dalla permutazione scelta. A questo punto osserva che la parità di una trasposizione, con la definizione che ti ho dato, è -1.

Supponiamo ora che la tua permutazione si scriva come composizione di n trasposizioni. Allora la parità della tua permutazione sarà (-1)^n. Ma questo numero non dipende dalla particolare decomposizione che hai scelto, dunque la parità di n non dipende dalla particolare decomposizione che hai scelto.

[Nonno Bassotto]

mi potreste riportare 1 dimostrazione che il numero di permutazioni pari è uguale a quello di permutazioni dispari?

Fissa una qualsiasi permutazione dispari a, ad esempio una trasposizione. Allora la funzione {permutazioni pari}->{permutazioni dispari} che manda b in $ b \circ a $ è biunivoca, con inversa la funzione {permutazioni dispari}->{permutazioni pari} che manda c in $ c \circ a^{-1} $

[Nonno Bassotto]

Riesci a vedere da questo perché il gioco del 15 non è risolubile se si parte dalla configurazione con tutti i numeri ordinati tranne il 14 e il 15 scambiati?

vediamo se è così:inizialmente tutti i numeri stanno a posto tranne il 14 e il 15 scambiati tra loro quindi per ottenere la soluzione bisogna fare l'equivalente di 1 (dispari) scambio: scambiare il 14 col 15. E' impossibile scmbiare il 14 e il 15 senza coinvolgere gli altri numeri; dato che le permutazioni conservano la parità e la disparità per raggiungere la soluzione bisogna fare 1 numero dispari di scambi; supponiamo quindi di poterlo risolvere; consideriamo lo spazio vuoto:esso inizialmemente sta nell'angolo in basso a destra e alla fine della soluzione ritorna in questa casella originale, quindi in tutto avrà compiuto 1 numero pari mosse perchè se si sposta lungo 1 asse di 1 certo numro di posizioni le dovrà"recuperare". se lo spazio vuoto compie n mosse ci sono esattamente n-2 scambi: infatti la prima mossa sposta o il 12 o il 15 ma non li permuta, l'ultima serve solo a far venire lo spazio nell'angolo in basso a desta, tutte le altre mosse invece permutano una coppia di numeri. Quindi il numero di scambi dovrebbe essere sia pari che dispari ma ciò è impossibile. Tutto giusto?

No, non è vero che ogni mossa permuta una coppia di numeri. Le mosse "orizzontali" lasciano invariato l'ordine dei numeri, mentre quelle "verticali" spostano un numero avanti o indietro di tre posizioni.

[edriv]

Grazie comunque a tutti e soprattutto a edriv che è riuscito a farmi conciliare i discorsi di hydro e nonno bassotto.

Prego, non pensavo di essere stato così utile
(forse ti riferivi ad EvaristeG, visto che in tutto il forum sono tra i pochi utenti che non hanno ancora risposto a questa discussione )

[sgiangrag]

Supponiamo ora che la tua permutazione si scriva come composizione di n trasposizioni. Allora la parità della tua permutazione sarà (-1)^n. Ma questo numero non dipende dalla particolare decomposizione che hai scelto, dunque la parità di n non dipende dalla particolare decomposizione che hai scelto.

...ah,certo,quanto sono cretino!

Fissa una qualsiasi permutazione dispari a, ad esempio una trasposizione. Allora la funzione {permutazioni pari}->{permutazioni dispari} che manda b in $ b \circ a $ è biunivoca, con inversa la funzione {permutazioni dispari}->{permutazioni pari} che manda c in $ c \circ a^{-1} $

uhmm...OK!

Riesci a vedere da questo perché il gioco del 15 non è risolubile se si parte dalla configurazione con tutti i numeri ordinati tranne il 14 e il 15 scambiati?

[....] infatti la prima mossa sposta o il 12 o il 15 ma non li permuta, l'ultima serve solo a far venire lo spazio nell'angolo in basso a desta, tutte le altre mosse invece permutano una coppia di numeri. Quindi il numero di scambi dovrebbe essere sia pari che dispari ma ciò è impossibile. Tutto giusto?

No, non è vero che ogni mossa permuta una coppia di numeri. Le mosse "orizzontali" lasciano invariato l'ordine dei numeri, mentre quelle "verticali" spostano un numero avanti o indietro di tre posizioni.

si infatti hai ragione...allora qual è il ragionamento corretto?

Grazie comunque a tutti e soprattutto a edriv che è riuscito a farmi conciliare i discorsi di hydro e nonno bassotto.

Prego, non pensavo di essere stato così utile
(forse ti riferivi ad EvaristeG, visto che in tutto il forum sono tra i pochi utenti che non hanno ancora risposto a questa discussione )

Si Edriv, Evariteg...iniziano sempre per E e devi essermi confuso -forse sono 1 po' dislessico. Scusa a Evaristeg quindi per averlo confuso e grazie ancora