Permutazione

Da Wikipedia, l'enciclopedia libera.

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 p:X \rightarrow X.

Indice

[modifica] Elencare e contare le permutazioni

Il numero delle permutazioni di n oggetti è pari al fattoriale di n:

n! = n \cdot (n-1) \cdot (n-2) \cdots 1

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

Ad esempio, le 24 permutazioni possibili della parola "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

[modifica] Insiemi con ripetizioni

Se nell'insieme di partenza vi sono degli elementi ripetuti, alcune permutazioni danno la stessa sequenza. Ad esempio, le permutazioni della parola "ABAB" forniscono soltanto 6 risultati distinti:

AABB ABAB ABBA
BBAA BABA BAAB

In generale, se l'insieme è formato da n oggetti, di cui n1 sono di un tipo, n2 di un altro tipo, etc. fino a nk, con n=n_1+n_2+\cdots + n_k, il numero di risultati distinti è

{n \choose n_1, \dots , n_k} = \frac {n!}{n_1!\cdots n_k!}

che viene detto coefficiente multinomiale.

Nell'esempio mostrato, n = 4 e n1 = n2 = 2, e si ottiene quindi

\frac{4!}{2!\,2!} = \frac {24}{4} = 6.

[modifica] Composizione

Per approfondire, vedi la voce Gruppo simmetrico.

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

[modifica] Cicli

Sia a_1,\ldots, a_n una successione di elementi distinti di X. Il ciclo

p = (a_1,\ldots, a_n)

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

p(a_1) = a_2, p(a_2) = a_3, \ldots, p(a_n) = a_1
p(a) = a per gli altri a

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

Due cicli (a_1,\ldots, a_n) e (b_1,\ldots, b_m) sono indipendenti se a_i \neq b_j per ogni i e j. Due cicli indipendenti a e b commutano, cioè a * b = b * a. 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 (a,b,c) e (b,c,a) definiscono lo stesso ciclo, mentre (a,b,c) e (b,a,c) sono cicli diversi.

[modifica] 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:

\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{bmatrix}

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).

[modifica] Segno di una permutazione

[modifica] Definizione

Ogni ciclo è prodotto di trasposizioni. Infatti:

(a_1,\ldots, a_n) = (a_1,a_2)(a_2,a_3)\cdots(a_{n-1},a_n).

Ne segue che ogni permutazione p è prodotto di un certo numero k di trasposizioni. Benché il numero k sia variabile (la stessa p può essere ottenuta componendo un numero diverso di trasposizioni), la sua parità dipende soltanto da p.

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.

[modifica] 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).

[modifica] Proprietà

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

\operatorname{segno}(\sigma_1\sigma_2)=\operatorname{segno}(\sigma_1)\cdot \operatorname{segno}(\sigma_2).

[modifica] 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

\operatorname{segno}: S(X) \to \{+1,-1\}.

L'immagine è un gruppo ciclico con due elementi.

[modifica] Formula per il segno

Il segno di una permutazione σ può essere calcolato tramite la formula seguente:

\operatorname{segno}(\sigma)=\prod_{1\le i<j\le n}\frac{\sigma(j)-\sigma(i)}{j-i}.

[modifica] Voci correlate


Estratto da "http://it.wikipedia.org/wiki/Permutazione"
Strumenti personali