Permutazione: differenze tra le versioni

[[File:Permutations RGB.svg|thumb|alt=Ognuna delle sei filerighe è una diversa permutazione di tre pallesfere distinte |Ognuna delle sei filerighe è una diversa permutazione di tre pallesfere distinte]]

Una '''permutazione''' è un modo di [[Relazione d'ordine|ordinare]] in [[Successione (matematica)|successione]] oggetti distinti, come nell'[[anagramma]] di una parola. In termini [[matematica|matematici]] una permutazione di un [[insieme]] ''<math>X''</math> si definisce come una funzione [[Corrispondenza biunivoca|biiettiva]] <math>p:\colon X \rightarrow X</math>.

:<math>n! = n \cdot (n-1) \cdot (n-2) \cdots 1,</math>

:<math>\frac{4!}{2!\,2!} = \frac {24}{4} = 6. </math>

Si inseriscano in una tabella tutte le permutazioni semplici di ''<math>n''</math> oggetti in cui solo ''<math>k''</math> si ripetono trattandoli come diversi tra loro in modo da avere sulle righe le permutazioni delle lettere non uguali e sulle colonne le permutazioni delle lettere uguali. Procedendo in questo modo su ogni riga ci saranno le stesse permutazioni, quindi se si calcola {{Chiarire|il prodotto righe e colonne|il prodotto del numero di righe per il numero di colonne?}} si ottengonoottiene le {{Chiarire|permutazioni semplici|il numero di permutazioni o le permutazioni?}}:

:<math>\mathrm{righe} \times \mathrm{colonne} = P_n.</math>

Una permutazione è una [[funzione biettiva]] <math> p:\colon X\to X </math>. Due permutazioni <math>p</math> e <math>p'</math> possono quindi essere [[funzione composta|composte]] e il risultato è ancora una permutazione. L'insieme <math>S(X)</math> delle permutazioni di <math>X</math> con l'operazione di composizione forma un [[gruppo (matematica)|gruppo]], detto [[gruppo simmetrico]]. L'[[elemento neutro]] è la permutazione che lascia fissi tutti gli elementi.

Sia <math> a_1,\ldots, a_n </math> una successione di elementi distinti di ''<math>X''</math>. Il ciclo

:<math> p(a_1) = a_2, p(a_2) = a_3,\ldots, p(a_n) = a_1 ;</math>

:<math> p(a) = a </math> per gli altri <math>a.</math>

L'ordine del ciclo è il numero ''<math>n''</math>. Una trasposizione è un ciclo <math> (a,b) </math> di ordine 2: consiste semplicemente nello scambiare gli elementi ''<math>a''</math> e ''<math>b''</math>, lasciando fissi tutti gli altri.

Due cicli <math> (a_1,\ldots, a_n)</math> e <math> (b_1,\ldots, b_m)</math> sono ''indipendenti'' se <math> a_i \neq b_j </math> per ogni ''<math>i''</math> e ''<math>j''</math>. Due cicli indipendenti ''<math>a''</math> e ''<math>b''</math> commutano, cioè <math> a*b = b*a </math>. L'importanza dei cicli sta nel seguente teorema: Ogni permutazione si scrive in modo unico come prodotto di cicli indipendenti.

Notiamo infine che le notazioni <math> (a,b, c) </math> e <math> (b,c,a) </math> definiscono lo stesso ciclo, mentre <math> (a,b, c) </math> e <math> (b,a,c) </math> sono cicli diversi.

Ci sono due notazioni per scrivere una permutazione. Si considerino ad esempio una permutazione dell'insieme <math>\{1, 2, 3, 4, 5\}.</math> Si può scrivere sotto ada ogni numero la posizione in cui questo viene spostato:

2 & 5 & 4 & 3 & 1\end{bmatrix}.</math>

Alternativamente, si può codificare la stessa permutazione sfruttando il teorema enunciato sopra, scrivendola come prodotto di cicli. Nel caso in esempio si ottiene <math>(1 2 5)(3 4).</math>

Con la notazione ciclica due permutazioni possono essere composte in modo agevole: ad esempio <math>(1 2 5)(3 4)</math> e <math>(1 2 3)</math> danno <math>(1 2 5)(3 4)(1 2 3) = (1 5)(2 4 3).</math> Si noti che composizione è fatta da destra verso sinistra. Per esempio, per vedere dove viene mandato 1 dalla composizione <math>(1 2 5)(3 4)(1 2 3)</math> si vede che <math>(1 2 3)</math> lo manda in 2, <math>(3 4)</math> non muove 2, e infine <math>(1 2 5)</math> manda 2 in 5. Quindi 1 va in 5.

Ne segue che ogni permutazione è prodotto di trasposizioni. Il numero di queste trasposizioni non è univocamente determinato dalla permutazione: per esempio si può scrivere la trasposizione <math>(1 2)</math>anche come <math>(2 3) (1 3) (2 3)</math> o <math>(1 4) (2 3) (3 4) (2 3) (1 4)</math>. Si può dimostrare che se una stessa permutazione <math>p</math> può essere scritta sia come prodotto di <math>h</math> trasposizioni, sia come prodotto di <math>k</math> trasposizioni, allora <math>h</math> e <math>k</math> hanno la stessa [[parità]], cioè sono entrambi pari o entrambi dispari.

Una permutazione ''<math>p''</math> è detta '''pari''' o '''dispari''' a seconda che sia ottenibile come prodotto di un numero pari o dispari di trasposizioni. Il ''segno'' di ''<math>p''</math> è definito rispettivamente come +1 e -1.

* Tra le 6=3! permutazioni degli elementi <math>\{1, 2, 3\}</math> vi sono:

*: <math>\mathrm{id}, (1 2 3), (1 3 2)</math> sono pari;

*: <math>(1 2), (1 3), (2 3)</math> sono dispari.

Metà delle ''<math>n''!</math> permutazioni di un insieme di ''<math>n''</math> elementi sono pari. Poiché la funzione segno è moltiplicativa, le permutazioni pari formano un [[sottogruppo normale]] del gruppo ''<math>S''(''X'')</math> delle permutazioni di ''<math>X''</math> di [[sottogruppo|indice]] due, detto '''gruppo alternante''' e indicato con ''<math>A''(''X'').</math> Si tratta del [[nucleo (matematica)|nucleo]] dell'[[omomorfismo di gruppi]]

:<math>\operatorname{segno}:\colon S(X) \to \{+1,-1\}.</math>

:<math>\operatorname{segno}(\sigma)=\prod_{1\le i<j\le n}\frac{\sigma(j)-\sigma(i)}{j-i} = \prod_{i=1}^{n-1}\left (\prod_{j=i+1}^{n} \frac{\sigma(j)-\sigma(i)}{j-i} \right ).</math>