Permutazione

Da Wikipedia, l'enciclopedia libera.

Una permutazione è un modo di combinare n oggetti distinti scambiandoli di posizione, 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

1 Elencare e contare le permutazioni
- 1.1 Insiemi con ripetizioni
2 Composizione
3 Cicli
4 Notazione
5 Permutazioni pari e dispari
6 Voci correlate

[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 $n 1$ sono di un tipo, $n 2$ di un altro tipo, etc. fino a $n k$ , con $n=n_1+n_2+\ldots n_k$ , il numero di risultati distinti è

$\frac {n!}{n_1!\cdots n_k!}.$

Nell'esempio mostrato, $n = 4$ e $n 1 = n 2 = 2$ , e si ottiene quindi

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

[modifica] Composizione

Una permutazione è una funzione biiettiva $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 $a i$ 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] Permutazioni pari e dispari

Ogni ciclo è prodotto di trasposizioni. Infatti:

$(a_1,\ldots, a_n) = (1,2)(2,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.

Diciamo quindi che p è una permutazione pari o dispari a seconda che sia ottenibile con un numero pari o dispari di trasposizioni.

Ad esempio, tra le 6=3! permutazioni degli elementi {1, 2, 3} troviamo:

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

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

Qui e è la permutazione identica.

In generale, metà delle n! permutazioni di un insieme di n elementi sono pari. 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).