Questa voce o sezione sull'argomento matematica non cita alcuna fonte o le fonti presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

Una permutazione è un modo di ordinare in successione n oggetti distinti, come nell'anagrammare una parola. In termini matematici una permutazione di un insieme X 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 24 permutazioni possibili della serie di quattro lettere "ABCD" sono:

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, etc. fino a , con , il numero di risultati distinti è

che viene detto coefficiente multinomiale.

Nell'esempio mostrato, e , e si ottiene quindi

  Composizione

Per approfondire, vedi la voce Gruppo simmetrico.

Una permutazione è una funzione biettiva . Due permutazioni e possono quindi essere composte, ed 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.

  Cicli

Sia una successione di elementi distinti di X. Il ciclo

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

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

Due cicli e sono indipendenti se per ogni i e j. Due cicli indipendenti a e b commutano, cioè . L'importanza dei cicli sta nel seguente teorema:

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 essenzialmente due notazioni per scrivere una permutazione. Consideriamo ad esempio una permutazione dell'insieme {1, 2, 3, 4, 5}. Si può scrivere sotto ad 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 nostro caso, otteniamo (1 2 5)(3 4).

Con la notazione ciclica, due permutazioni possono essere composte in modo agevole: ad esempio (1 2 5)(3 4) e (1 2 3) danno (1 2 5)(3 4)(1 2 3) = (1 3 4)(2 5). Si noti che composizione è fatta da sinistra verso destra, come si legge nelle lingue occidentali. Per esempio, per vedere in cosa viene mandato 1 dalla composizione (1 2 5)(3 4)(1 2 3) si vede che (1 2 5) lo manda in 2, (3 4) non muove 2, e infine (1 2 3) manda 2 in 3.

  Segno di una permutazione

  Definizione

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

Ne segue che ogni permutazione è prodotto di trasposizioni. Il numero di tali trasposizioni non è univocamente determinato dalla permutazione: per esempio la trasposizione si può scrivere anche come o . Si può però mostrare che se una stessa permutazione si può scrivere sia come prodotto di trasposizioni, che come prodotto di trasposizioni, allora e hanno la stessa parità, cioè sono entrambi pari o entrambi dispari.

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

  Esempi

• Tutte le trasposizioni sono dispari.
• Tra le 6=3! permutazioni degli elementi {1, 2, 3} vi sono:

  e, (1 2 3), (1 3 2) sono pari;

  (1 2), (2 3), (1 3) sono dispari.

• Tra le 24=4! permutazioni degli elementi {1, 2, 3, 4} ci sono permutazioni dispari che non sono trasposizioni: ad esempio, (1 2 3 4).

  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 n! permutazioni di un insieme di n elementi sono pari. Poiché la funzione segno è moltiplicativa, le permutazioni pari formano un sottogruppo normale del gruppo S(X) delle permutazioni di X di indice due, detto gruppo alternante e indicato con A(X). 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:

  Voci correlate

• Combinazione
• Dismutazione
• Disposizione
• Probabilità
• Statistica

  Altri progetti

• Commons contiene file multimediali su Permutazione

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi
Algebra elementare	Numero primo · MCD · mcm · Algoritmo di Euclide · Equazione · Disequazione · Polinomio · Aritmetica modulare
Teoria dei gruppi	Gruppo (finito · ciclico · abeliano) · Omomorfismo · Sottogruppo normale · Teorema di isomorfismo · Permutazione
Teoria degli anelli	Anello · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice
Teoria dei campi	Campo · Estensione di campi · Chiusura algebrica · Teorema fondamentale dell'algebra · Teoria di Galois

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica