Utente:Grasso Luigi/sandbox4/Permutazioni

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

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

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 dell'insieme 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 permutazioni distinte

o permutazioni con ripetizioni di un insieme di $n$ elementi, contenente $n_{1}$, $n_{2}$, ecc. elementi ripetuti ovvero identici tra loro, è il numero di sequenze con elementi distinti pari a

${n \choose n_{1},\dots ,n_{k}}={\frac {n!}{n_{1}!\cdots n_{k}!}}$

che viene detto coefficiente multinomiale. Nelle permutazioni di un insieme con ripetizioni, se un elemento in una data posizione è sostituito da un altro elemento ripetuto la permutazione non cambia.

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.

Notazione

Ci sono due notazioni per scrivere una permutazione. La notazione detta 2-linea:

$\alpha ={\begin{pmatrix}1&2&3&\ldots &n\\\alpha (1)&\alpha (2)&\alpha (3)&\ldots &\alpha (n)\end{pmatrix}}$

$\beta ={\begin{pmatrix}1&2&3&\ldots &n\\\beta (1)&\beta (2)&\beta (3)&\ldots &\beta (n)\end{pmatrix}}$

$\alpha \beta ={\begin{pmatrix}1&2&3&\ldots &n\\\alpha (\beta (1))&\alpha (\beta (2))&\alpha (\beta (3))&\ldots &\alpha (\beta (n))\end{pmatrix}}$

oppure la notazione detta ciclica:

$\alpha =\alpha _{1}\,\alpha _{2}\cdots \alpha _{r}=\prod _{i=1}^{r}\,\alpha _{i}\qquad$

$\beta =\beta _{1}\,\beta _{2}\cdots \beta _{s}=\prod _{j=1}^{s}\,\beta _{j}\qquad$

$\alpha \beta =\alpha _{1}\,\alpha _{2}\cdots \alpha _{r}\beta _{r+1}\,\beta _{r+2}\cdots \beta _{r+s}$

dove

$\alpha _{i}=({a_{1}}^{i}\ {a_{2}}^{i}\ldots {a_{l_{i}}}^{i})\quad i=1,2...r$ è un generico li-ciclo ${\textstyle \quad \left(\sum _{i=1}^{r}\,l_{i}=n!\right)}$

$\beta _{j}=({b_{1}}^{j}\ {b_{2}}^{j}\ldots {b_{l_{j}}}^{j})\quad j=1,2...s$ è un generico lj-ciclo ${\textstyle \quad \left(\sum _{j=1}^{s}\,l_{j}=n!\right)}$

da notare la differenza tra le notazioni che indicano la corrispondenza di valori $\alpha (i)\;\beta (j)$ e quella che indica un l_i-ciclo o un l_j-ciclo $\alpha _{i}\;\beta _{j}.$

Per la composizione $\alpha \beta =\alpha \circ \beta$ si possono utilizzare le seguenti tabelle di corrispondenza:

Composizione 2-linea

β	α	γ = α ∘ β
1-β(1)	β(1)-α(β(1))	1-α(β(1))
2-β(2)	β(2)-α(β(2))	2-α(β(2))
3-β(3)	β(3)-α(β(3))	3-α(β(3))
...	...	...
...	...	...
n-β(n)	β(n)-α(β(n))	n-α(β(n))

Composizione ciclica

β			α			γ = α ∘ β
ls-ciclo dx	$\cdots$	l1-ciclo sx	lr-ciclo dx	$\cdots$	l1-ciclo sx
$b_{1}^{s}\rightarrow b_{2}^{s}$	$\cdots$	$b_{1}^{1}\rightarrow b_{2}^{1}$	$a_{1}^{r}\rightarrow a_{2}^{r}$	$\cdots$	$a_{1}^{1}\rightarrow a_{2}^{1}$	$b_{1}^{s}\rightarrow a_{2}^{1}$
→	$\cdots$	→	→	$\cdots$	→	→
$b_{1}^{s}$
$b_{2}^{s}\rightarrow b_{3}^{s}$	$\cdots$	$b_{2}^{1}\rightarrow b_{3}^{1}$	$a_{2}^{r}\rightarrow a_{3}^{r}$	$\cdots$	$a_{2}^{1}\rightarrow a_{3}^{1}$	$b_{2}^{s}\rightarrow a_{3}^{1}$
→	$\cdots$	→	→	$\cdots$	→	→
→	$\cdots$	→	→	$\cdots$	→	→
$b_{l_{s}-1}^{s}$
$b_{l_{s}}^{s}\rightarrow b_{1}^{s}$	$\cdots$	$b_{l_{1}}^{1}\rightarrow b_{1}^{1}$	$a_{l_{r}}^{r}\rightarrow a_{1}^{r}$	$\cdots$	$a_{l_{1}}^{1}\rightarrow a_{1}^{1}$	$b_{l_{s}}^{s}\rightarrow a_{1}^{1}$
→	$\cdots$	→	→	$\cdots$	→	→
$b_{l_{s}}^{s}$

da notare che nella composizione ciclica le righe evidenziate in celeste indicano la chiusura di un ciclo per il risultato. Inoltre i valori delle colonne sono indicativi per quanto riguarda il loro ordine che segue quello del ciclo. Comunque la sequenza iniziale $b_{1}^{s}\rightarrow b_{2}^{s}$ è corretta. Vedere l'esempio per chiarezza.

esempi

Si considerino ad esempio le due permutazioni dell'insieme $X=\{1,2,3,4,5\}.$ Si può scrivere sotto a ogni numero la posizione in cui questo viene spostato:

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

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

$\alpha \beta ={\begin{bmatrix}1&2&3&4&5\\5&4&2&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 $\alpha =(125)(34)$ e $\beta =(123)(4)(5).$

Con la notazione ciclica due permutazioni possono essere composte in modo agevole: ritornando all'esempio si ha $\alpha \circ \beta =(125)(34)(123)(4)(5)=(125)(34)(123)=(15)(243).$ L'implementazione con le tabelle di corrispondenza risulta più chiara:

Composizione 2-linea

β	α	γ = α ∘ β
1-2	2-5	1-5
2-3	3-4	2-4
3-1	1-2	3-2
4-4	4-3	4-3
5-5	5-1	5-1

Composizione ciclica

β	α		γ = α ∘ β
3-ciclo dx	2-ciclo	3-ciclo sx
1 → 2	2 → 2	2 → 5	1 → 5
5 → 5	5 → 5	5 → 1	5 → 1
1
2 → 3	3 → 4	4 → 4	2 → 4
4 → 4	4 → 3	3 → 3	4 → 3
3 → 1	1 → 1	1 → 2	3 → 2
2

Si noti che la composizione ciclica viene effettuata dal ciclo di destra verso il ciclo di 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 (corrisponde alla riga evidenziata in grigio nella tabella). Le righe evidenziate in celeste corrispondono alla chiusura di un ciclo del risultato.

Segno di una permutazione

Definizione

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

$\alpha =(a_{1}\ a_{2}\ldots a_{l-1}\ a_{l})=(a_{1}\ a_{l})(a_{1}\ a_{l-1})\cdots (a_{1}\ a_{2}).$

in particolare si ha

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

che non sono 2-cicli disgiunti. 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.

Proprietà

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

$\operatorname {sgn} (\sigma _{1}\,\sigma _{2})=\operatorname {sgn} (\sigma _{1})\cdot \operatorname {sgn} (\sigma _{2}).$

Ne consegue che $\operatorname {sgn} \left(\sigma \,\sigma ^{-1}\right)=+1.$

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 di indice due del gruppo simmetrico $S(X)=S_{n}$ delle permutazioni dell'insieme $X=\{1,2,\ldots ,n\}$, detto gruppo alternante e indicato con $A(X)=A_{n}.$ 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

Fissiamo un elemento $\sigma \in S_{n}$ nella notazione 2-linea:

$\sigma ={\begin{pmatrix}1&\ldots &i&\ldots &j&\ldots &n\\\sigma (1)&\ldots &\sigma (i)&\ldots &\sigma (j)&\ldots &\sigma (n)\end{pmatrix}}$

consideriamo la coppia $(i,j)\quad 1\leq i<j\leq n$ dicesi inversione per σ se si verifica $\sigma (i)>\sigma (j)$. Supponendo di ottenere r inversioni, allora il segno della permutazione $\sigma$ può essere calcolato tramite la formula seguente:

$\operatorname {sgn} (\sigma )=\epsilon (\sigma )=(-1)^{r}=\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)={\begin{cases}+1\quad \sigma {\text{ pari}}\\-1\quad \sigma {\text{ dispari}}\\\end{cases}}$

Esempi

Tutte le trasposizioni, cioè i 2-cicli del tipo $(a\ b)$, sono dispari.

Ad esempio nel gruppo simmetrico $S_{3}$ abbiamo i seguenti 3 casi possibili per le coppie $(i,j)=(1,2),(1,3),(2,3)$ e in $S_{4}$ diventano 6 casi $(i,j)=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$.

Facciamo vedere che in $S_{3}$ con 6 elementi vi sono:

$\mathrm {id} ,(1\ 2\ 3),(1\ 3\ 2)$ cioè 3 elementi sono pari;

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

Infatti per $\sigma ={\begin{pmatrix}1&2&3\\\sigma (1)&\sigma (2)&\sigma (3)\end{pmatrix}}={\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}=(1\ 3)(2)$ si ottiene

$\epsilon (\sigma )=\prod _{1\leq i<j\leq 3}{\frac {\sigma (j)-\sigma (i)}{j-i}}={\frac {\sigma (2)-\sigma (1)}{2-1}}\cdot {\frac {\sigma (3)-\sigma (1)}{3-1}}\cdot {\frac {\sigma (3)-\sigma (2)}{3-2}}={\frac {2-3}{1}}\cdot {\frac {1-3}{2}}\cdot {\frac {1-2}{1}}=(-1)(-1)(-1)=-1$

quindi possiamo anche dire $r=3\quad \epsilon (\sigma )=(-1)^{r}=(-1)^{3}=-1$. Lo stesso discorso si applica per le restanti riflessioni $\sigma =(1\ 2)(3),(1)(2\ 3)$

per $\sigma ={\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}}=(1\ 2\ 3)$ si ottiene

$\epsilon (\sigma )=\prod _{1\leq i<j\leq 3}{\frac {\sigma (j)-\sigma (i)}{j-i}}={\frac {3-2}{2-1}}\cdot {\frac {1-2}{3-1}}\cdot {\frac {1-3}{3-2}}=(+1)(-1)(-1)=+1$

quindi possiamo anche dire $r=2\quad \epsilon (\sigma )=(-1)^{r}=(-1)^{2}=+1$. Lo stesso discorso si applica per le restanti rotazioni $\sigma =(1\ 3\ 2),(1)(2)(3)$ dove l'ultima è la rotazione nulla (elemento neutro del gruppo S₃). Le tre rotazioni sono tutte pari e formano il sottogruppo normale alterno A₃.

Rappresentazioni

Il numero di permutazioni di n oggetti distinti abbiamo detto essere n!. In questa sezione descriviamo le due principali rappresentazione delle permutazioni. Il numero di permutazioni n con k cicli disgiunti è il Numero di Stirling del primo tipo senza segno, indicato con C(n, k) oppure con C_n,k.

Rappresentazione ciclica

Sia $a_{1},\ldots ,a_{n}$ una successione di elementi distinti di $X$. Un l-ciclo

$\alpha ^{'}=(a_{1}\,a_{2}\ldots \,a_{l})$

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

$\alpha (a_{1})=a_{2},\,\alpha (a_{2})=a_{3},\ldots ,\alpha (a_{l})=a_{1};$

$\alpha (a_{i})=a_{i}\qquad i=(l+1),\ldots ,n$ per gli altri $a.$

quindi si ottiene la permutazione completa

$\alpha =(a_{1}\,a_{2}\ldots \,a_{l})(a_{l+1})\cdots (a_{n})\ \in S_{n}$

L'ordine del ciclo è il numero $l$. 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 $\alpha =(a_{1}\,\ldots \,a_{n})$ e $\beta =(b_{1}\,\ldots \,b_{m})$ sono indipendenti se $a_{i}\neq b_{j}$ per ogni $i$ e $j$. Due cicli indipendenti $\alpha$ e $\beta$ commutano, cioè $\alpha \circ \beta =\beta \circ \alpha$. 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.

Tipo di ciclo

I cicli (inclusi i punti fissi) di una permutazione $\sigma$ di un insieme con n elementi crea una partizione; quindi la lunghezza di questi cicli forma una partizione intera di n, che viene detta tipo di ciclo (o talvolta struttura ciclica o forma del ciclo) di $\sigma$. Ogni punto fisso di $\sigma$ viene detto 1-ciclo, ogni trasposizione si dice 2-ciclo, e così per un generico l-ciclo.

Il tipo di ciclo della permutazione $\beta =(1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)\in S_{8}$ è $(3,2,2,1).$ Questo può anche essere scritto in una forma più compatta come [1¹ 2² 3¹].

Più precisamente, la forma generale è $[1^{k_{1}}\ 2^{k_{2}}\dotsm n^{k_{n}}]$, dove $k_{1},\ldots ,k_{n}$ sono i numeri di cicli di rispettiva lunghezza $1,2,\ldots ,n$. Il numero di permutazioni od elementi del gruppo simmetrico di un dato tipo di ciclo è

$|Co(\sigma )|\ =\ {\frac {n!}{(1^{k_{1}}\ 2^{k_{2}}\dotsm n^{k_{n}})\;(k_{1}!\ k_{2}!\dotsm k_{n}!)}}$

dove con $|Co(\sigma )|$ indichiamo il numero di elementi della classe di coniugio che hanno rappresentante $\sigma$ con struttura ciclica o tipo $[1^{k_{1}}\ 2^{k_{2}}\dotsm n^{k_{n}}]$. Ritornando all'esempio del tipo [1¹ 2² 3¹], si ottiene:

$|Co(\sigma )|\ =\ {\frac {8!}{(1^{1}\ 2^{2}\ 3^{1})\;(1!\ 2!\ 1!)}}={\frac {2\ 3\ 4\ 5\ 6\ 7\ 8}{(4\ 3)\;(2)}}=5\ 6\ 7\ 8=30\ 56=1680$

con elemento rappresentativo $\sigma =(1)(2\ 3)(4\ 5)(6\ 7\ 8)$.

Permutazioni coniugate

In genere, la composizione di permutazioni scritte in notazione ciclica non segue uno schema definito: i cicli della composizione possono essere diversi da quelli prima della fase di composizione. Tuttavia il tipo di ciclo viene preservato nel caso particolare di permutazioni coniugate cioè quando due elementi $\sigma$ e $\tau$ verificano la relazione $\sigma ^{*}=\tau \sigma \tau ^{-1}$. Qui, $\sigma ^{*}$ è l'elemento coniugato di $\sigma$ tramite $\tau$ e si può ottenere la sua notazione ciclica prendendo la notazione ciclica per $\sigma$ e applicando $\tau$ a tutti i singoli cicli di cui è formato $\sigma$ .

Ne consegue che due permutazioni sono coniugate esattamente quando hanno lo stesso tipo di ciclo o stessa classe di coniugio, come visto in precedenza. Ritornando all'esempio $\beta =(1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)$ del tipo [1¹ 2² 3¹], utilizzando l'elemento $\tau =(1\,2\,3\,4\,5\,6\,7\,8\,)$ si ottiene:

$\tau \,=\,{\begin{pmatrix}1&2&3&4&5&6&7&8\\2&3&4&5&6&7&8&1\end{pmatrix}}\,=\,(1\,2\,3\,4\,5\,6\,7\,8\,)$

${\begin{alignedat}{2}\sigma ^{*}&=\tau \sigma \tau ^{-1}=(1\,2\,3\,4\,5\,6\,7\,8\,)\,(1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)\,(8\,7\,6\,5\,4\,3\,2\,1\,)=\\&=\prod _{i=1}^{4}\tau (\sigma _{i})=\tau (1\,2\,5\,)\,\tau (\,3\,4\,)\,\tau (6\,8\,)\,\tau (\,7\,)=\\&=(\tau (1)\,\tau (2)\,\tau (5)\,)\,(\tau (3)\,\tau (4)\,)\,(\tau (6)\,\tau (8)\,)\,\tau (7)\,=(2\,3\,6\,)\,(4\,5\,)\,(7\,1\,)\,(\,8\,)\\\end{alignedat}}$

Ordine e parità

L'ordine di una permutazione $\sigma$ è il più piccolo intero positivo m tale che $\sigma ^{m}=\mathrm {id}$. Corrisponde al minimo comune multiplo delle lunghezze dei suoi cicli. Cioè se $\sigma$ ha struttura ciclica o tipo $[1^{k_{1}}\ 2^{k_{2}}\dotsm n^{k_{n}}]$ si definisce m come:

$m={\text{mcm}}(1,\,2,\ldots ,n)$

Ad esempio $\sigma =(\,1\,3\,2)(\,4\,5\,)$ ha struttura ciclica $[2^{1}\,3^{1}]$ ed ammette ordine $o(\sigma )={\text{mcm}}(3,2)=2\cdot 3=6$.

Abbiamo già visto che ogni permutazione di un insieme finito può essere espressa come il prodotto di trasposizioni. Sebbene possano esistere molte espressioni di questo tipo per una data permutazione, si dimostra che contengono tutte un numero pari di trasposizioni oppure un numero dispari di trasposizioni. Pertanto tutte le permutazioni possono essere classificate come pari o dispari a seconda di questo numero.

Questo risultato può essere esteso in modo da assegnare un segno, scritto $\operatorname {sgn} \sigma$, ad ogni permutazione. $\operatorname {sgn} \sigma =+1$ se $\sigma$ è pari e $\operatorname {sgn} \sigma =-1$ se $\sigma$ è dispari. Questo argomento è stato già trattato nella sezione segno di una permutazione e viene riportato per completezza.

Rappresentazione con matrici

Una matrice di permutazione è una matrice n × n che ha esattamente un elemento in ogni colonna e in ogni riga, e tutte le altre sono nulle. Esistono diverse convenzioni per assegnare una matrice di permutazione a una permutazione dell'insieme {1, 2, ..., n}. Ne riportiamo i due più comuni in letteratura.

1. Un metodo naturale data la permutazione:

   $\sigma ={\begin{pmatrix}1&2&\ldots &j&\ldots &n\\\sigma (1)&\sigma (2)&\ldots &\sigma (j)&\ldots &\sigma (n)\end{pmatrix}}$

   consiste nell'associare una matrice detta $M_{\sigma }$ definita come segue:

   $M_{\sigma }\ (i,j)={\begin{cases}1,&{\text{se }}i=\sigma (j)\\0&{\text{se }}i\neq \sigma (j)\end{cases}}$

   Questa convenzione ha due proprietà:
   • il prodotto delle matrici e delle permutazioni è nello stesso ordine, cioè $M_{\sigma }M_{\pi }=M_{\sigma \circ \pi }$ per ogni σ e π.
   • se ${\bf {e}}_{i}$ rappresenta il vettora colonna standard $n\times 1$ (il vettore con e_i = 1 e all other entries equal to 0), then $M_{\sigma }{\bf {e}}_{i}={\bf {e}}_{\sigma (i)}$.
2. L'altra convenzione è quella inversa, data la permutazione σ viene associata la matrice $P_{\sigma }=(M_{\sigma })^{-1}=(M_{\sigma })^{T}$ cioè:

   $P_{\sigma }\ (i,j)={\begin{cases}1,&{\text{se }}j=\sigma (i)\\0&{\text{se }}j\neq \sigma (i)\end{cases}}$

   Le precedenti proprietà diventano:
   • le matrici di permutazione si moltiplicano nell'ordine opposto rispetto alle composizioni di due permutazioni, cioè$P_{\sigma }P_{\pi }=P_{\pi \circ \sigma }\forall \sigma ,\ \pi$.
   • la matrice di permutazione permuta gli indici di un vettore riga standard $1\times n$ con simbolo $({\bf {e}}_{i})^{T}$: quindi si ha $({\bf {e}}_{i})^{T}P_{\sigma }=({\bf {e}}_{\sigma (i)})^{T}$.

Esempi

La tabella di Cayley del gruppo simmetrico $S_{3}$ viene implementata con la rappresentazione a matrice dove la legge di composizione corrisponde ad una moltiplicazione di matrici.

Consideriamo la permutazione $\sigma ={\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}}=(1\ 2\ )(3)$, allora la matrice $M_{\sigma }$ ha i valori $(\sigma (j),\ j)=(2,1)=(1,2)=(3,3)=1$ e le posizioni restanti sono nulle, cioè

$M_{\sigma }={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}$

consideriamo un'altra permutazione $\pi ={\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}}=(1\ 2\ 3)$ e la corrispondente matrice

$M_{\pi }={\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}$.

Allora possiamo effettuare la composizione ciclica $\sigma \circ \pi =(1\ 2\ )(3)(1\ 2\ 3)=(1\ 2\ )(1\ 2\ 3)=(1)(2\ 3)$, e la corrispondente composizione delle matrici diventa:

$M_{\sigma }M_{\pi )}={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}={\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}=M_{\sigma \circ \pi }.$

I vettori colonna associati a $\sigma$ sono

${\bf {e}}_{1}={\begin{pmatrix}1\\0\\0\\\end{pmatrix}}\quad {\bf {e}}_{2}={\begin{pmatrix}0\\1\\0\\\end{pmatrix}}\quad {\bf {e}}_{3}={\begin{pmatrix}0\\0\\1\\\end{pmatrix}}$

L'altro esempio visualizza la tabella di Cayley in questa sezione con le matrici di permutazioni per 3 elementi.

Permutazioni di insiemi totalmente ordinati

In some applications, the elements of the set being permuted will be compared with each other. This requires that the set S has a total order so that any two elements can be compared. The set {1, 2, ..., n} is totally ordered by the usual "≤" relation and so it is the most frequently used set in these applications, but in general, any totally ordered set will do. In these applications, the ordered arrangement view of a permutation is needed to talk about the positions in a permutation.

There are a number of properties that are directly related to the total ordering of S.

Ascendente, discendente, itinerario ed eccedente

Un salita o ascesa di una permutazione σ di n è qualsiasi posizione i < n dove il valore successivo è maggiore di quello corrente. Cioè, se σ = σ₁σ₂...σ_n, allora i è ascendente di σ_i < σ_i+1.

For example, the permutation 3452167 has ascents (at positions) 1, 2, 5, and 6.

Similarly, a descent is a position i < n with σ_i > σ_i+1, so every i with $1\leq i<n$ either is an ascent or is a descent of σ.

Un itinerario ascendente of a permutation is a nonempty increasing contiguous subsequence of the permutation that cannot be extended at either end; it corresponds to a maximal sequence of successive ascents (the latter may be empty: between two successive descents there is still an ascending run of length 1). By contrast an increasing subsequence of a permutation is not necessarily contiguous: it is an increasing sequence of elements obtained from the permutation by omitting the values at some positions. For example, the permutation 2453167 has the ascending runs 245, 3, and 167, while it has an increasing subsequence 2367.

If a permutation has k − 1 descents, then it must be the union of k ascending runs.

The number of permutations of n with k ascents is (by definition) il numero euleriano $\textstyle \left\langle {n \atop k}\right\rangle$; questo è anche il numero di permutazioni di n con k discese. Some authors however define the Eulerian number $\textstyle \left\langle {n \atop k}\right\rangle$ as the number of permutations with k ascending runs, which corresponds to k − 1 descents.

An exceedance of a permutation σ₁σ₂...σ_n is an index j such that σ_j > j. If the inequality is not strict (that is, σ_j ≥ j), then j is called a weak exceedance. The number of n-permutations with k exceedances coincides with the number of n-permutations with k descents.

Lemma di transizione di Foata

There is a relationship between the one-line notation and the canonical cycle notation. Consider the permutation $(\,2\,)(\,3\,1\,)$ in canonical cycle notation; if we simply remove the parentheses, we obtain the permutation $231$ in one-line notation. Foata's transition lemma establishes the nature of this correspondence as a bijection on the set of n-permutations (to itself).Template:Sfn Richard P. Stanley calls this correspondence the fundamental bijection.

Let $f(p)=q$ be the parentheses-erasing transformation which returns $q$ in one-line notation when given $p$ in canonical cycle notation. As stated, $f$ operates by simply removing all parentheses. The operation of the inverse transformation, $f^{-1}(q)=p$, which returns $p$ in canonical cycle notation when given $q$ in one-line notation, is a bit less intuitive. Given the one-line notation $q=q_{1}q_{2}\cdots q_{n}$, the first cycle of $p$ in canonical cycle notation must start with $q_{1}$. As long as the subsequent elements are smaller than $q_{1}$, we are in the same cycle of $p$. The second cycle of $p$ starts at the smallest index $j$ such that $q_{j}>q_{1}$. In other words, $q_{j}$ is larger than everything else to its left, so it is called a left-to-right maximum. Every cycle in the canonical cycle notation starts with a left-to-right maximum.Template:Sfn

For example, in the permutation $q=312548976$, 5 is the first element larger than the starting element 3, so the first cycle of $p$ must be $(\,3\,1\,2\,)$. Then 8 is the next element larger than 5, so the second cycle is $(\,5\,4\,)$. Since 9 is larger than 8, $(\,8\,)$ is a cycle by itself. Finally, 9 is larger than all the remaining elements to its right, so the last cycle is $(\,9\,7\,6\,)$. Concatenating these 4 cycles gives $p=(\,3\,1\,2\,)(\,5\,4\,)(\,8\,)(\,9\,7\,6\,)$ in canonical cycle notation.

The following table shows both $q$ and $p$ for the six permutations of $123$. The bold side of each equality shows the permutation using its designated notation (one-line notation for $q$ and canonical cycle notation for $p$) while the non-bold side shows the same permutation in the other notation. Comparing the bold side of each column of the table shows the parenthesis removing/restoring operation of Foata's bijection, while comparing the same side of each column (for example, the LHS) shows which permutations are mapped to themselves by the bijection (first 3 rows) and which are not (last 3 rows).

$q=f(p)$	$p=f^{-1}(q)$
$\mathbf {123} =(\,1\,)(\,2\,)(\,3\,)$	$123=\mathbf {(\,1\,)(\,2\,)(\,3\,)}$
$\mathbf {132} =(\,1\,)(\,3\,2\,)$	$132=\mathbf {(\,1\,)(\,3\,2\,)}$
$\mathbf {213} =(\,2\,1\,)(\,3\,)$	$213=\mathbf {(\,2\,1\,)(\,3\,)}$
$\mathbf {231} =(\,3\,1\,2\,)$	$321=\mathbf {(\,2\,)(\,3\,1\,)}$
$\mathbf {312} =(\,3\,2\,1\,)$	$231=\mathbf {(\,3\,1\,2\,)}$
$\mathbf {321} =(\,2\,)(\,3\,1\,)$	$312=\mathbf {(\,3\,2\,1\,)}$

As a first corollary, the number of n-permutations with exactly k left-to-right maxima is also equal to the signless Stirling number of the first kind, $c(n,k)$. Furthermore, Foata's mapping takes an n-permutation with k-weak exceedances to an n-permutations with k − 1 ascents.Template:Sfn For example, (2)(31) = 321 has two weak exceedances (at index 1 and 2), whereas f(321) = 231 has one ascent (at index 1; that is, from 2 to 3).

Inversioni

Nel 15 puzzle l'obiettivo è disporre i quadrati in ordine crescente. Le posizioni iniziali che hanno un numero dispari di inversioni sono impossibili da risolvere.

An inversion of a permutation σ is a pair Template:Math of positions where the entries of a permutation are in the opposite order: $i<j$ and $\sigma _{i}>\sigma _{j}$.Template:Sfn So a descent is just an inversion at two adjacent positions. For example, the permutation σ = 23154 has three inversions: (1, 3), (2, 3), and (4, 5), for the pairs of entries (2, 1), (3, 1), and (5, 4).

Sometimes an inversion is defined as the pair of values Template:Math whose order is reversed; this makes no difference for the number of inversions, and this pair (reversed) is also an inversion in the above sense for the inverse permutation σ⁻¹. The number of inversions is an important measure for the degree to which the entries of a permutation are out of order; it is the same for σ and for σ⁻¹. To bring a permutation with k inversions into order (that is, transform it into the identity permutation), by successively applying (right-multiplication by) adjacent transpositions, is always possible and requires a sequence of k such operations. Moreover, any reasonable choice for the adjacent transpositions will work: it suffices to choose at each step a transposition of i and i + 1 where i is a descent of the permutation as modified so far (so that the transposition will remove this particular descent, although it might create other descents). This is so because applying such a transposition reduces the number of inversions by 1; as long as this number is not zero, the permutation is not the identity, so it has at least one descent. Bubble sort and insertion sort can be interpreted as particular instances of this procedure to put a sequence into order. Incidentally this procedure proves that any permutation σ can be written as a product of adjacent transpositions; for this one may simply reverse any sequence of such transpositions that transforms σ into the identity. In fact, by enumerating all sequences of adjacent transpositions that would transform σ into the identity, one obtains (after reversal) a complete list of all expressions of minimal length writing σ as a product of adjacent transpositions.

The number of permutations of n with k inversions is expressed by a Mahonian number,Template:Sfn it is the coefficient of X^k in the expansion of the product

$$\prod _{m=1}^{n}\sum _{i=0}^{m-1}X^{i}=1\left(1+X\right)\left(1+X+X^{2}\right)\cdots \left(1+X+X^{2}+\cdots +X^{n-1}\right),$$

which is also known (with q substituted for X) as the q-factorial [n]_q! . The expansion of the product appears in Necklace (combinatorics).

Let $\sigma \in S_{n},i,j\in \{1,2,\dots ,n\}$ such that $i<j$ and $\sigma (i)>\sigma (j)$. In this case, say the weight of the inversion $(i,j)$ is $\sigma (i)-\sigma (j)$. Kobayashi (2011) proved the enumeration formula

$$\sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{ is bigrassmannian}}\}$$

where $\leq$ denotes Bruhat order in the symmetric groups. This graded partial order often appears in the context of Coxeter groups.

Storia

Le permutazioni dette esagrammi venivano usate in Cina nell'I Ching (Pinyin: Yi Jing) già nel 1000 a.C..

In Grecia, Plutarco scrisse che Senocrate di Calcedonia (396–314 a.C.) scoprì il numero di sillabe diverse possibili della lingua greca. Questo sarebbe stato il primo tentativo non documentato di risolvere un difficile problema di permutazioni e combinazioni.

Al-Khalil (717–786), un matematico arabo e crittografo, ha scritto il Libro dei Messaggi Crittografici. Contiene il primo utilizzo di permutazioni e combinazioni, per elencare tutte le possibili parole arabe con e senza vocali.

The rule to determine the number of permutations of n objects was known in Indian culture around 1150 AD. The Lilavati by the Indian mathematician Bhaskara II contains a passage that translates to:

The product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures.

In 1677, Fabian Stedman described factorials when explaining the number of permutations of bells in change ringing. Starting from two bells: "first, two must be admitted to be varied in two ways", which he illustrates by showing 1 2 and 2 1. He then explains that with three bells there are "three times two figures to be produced out of three" which again is illustrated. His explanation involves "cast away 3, and 1.2 will remain; cast away 2, and 1.3 will remain; cast away 1, and 2.3 will remain". He then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three. Effectively, this is a recursive process. He continues with five bells using the "casting away" method and tabulates the resulting 120 combinations. At this point he gives up and remarks:

Now the nature of these methods is such, that the changes on one number comprehends the changes on all lesser numbers, ... insomuch that a compleat Peal of changes on one number seemeth to be formed by uniting of the compleat Peals on all lesser numbers into one entire body;

Stedman widens the consideration of permutations; he goes on to consider the number of permutations of the letters of the alphabet and of horses from a stable of 20.

A first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, when Joseph Louis Lagrange, in the study of polynomial equations, observed that properties of the permutations of the roots of an equation are related to the possibilities to solve it. This line of work ultimately resulted, through the work of Évariste Galois, in Galois theory, which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals. In modern mathematics, there are many similar situations in which understanding a problem requires studying certain permutations related to it.

Permutations played an important role in the cryptanalysis of the Enigma machine, a cipher device used by Nazi Germany during World War II. In particular, one important property of permutations, namely, that two permutations are conjugate exactly when they have the same cycle type, was used by cryptologist Marian Rejewski to break the German Enigma cipher in turn of years 1932-1933.

Note

Libri

Riviste

Fonti web

Bibliografia

• Michael Artin, Algebra, Bollati Boringhieri, 1997, ISBN 88-339-5586-9.
• Israel Nathan Herstein, Algebra, Editori Riuniti, 2003, ISBN 88-359-5479-7.
• (EN) Neal H. McCoy, Introduction To Modern Algebra, Revised Edition, Boston, Allyn and Bacon, 1968, LCCN 68015225.
• (EN) Norman L. Biggs, Discrete Mathematics, 2ª ed., Oxford, OUP, 2002, ISBN 978-0-19-850717-8.
• (EN) Miklós Bóna, Combinatorics of Permutations, 2ª ed., Boca Raton, FL, Chapman & Hall (CRC Press), 2012, ISBN 978-1-4398-5051-0.
• (EN) Miklós Bóna, Combinatorics of Permutations, 1ª ed., Boca Raton, Chapman & Hall (CRC Press), 2004, ISBN 978-1-58488-434-7.
• (EN) Humphreys J. F., IX. Permutations, in A course in group theory, 1ª ed., Oxford, OUP, 1996, ISBN 978-0-19-853459-4.
• (EN) Marshall Jr. Hall, The Theory of Groups, 1ª ed., Chelsea Pub Co;, 1999, ISBN 978-0-8218-1967-8.
• (EN) Fabian Stedman, Campanalogia, Londra, ASCY, 1677.

Voci correlate

• Combinazione
• Convoluzione
• Dismutazione (matematica)
• Disposizione
• Ordine ciclico
• Permutazione alternata
• Probabilità
• Statistica
• Superpermutazione