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 $X$ si definisce come una funzione biiettiva $p\colon X\rightarrow X$.

Ognuna delle sei righe è una diversa permutazione di tre sfere distinte

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 permutazioni possibili della serie 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 $n$ oggetti, di cui $n_{1}$ sono di un tipo, $n_{2}$ di un altro tipo, ecc. 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

Si inseriscano 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. 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:

$\mathrm {righe} \times \mathrm {colonne} =P_{n}.$

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

$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 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

$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

Una permutazione è una funzione biettiva $p\colon X\to X$. Due permutazioni $p$ e $p'$ possono quindi essere composte e 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

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.

Notazione

Ci sono due notazioni per scrivere una permutazione. Si considerino ad esempio una permutazione dell'insieme $\{1,2,3,4,5\}.$ Si può scrivere sotto a 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 caso in esempio si ottiene $(125)(34).$

Con la notazione ciclica due permutazioni possono essere composte in modo agevole: ad esempio $(125)(34)$ e $(123)$ danno $(125)(34)(123)=(15)(243).$ Si noti che composizione è fatta da destra verso sinistra. Per esempio, per vedere dove viene mandato 1 dalla composizione $(125)(34)(123)$ si vede che $(123)$ lo manda in 2, $(34)$ non muove 2, e infine $(125)$ manda 2 in 5. Quindi 1 va in 5.

Segno di una permutazione

Definizione

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

$(a_{1},\ldots ,a_{n})=(a_{1},a_{n})(a_{1},a_{n-1})\cdots (a_{1},a_{2}).$

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 $(12)$anche come $(23)(13)(23)$ o $(14)(23)(34)(23)(14)$. Si può dimostrare che se una stessa permutazione $p$ può essere scritta sia come prodotto di $h$ trasposizioni, sia 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

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

  $\mathrm {id} ,(123),(132)$ sono pari;

  $(12),(13),(23)$ sono dispari.

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

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 simmetrico $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} \colon S(X)\to \{+1,-1\}.$

L'immagine è un gruppo ciclico con due elementi.

Formula per il segno

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

$\operatorname {segno} (\sigma )=\prod _{1\leq i<j\leq n}{\frac {\sigma (j)-\sigma (i)}{j-i}}=\prod _{i=1}^{n-1}\left(\prod _{j=i+1}^{n}{\frac {\sigma (j)-\sigma (i)}{j-i}}\right).$

Voci correlate

• Combinazione
• Dismutazione (matematica)
• Disposizione
• Probabilità
• Statistica
• Superpermutazione

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su permutazione

Collegamenti esterni

• (EN) Permutazione, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

Controllo di autorità	Thesaurus BNCF 32734