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.

Elencare e contare le permutazioni[modifica | modifica wikitesto]

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

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  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+\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 n_1=n_2=2 , e si ottiene quindi

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

Dimostrazione[modifica | modifica wikitesto]

Mettiamo in una tabella tutte le permutazioni semplici di n oggetti in cui solo k 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, per tale motivo su ogni riga ci saranno le stesse permutazioni, quindi se consideriamo il prodotto righe e colonne otteniamo le permutazioni semplici, cioè

righe \times colonne=P_n

Ci saranno quindi tante righe quante le permutazioni delle lettere ripetute e tante colonne quanto le permutazioni con ripetizione da trovare

k!\cdot P_{n;k}=P_n \quad \to \quad P_{n;k}=\frac{P_n}{k!}

Se gli oggetti che si ripetono sono di più tipi allora eliminiamo prima gli elementi di un tipo trattando come diversi quelli di altro tipo quindi applichiamo la formula sopra, otterremo le permutazioni semplici degli oggetti compresi quelle del tipo rimanente, per cui riapplicheremo la formula ottenendo le permutazioni con ripetizione cercate, quindi in generico si ottiene la formula P_{n;k_1,k_2,\cdots,k_n}=\frac{P_n}{k_1!k_2!\cdots k_n!}={n \choose k_1,k_2,\cdots,k_n}

Composizione[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi 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.

Cicli[modifica | modifica wikitesto]

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 \mbox{ 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.

Notazione[modifica | modifica wikitesto]

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

Definizione[modifica | modifica wikitesto]

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

 (a_1,\ldots, a_n) = (a_1,a_2)(a_1,a_3)\cdots(a_1,a_n).

Ne segue che ogni permutazione è prodotto di trasposizioni. Il numero di tali trasposizioni non è univocamente determinato dalla permutazione: per esempio la trasposizione (1 2) si può scrivere anche come (2 3) (1 3) (2 3) o (1 4) (2 3) (3 4) (2 3) (1 4). Si può però mostrare che se una stessa permutazione p si può scrivere sia come prodotto di h trasposizioni, che come prodotto di k trasposizioni, allora h e k 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[modifica | modifica wikitesto]

  • 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à[modifica | modifica wikitesto]

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

Gruppo alternante[modifica | modifica wikitesto]

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.

Formula per il segno[modifica | modifica wikitesto]

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

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

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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