Permutazione

Una permutazione è un modo di ordinare in successione oggetti distinti, come nell'anagramma di una parola. In termini matematici una permutazione di un insieme  si definisce come una funzione biiettiva .

Elencare e contare le permutazioni 
Il numero delle permutazioni di  oggetti è pari al fattoriale di :

infatti ci sono  modi di scegliere l'oggetto che occupa la prima posizione, per ciascuno di essi ci sono  modi di scegliere l'oggetto che occupa la seconda posizione, poi per ogni coppia di oggetti fissati nelle prime due posizioni ci sono  modi di scegliere l'oggetto nella terza posizione, e così via, fino ad occupare tutte le posizioni.

Ad esempio, le permutazioni possibili dell'insieme di quattro lettere "ABCD" sono 24 e si presentano come:
ABCD BACD CABD DABC
ABDC BADC CADB DACB
ACBD BCAD CBAD DBAC
ACDB BCDA CBDA DBCA
ADBC BDAC CDAB DCAB
ADCB BDCA CDBA DCBA

Insiemi con ripetizioni 
Se nell'insieme di partenza vi sono degli elementi ripetuti, alcune permutazioni danno la stessa sequenza. Ad esempio le permutazioni della serie di quattro lettere "ABAB" forniscono soltanto 6 risultati distinti:
AABB ABAB ABBA
BBAA BABA BAAB
In generale, se l'insieme è formato da  oggetti, di cui  sono di un tipo,  di un altro tipo, ecc. fino a , con , il numero di permutazioni distinte 

o permutazioni con ripetizioni di un insieme di  elementi, contenente , , ecc. elementi ripetuti ovvero identici tra loro, è il numero di sequenze con elementi distinti pari a

che viene detto coefficiente multinomiale. Nelle permutazioni di un insieme con ripetizioni, se un elemento in una data posizione è sostituito da un altro elemento ripetuto la permutazione non cambia.

Nell'esempio mostrato,  e , e si ottiene quindi

Dimostrazione 
Si inseriscano in una tabella tutte le permutazioni semplici di  oggetti in cui solo  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 il prodotto del numero di righe per il numero di colonne si ottiene il numero di permutazioni:

Ci saranno quindi tante righe quante permutazioni delle lettere ripetute e tante colonne quante permutazioni con ripetizione

Se gli oggetti che si ripetono sono di più tipi, allora si eliminano prima gli elementi di un tipo trattandoli come diversi da quelli di altro tipo. Quindi si applica la formula sopra ottenendo le permutazioni semplici degli oggetti comprese quelle del tipo rimanente su cui sarà possibile applicare nuovamente la formula ottenendo le permutazioni con ripetizione cercate. Generalizzando si ottiene la formula

Composizione 

Una permutazione è una funzione biettiva . Due permutazioni  e  possono quindi essere composte e il risultato è ancora una permutazione. L'insieme  delle permutazioni di  con l'operazione di composizione forma un gruppo, detto gruppo simmetrico. L'elemento neutro è la permutazione che lascia fissi tutti gli elementi; in notazione ciclica  cioè si rappresenta con un numero di n del tipo 1-ciclo.

Cicli 
Sia  una successione di elementi distinti di . Il ciclo

è la permutazione che sposta in avanti di uno tutti gli  e tiene fissi gli altri. Più formalmente è definita nel modo seguente:

 per gli altri 
L'ordine del ciclo è il numero . Una trasposizione è un ciclo  di ordine 2: consiste semplicemente nello scambiare gli elementi  e , lasciando fissi tutti gli altri.

Due cicli  e  sono indipendenti se  per ogni  e . Due cicli indipendenti  e  commutano, cioè . L'importanza dei cicli sta nel seguente teorema: ogni permutazione si scrive in modo unico come prodotto di cicli indipendenti.

Poiché cicli indipendenti commutano, l'unicità è da intendersi a meno di scambiare l'ordine dei cicli.

Notiamo infine che le notazioni  e  definiscono lo stesso ciclo, mentre  e  sono cicli diversi.

Notazione 
Ci sono due notazioni per scrivere una permutazione. La notazione detta 2-linea:

oppure la notazione detta ciclica:

dove 

da notare la differenza tra le notazioni che indicano la corrispondenza di valori  e quella che indica un li-ciclo o un lj-ciclo 

Per la composizione  si possono utilizzare le seguenti tabelle di corrispondenza: 

{| class="wikitable"; style="text-align: center"
|+ Composizione ciclica
! colspan=3|β || colspan=3 | α || rowspan = 2 |γ =  α ∘ β
|-
! style="min-width:4em;" |ls-ciclo dx
! style="min-width:4em;" | 
! style="min-width:4em;" |l1-ciclo sx
! style="min-width:4em;" |lr-ciclo dx
! style="min-width:4em;" | 
! style="min-width:4em;" |l1-ciclo sx

|-
| style="background-color:#D2D2D2;"| ||  ||  ||  ||  ||  ||
|-
| → ||  || → || → || ||→  ||→
|-style="background-color:#ABCDEF;"
|  ||  ||  ||  || ||  || 
|-
| ||  ||   ||     || ||  ||
|-
|  →  ||  ||  →  ||  →   || ||  →  || → 
|-
|  →  ||  ||  →  ||  →   || ||  →  || → 
|-style="background-color:#ABCDEF;"
|  ||  ||  ||  ||  ||  ||
|-
|  ||  || ||  || ||  ||
|-
| → ||  || → || → || || →  || →
|-style="background-color:#ABCDEF;"
|  ||  ||  ||  ||  ||  ||
|}

da notare che nella composizione ciclica le righe evidenziate in celeste indicano la chiusura di un ciclo per il risultato. Inoltre i valori delle colonne sono indicativi per quanto riguarda il loro ordine che segue quello del ciclo. Comunque la sequenza iniziale (evidenziata in grigio nella tabella)  è corretta. Vedere l'esempio per chiarezza. 

Esempio
Si considerino ad esempio le due permutazioni dell'insieme  Si può scrivere sotto a ogni numero la posizione in cui questo viene spostato:

Alternativamente, si può codificare la stessa permutazione sfruttando il teorema enunciato sopra, scrivendola come prodotto di cicli. Nel caso in esempio si ottiene  e 

Con la notazione ciclica due permutazioni possono essere composte in modo agevole: ritornando all'esempio si ha  L'implementazione con le tabelle di corrispondenza risulta più chiara:

{| class="wikitable"; style="text-align: center"
|+ Composizione ciclica
! β ||colspan=2|  α || rowspan = 2 |γ =  α ∘ β
|-
! style="min-width:4em;" |3-ciclo dx
! style="min-width:4em;" |2-ciclo
! style="min-width:4em;" |3-ciclo sx

|-style="background-color:#B2B2B2;"
| 1 → 2 || 2 → 2 || 2 → 5 ||  1 → 5 
|-
| 5 → 5 || 5 → 5 || 5 → 1 ||  5 → 1
|-style="background-color:#ABCDEF;"
| 1||  ||  ||  
|-
| 2 → 3 || 3 → 4 || 4 → 4 || 2 → 4
|-
| 4 → 4 || 4 → 3 || 3 → 3 || 4 → 3
|-
| 3 → 1 || 1 → 1 || 1 → 2 ||  3 → 2
|-style="background-color:#ABCDEF;"
| 2 ||  ||  ||   
|}

Si noti che la composizione ciclica viene effettuata dal ciclo di destra verso il ciclo di sinistra. Per esempio, per vedere dove viene mandato 1 dalla composizione  si vede che  lo manda in 2,  non muove 2, e infine  manda 2 in 5. Quindi 1 va in 5 (corrisponde alla riga evidenziata in grigio nella tabella). Le righe evidenziate in celeste corrispondono alla chiusura di un ciclo del risultato.

Segno di una permutazione

Definizione 
Ogni ciclo è prodotto di trasposizioni. Infatti, sempre con la composizione da destra verso sinistra, si ha:

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 anche come  o . Si può dimostrare che se una stessa permutazione  può essere scritta sia come prodotto di  trasposizioni, sia come prodotto di  trasposizioni, allora  e  hanno la stessa parità, cioè sono entrambi pari o entrambi dispari.

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

Esempi 
 Tutte le trasposizioni sono dispari.
 Tra le  permutazioni degli elementi  vi sono:
 sono pari;
 sono dispari.

Proprietà 
Definito il prodotto di due permutazioni come la composizione delle stesse, si può dire che la funzione "segno" è moltiplicativa, cioè

Gruppo alternante 
Metà delle  permutazioni di un insieme di  elementi sono pari. Poiché la funzione segno è moltiplicativa, le permutazioni pari formano un sottogruppo normale del gruppo simmetrico  delle permutazioni di  di indice due, detto gruppo alternante e indicato con  Si tratta del nucleo dell'omomorfismo di gruppi

L'immagine è un gruppo ciclico con due elementi.

Formula per il segno 
Il segno di una permutazione  può essere calcolato tramite la formula seguente:

Note

Bibliografia

Voci correlate 
 Combinazione
 Convoluzione
 Dismutazione (matematica)
 Disposizione
 Ordine ciclico
 Permutazione alternata
 Probabilità
 Statistica
 Superpermutazione

Altri progetti

Collegamenti esterni 
 

Teoria della probabilità
Combinatoria