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.

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

$\alpha ={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}},\qquad \beta ={\begin{pmatrix}1&2&3&4&5\\2&3&1&4&5\end{pmatrix}},\qquad \alpha \circ \beta ={\begin{pmatrix}1&2&3&4&5\\5&4&2&3&1\end{pmatrix}}.$

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.

Notazioni

Ci sono diverse notazioni per scrivere una permutazione. Qui definiamo quelle principali. La "notazione ciclica" è la scelta più comune, poiché è compatta e mostra chiaramente la struttura della permutazione. Questo articolo utilizzerà tale notazione se non diversamente specificato.

Notazione 2-linea

La notazione 2-linea di Cauchy lista gli elementi di X nella prima riga, e l'immagine di tali elementi nella seconda riga. Cioè:

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

Pe esempio, sia X = {1, 2, 3, 4, 5, 6} e consideriamo una permutazione di tali numeri tramite la funzione

$\sigma (1)=2,\ \ \sigma (2)=6,\ \ \sigma (3)=5,\ \ \sigma (4)=4,\ \ \sigma (5)=3,\ \ \sigma (6)=1$

in tale notazione diventa

$\sigma ={\begin{pmatrix}1&2&3&4&5&6\\2&6&5&4&3&1\end{pmatrix}}.$

Gli elementi di X possono apparire in qualsiasi ordine nella prima riga, quindi questa permutazione può essere scritta in molti modi:

$\sigma ={\begin{pmatrix}2&3&4&5&6&1\\6&5&4&3&1&2\end{pmatrix}}={\begin{pmatrix}6&5&4&3&2&1\\1&3&4&5&6&2\end{pmatrix}}=\cdots .$

Notazione 1-linea

Se esiste un ordine "naturale" per gli elementi di X, cioè $x_{1},x_{2},\ldots ,x_{n}$, quindi si usa questa scrittura per la prima riga nella notazione 2-linea:

$\sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}.$

Fatte queste premesse, possiamo omettere la prima riga e scrivere la permutazione in notazione detta 1-linea come

$\sigma =\sigma (x_{1})\;\sigma (x_{2})\;\sigma (x_{3})\;\cdots \;\sigma (x_{n})$,

cioè come disposizione ordinata degli elementi di X.

Bisogna fare attenzione a distinguere la notazione 1-linea dalla notazione ciclica descritta di seguito: un uso comune è omettere le parentesi o usare le parentesi quadre o utilizzare le virgole per separare queste voci solo se alcune hanno due o più cifre, mentre si utilizzano parentesi tonde per la notazione ciclica. La notazione 1-linea viene anche detta una rappresentazione parola.

L'esempio visto in tale notazione si scrive:

$\sigma ={\begin{pmatrix}1&2&3&4&5&6\\2&6&5&4&3&1\end{pmatrix}}=265431.$

Questa forma compatta è comune nella combinatoria elementare e nell'informatica. In particolare è utilizzata in applicazioni dove le permutazioni devono essere confrontate tra più grande o più piccolo rispetto all'ordine lessicografico.

Notazione ciclica

La notazione ciclica descrive l'effetto dell'applicazione ripetuta della permutazione sugli elementi dell'insieme X, con un'orbita cioè un sottoinsieme ${\textstyle X_{i}\subseteq X}$ chiamata un "ciclo". La permutazione è scritta come un elenco di cicli; poiché i cicli distinti coinvolgono sottoinsiemi disgiunti di elementi di X, questa viene definita "scomposizione in cicli disgiunti".

Per scrivere la permutazione $\sigma$ in notazione ciclica si procede come segue:

1. Aprire una parentesi tonda seguita da un elemento qualsiasi $x_{11}\in X$: $(\,x_{11}$
2. Tracciare l'orbita di x₁₁, annotando i valori delle successive applicazioni di $\sigma$:

   $(\,x_{11},\sigma (x_{11}),\sigma (\sigma (x_{11})),\ldots =(\,x_{11},\sigma (x_{11}),\sigma ^{2}(x_{11}),\ldots$

3. Ripetere fino a quando si verifica $\sigma ^{l_{1}-1}(x_{11})=x_{11}$ e chiudere le parentesi senza ripetere x₁₁:

   $(\,x_{1}\,\sigma (x_{1})\,\sigma ^{2}(\sigma (x_{1}))\,\ldots ,\sigma ^{l_{1}-1}(x_{1}))$ detto l₁-ciclo

4. Prendiamo un elemento x₂₁ of X che non fa parte dell'insieme $X_{1}=\{\,x_{11},\ \sigma (x_{11}),\ \sigma ^{2}(x_{11}),\ldots ,\sigma ^{l_{1}-1}(x_{11})\}$, e ripetere il processo al punto 1: $(\,x_{11},\sigma (x_{11}),\sigma (\sigma (x_{11})),\ldots \,)(\,x_{21}\,\ldots \,)$
5. Ripetere dal punto 1 fino a quando tutti gli elementi di X sono scritti in cicli, cioè:

   $\sigma =\sigma _{1}\cdots \sigma _{r}=\left(x_{11}\ x_{12}\ \ldots \ x_{1l_{1}}\right)\cdots \left(x_{r1}\ x_{r2}\ \ldots \ x_{rl_{r}}\right)=\prod _{i=1}^{r}\sigma _{i}$

Inoltre, è comune omettere gli 1-ciclo in quanto si possono dedurre: ogni elemento x che non fa parte di tutti i cicli ottenuti, in questi casi si assume implicitamente che $\sigma (x)=x$.

Seguendo la convenzione di omettere gli 1-ciclo, si può interpretare un ciclo individuale come una permutazione che fissa tutti gli elementi non presenti nel ciclo (una permutazione ciclica avente un solo ciclo di lunghezza maggiore di 1). Allora la lista di cicli disgiunti si può interpretare come composizione di queste permutazioni cicliche. Formalmente una permutazione ciclica è un solo l-ciclo ed (n-l+1) 1-ciclo. Prendiamo un l_i-ciclo

$\sigma _{i}=(s_{i1}\,s_{i2}\ldots \,s_{i1_{i}})$

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

$\sigma (s_{i1})=s_{i2},\,\sigma (s_{i2})=s_{i3},\ldots ,\sigma (s_{i1_{i}})=s_{i1};$

$\sigma (x_{ij})=x_{ij}\qquad j=(l_{i}+1),\ldots ,n$ per gli altri $s.$

quindi si ottiene la permutazione ciclica

$\sigma _{i}=(s_{i1}\,s_{i2}\ldots \,s_{i1_{i}})(x_{il_{i+1}})\cdots (x_{in})\ \in S_{n}$

L'ordine del ciclo è il numero $l_{i}$.

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 o disgiunti 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.

Riprendiamo l'esempio, la permutazione 1-linea $\sigma =265431$ in notazione ciclica diventa:

$\sigma =(1~2~6)(3~5)(4)=(1~2~6)(3~5).$

Per quanto detto, possiamo esplicitarla come composizione di permutazioni cicliche

$\sigma _{1}=(1~2~6)=(1~2~6)(3)(4)(5),\quad \sigma _{2}=(3~5)=(3~5)(1)(2)(4)(6)\quad \sigma =\sigma _{1}\sigma _{2}.$

Mentre le permutazioni in generale non commutano, i cicli disgiunti lo fanno; quindi

$\sigma =(1~2~6)(3~5)=(3~5)(1~2~6)$

inoltre, ogni ciclo può essere riscritto partendo da elementi in posizioni diverse; cioè

$\sigma _{1}=(1~2~6)=(2~6~1)=(6~2~1)\quad \sigma _{2}=(5~3)=(3~5)$

Pertanto si possono scrivere i cicli disgiunti di una data permutazione in molti modi diversi. Una caratteristica utile della notazione ciclica è che la permutazione inversa è data dall'inversione dell'ordine degli elementi in ogni ciclo. Quindi

$\sigma ^{-1}=\left({\vphantom {A^{2}}}(1~2~6)(3~5)\right)^{-1}=(6~2~1)(5~3).$

Riassumendo l'esempio con le notazioni descritte si ha:

$\sigma ={\begin{pmatrix}1&2&3&4&5&6\\2&6&5&4&3&1\end{pmatrix}}=265431=(1~2~6)(4)(3~5)=(4)(5~3)(6~1~2).$

l'ultima scrittura è la notazione ciclica canonica descritta di seguito.

Notazione ciclica canonica

Nell'ambito combinatorio è utile definire un certo ordine per gli elementi che compongono un singolo ciclo e un ordine tra i cicli disgiunti in cui si decompone la permutazione $\sigma$. Tale scelta di ordinamento viene detta notazione ciclica canonica. Consideriamo una generica permutazione formata da r cicli:

$\sigma \ =\underbrace {\sigma _{1}\ \sigma _{2}\cdots \sigma _{r}\ } _{l_{i}{\mbox{-cicli}}}=\prod _{i=1}^{r}\sigma _{i}\qquad \sum _{i=1}^{r}l_{i}\ =\ n\qquad {\mbox{tipo = }}(l_{1},l_{2},\ldots ,l_{r})\qquad o(\sigma )=\operatorname {mcm} \ (l_{1},l_{2},\ldots ,l_{r})$

e consideriamo una particolare scrittura tra le tante equivalenti con le seguenti due proprietà

• in un singolo ciclo l'elemento maggiore compare all'inizio del ciclo, cioè

  $\sigma _{i}=(s_{i1}\ s_{i2}\ \cdots \ s_{il_{i}})=(s_{i1}\ \sigma _{i}(s_{i1})\ \cdots \ \sigma _{i}^{l_{i}-1}(s_{i1}))\quad :s_{i1}=\operatorname {max} X_{i}=\operatorname {max} \{s_{i1},s_{i2},\ldots ,s_{il_{i}}\}$

• i cicli sono ordinati in modo crescente rispetto al primo elemento di ogni singolo ciclo, non omettendo gli 1-ciclo, cioè

  $\sigma \ =\sigma _{1}\ \sigma _{2}\cdots \sigma _{r}\ =(s_{11}\ s_{12}\ \cdots \ s_{1l_{1}})(s_{21}\ s_{22}\ \cdots \ s_{2l_{2}})\cdots (s_{r1}\ s_{r2}\ \cdots \ s_{rl_{r}})\;:s_{11}<s_{21}<\cdots <s_{r1}$

Ad esempio, consideriamo l'insieme $X=\{1,\ 2,\ldots ,\ 9\}\quad |X|=9$ e il gruppo S₉ che agisce su esso tramite la permutazione

$\sigma \ ={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\3&7&5&9&1&6&8&2&4\end{pmatrix}}=(1\ 3\ 5)(2\ 7\ 8)(4\ 9)(6)\ =\ 375916824\qquad {\mbox{tipo = }}(1,2,3,3)\qquad o(\sigma )=\operatorname {mcm} \ (2,3)=6$

per poter ottenere la notazione ciclica canonica occorre

• in ogni ciclo l'elemento maggiore compare all'inizio del ciclo, cioè quelli segnati

  ${\begin{aligned}(1\ 3\ 5)&=(3\ 5\ 1)=({\underline {5}}\ 1\ 3)&5&=\operatorname {max} \{1,3,5\}\\(2\ 7\ 8)&=(7\ 8\ 2)=({\underline {8}}\ 2\ 7)&8&=\operatorname {max} \{2,7,8\}\\(4\ 9)&=({\underline {9}}\ 4)&9&=\operatorname {max} \{4,9\}\\(6)&=({\underline {6}})\\\end{aligned}}$

• i cicli vanno ordinati in modo crescente rispetto agli elementi segnati di ogni singolo ciclo

  $({\underline {5}}\ 1\ 3)({\underline {6}})({\underline {8}}\ 2\ 7)({\underline {9}}\ 4)$

Alcuni autori chiamano tale notazione rappresentazione standard di una permutazione, altri la forma standard . Il matematico russo Sergey Kitaev usa il termine forma standard, ma inverte entrambe le proprietà; cioè, ogni ciclo inizia col suo elemento minimo, e i cicli sono ordinati in modo decrescente rispetto al primo elemento di ogni singolo ciclo.

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

Proprietà

Il numero di permutazioni di n oggetti distinti abbiamo detto essere n!.

Cicli e punti fissi

Il numero di permutazioni di n oggetti distinti che hanno k cicli disgiunti è il Numero di Stirling del primo tipo senza segno, cioè

$s(n,\ k)\ =\ \left[{\begin{matrix}n\\k\end{matrix}}\right]\quad n,k\in \mathbb {Z} ^{+}\ 1\leqslant k\leqslant n$

qualche testo lo denota C(n, k) oppure C_n,k.

Il valore delle dismutazioni parziali, anche detto numero di rincontri, indica il numero di permutazioni di n elementi con k punti fissi e si denota

$f(n,\ k)\ =\ D(n,k)\quad n,k\in \mathbb {Z} ^{+}\quad 0\leqslant k\leqslant n$

dove l'insieme permutato è { 1, ..., n }.

Tipo o struttura

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.

Più precisamente, la forma generale di una struttura ha notazioni

$[1^{k_{1}}\ 2^{k_{2}}\dotsm n^{k_{n}}]\ =\ (\underbrace {1,\ldots ,1} _{k_{1}},\ \underbrace {2,\ldots ,2} _{k_{2}},\ldots ,\ \underbrace {n,\ldots ,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}}]$.

Ad esempio 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¹]. Mentre per il numero di coniugati o dello stesso tipo, 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)$.

Ordine

L'ordine di una permutazione $\sigma$ si definisce come

$\sigma ^{o(\sigma )}=\mathrm {id} =(1)(2)\ldots (n)$.

Corrisponde al minimo comune multiplo delle lunghezze dei suoi cicli. Cioè se $\sigma$ ha struttura ciclica o tipo $[l_{1}^{k_{1}}\ l_{2}^{k_{2}}\dotsm l_{r}^{k_{r}}]$ si definisce m come:

$o(\sigma )\ =\ {\text{mcm}}(l_{1},\,l_{2},\ldots ,l_{r})$

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

Segno o parità

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.

Segno del prodotto di permutazioni

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 alterno

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

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. Tenendo conto del tipo generalizzato con le molteplicità, cioè $k_{1}$ cicli di tipo $l_{1}$-ciclo ... si ha

$\operatorname {sgn} (\sigma )\ ={[\operatorname {sgn} (\sigma _{1})]}^{k_{1}}\ {[\operatorname {sgn} (\sigma _{2})]}^{k_{2}}\cdots {[\operatorname {sgn} (\sigma _{r})]}^{k_{r}}.$

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

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

Permutazioni in combinatoria

In certe aree matematiche, come nella combinatoria numerica, gli elementi dell'insieme da permutare si devono confrontare tra loro. Quindi è necessario che l'insieme X sia totalmente ordinato. Ad esempio L' insieme X = {1, 2,..., n} è un insieme ordinato tramite la relazione d'ordine "≤" ed è quello più utilizzato in queste applicazioni, ma in genere, si può utilizzare qualsiasi insieme purchè sia totalmente ordinato. In tali aree, avere una disposizione ordinata di una permutazione è necessario per il concetto di posizioni in una permutazione.

Vi sono alcune proprietà legate all'ordinamento totale dell'insieme X, nel seguito utilizzeremo la notazione 1-linea

$\sigma ={\begin{pmatrix}1&2&3&\cdots &n\\\sigma (1)&\sigma (2)&\sigma (3)&\cdots &\sigma (n)\end{pmatrix}}=\sigma (1)\sigma (2)\sigma (3)\cdots \sigma (n)$

Ascendente, discendente, itinerario, eccedente e record

Una salita o ascesa di una permutazione σ di n elementi è qualsiasi posizione i ≤ n dove il valore successivo è maggiore di quello corrente. Cioè, se σ = σ(1)σ(2)...σ(i) σ(i+1) ...σ(n), allora i è detto ascendente se si verifica σ(i) < σ(i+1). Possiamo introdurre l'insieme degli elementi ascendenti come

$\operatorname {asc} (\sigma )=\operatorname {A} (\sigma )=\{i\in \mathbb {Z} \mid \sigma (i)<\sigma (i+1)\ ,\quad 1\leqslant i\leqslant (n-1),\ i=n;\sigma \in S_{n}\}$

analogamente una scesa o discesa è una posizione i < n per cui si ha σ(i) > σ(i+1), quindi l'insieme degli elementi discendenti

$\operatorname {des} (\sigma )=\operatorname {D} (\sigma )=\{i\in \mathbb {Z} \mid \sigma (i)>\sigma (i+1)\ ,\quad 1\leqslant i\leqslant n-1\}$

cioè ogni i con $1\leq i\leq n$ può essere un ascendente o un discendente di σ.

Un itinerario ascendente è una sottosuccessione contigua crescente e non vuota della permutazione che non può essere estesa a nessuna delle due estremità; corrisponde ad una sequenza massima di salite successive. Una siffatta sottosuccessione può essere vuota (lunghezza 0), oppure avere due discese successive per cui ha lunghezza 1 e infine avere lunghezza massima n. Mentre una sottosuccessione crescente non è vincolata ad essere contigua: cioè una successione crescente di elementi ottenuti dalla permutazione omettendo i valori in alcune posizioni. Una analoga definizione si ha per un itinerario discendente e una sottosuccessione decrescente. Indichiamo l'insieme degli itinerari crescenti e decrescenti con i simboli $\operatorname {ascrun} (\sigma )\ \operatorname {desrun} (\sigma )$.

Una permutazione con k − 1 discese, allora dev'essere l'unione di k ascending runs. Il numero di permutazioni di n elementi con k ascendenti è, per definizione il numero euleriano

$\left\langle {n \atop k}\right\rangle =A(n,k)=\sum _{i=0}^{k}(-1)^{i}\ {\binom {n+1}{i}}\ (k-i)^{n}$;

e indica pure il numero di permutazioni di n con k discendenti. Alcuni autori tuttavia lo definiscono il numero di permutazioni con k ascending runs, che corrisponde a k − 1 discendenti.

Un eccedente di una permutazione σ di n elementi è un indice j per cui si ha σ_j > j. Se la disuguaglianza non è stretta (cioè, σ_j ≥ j), allora j viene detto eccedente debole. Il numero di n-permutazioni con k eccedenti coincide con il numero di n-permutazioni con k discese. Quindi ha senso considerare l'insieme eccedenza debole come

$\operatorname {E} (\sigma )=\{i\in \mathbb {Z} \mid \sigma (i)\geqslant i\ ,\quad 1\leqslant i\leqslant n\}$

Un record o massimo sx-dx (abbreviato in lrm per left-to-right maximum) della permutazione σ è un elemento i che verifica σ(j) < σ(i) per ogni j < i. Indichiamo l'insieme degli lrm con

$\operatorname {lrm} (\sigma )\ =\{i\in \mathbb {Z} \mid \sigma (j)<\sigma (i)\ ,\quad \forall j<i\quad i,j=1\ldots n\}$.

Esempio: consideriamo la seguente permutazione:

$S_{7}\ni \sigma ={\begin{pmatrix}1&2&3&4&5&6&7\\3&4&5&2&1&6&7\\\end{pmatrix}}=(135)(24)(6)(7)=3452167$

ammette i due insiemi

${\begin{aligned}\operatorname {asc} (\sigma )&=\{1,2,5,6,7\}&|A(\sigma )|=5\\\operatorname {des} (\sigma )&=\{3,4\}&|D(\sigma )|=2\\\end{aligned}}$

il numero di permutazioni tra le $|S_{7}|=5040$ che hanno 5 ascese e 2 discese sono i numeri

$\left\langle {7 \atop 5}\right\rangle =\sum _{i=0}^{5}(-1)^{i}\ {\binom {7+1}{i}}\ (5-i)^{7}=1191{\mbox{ su }}5040\quad \left\langle {7 \atop 2}\right\rangle =\sum _{i=0}^{2}(-1)^{i}\ {\binom {7+1}{i}}\ (2-i)^{7}=2^{7}-8=120{\mbox{ su }}5040$

e corrispondono pure al numero permutazioni con 6 discending run (5 ascese) e al numero di 3 ascending run (2 discese);
sequenza massima di salite successive e discese successive

$\operatorname {ascrun} (\sigma )=\{345,\ 2,\ 167\}\qquad |\operatorname {ascrun} (\sigma )|-1=|D(\sigma )|=2\ \implies |\operatorname {ascrun} (\sigma )|=2+1=3$

$\operatorname {desrun} (\sigma )=\{3,\ 4,\ 52,\ 1,\ 6,\ 7\}\quad$;

sottosuccessioni crescenti e decrescenti

$\operatorname {is} (\sigma )=\{34567,\ 4567,\ 3457,\ \ldots ,\ 345,\ 346,\ \ldots ,\ 34,\ \ldots \}\quad \operatorname {ds} (\sigma )=\{3,\ 4,\ 52,\ 1,\ 6,\ 7\}$

che ha $\operatorname {max} \operatorname {is} (\sigma )=34567=\quad l_{}=5$;
insieme delle eccedenze deboli

$\operatorname {E} (\sigma )=\{1,2,3,6,7\}\quad |\operatorname {E} (\sigma )|=5$.

il numero di permutazioni con 5 eccedenze coincide con quello delle permutazioni con 5 discese calcolato, cioè ${\textstyle \left\langle {7 \atop 5}\right\rangle =1191{\mbox{ su }}5040}$;
infine si hanno gli elementi di massimo da sx-dx

$\operatorname {lrm} (\sigma )\ =\{5,6,7\}\quad |\operatorname {lrm} (\sigma )|=3$.

Lemma di transizione di Foata

Esiste una relazione tra la notazione 1-linea e la notazione ciclica canonica. Consideriamo una permutazione in notazione ciclica canonica

${\begin{aligned}\sigma \ &=\prod _{i=1}^{r}\sigma _{i}&&\sum _{i=1}^{r}l_{i}=\ n\\\sigma _{i}&=(s_{i1}\ s_{i2}\ \cdots \ s_{il_{i}})&&s_{i1}=\operatorname {max} X_{i}=\operatorname {max} \{s_{i1},s_{i2},\ldots ,s_{il_{i}}\}\\&s_{11}<s_{21}<\cdots <s_{r1}&&&\\\end{aligned}}$

se rimuoviamo semplicemente le parentesi, otteniamo la permutazione in notazione 1-linea

$\sigma \ =\ s_{11}\ldots s_{1l_{1}}s_{21}\ldots s_{2l_{2}}\ldots s_{r1}\ldots s_{rl_{r}}$

Il lemma di transizione di Foata stabilisce la natura di questa corrispondenza come una biiezione sull'insieme di n-permutazioni (a se stessa). Richard P. Stanley chiama tale corrispondenza la biiezione fondamentale.

Sia $f(p)=q$ la trasformazione elimina-parentesi che ritorna $q$ in notazione 1-linea quando $p$ è in notazione ciclica canonica. Come detto, $f$ opera con una semplice rimozione delle parentesi di ogni singolo ciclo. L'operazione di trasformazione inversa, $f^{-1}(q)=p$, ritorna $p$ in notazione ciclica canonica quando $q$ è in notazione 1-linea, opera come segue:

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, che viene detto left-to-right maximum.

Ogni ciclo nella notazione ciclica canonica inizia con un elemento lrm(left-to-right maximum) che sarebbe il massimo da sinistra a destra.

Ritornando all'esempio, nella permutazione scritta in notazione 1-linea

$S_{7}\ni \sigma =q=4251367(\neq 3452167)$ con $\operatorname {lrm} (\sigma )=\{5,\ 6,\ 7\}$

per cui si hanno i quattro cicli $(4\ 2),\ (5\ 1\ 3),\ (6),\ (7)$ e per la corrispondenza vista si ottiene la permutazione in notazione ciclica canonica:

$f^{-1}(q)=p=(4\ 2)(5\ 1\ 3)(6)(7)$

$q=312548976$, 5 è il primo elemento maggiore rispetto a quello iniziale 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.

Un secondo esempio è una tabella di $q$ e $p$ per le sei permutazioni dell'insieme $X\ =\{1,2,3\}$. La scrittura in evidenza indica la notazione utilizzata per la permutazione (1-linea $q$ e ciclica canonica per $p$) mentre la scrittura standard indica altra notazione (ciclica per $p,\ q$). 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). $(\,2\,)(\,3\,1\,)=231$

$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\,)}$

Come corollario, il numero di n-permutazioni con k lrm è uguale al Numero di Stirling del primo tipo senza segno, $c(n,k)$. Inoltre, la corrispondenza di Foata equivale a considerare una n-permutazione con k-eccedenze deboli ed ottenere sempre una n-permuzione con k − 1 ascendenti. Ad esempio, (2)(31) = 321 ha due eccedenze deboli (per i=1,2), mentre f(321) = 231 ha un ascendente (i=1; cioè, da 2 a 3).

Inversioni e relazione di Kobayashi

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.

Un'inversione di una permutazione σ è una coppia (i, j) di posizioni in cui le voci di una permutazione sono nell'ordine opposto: $i<j$ e $\sigma (i)>\sigma (j)$. Quindi una discesa è semplicemente un'inversione in due posizioni adiacenti. Possiamo considerare allora l'insieme:

$\operatorname {inv} (\sigma )=\{\ (i,j)\ \mid \sigma (i)>\sigma (j),\quad i=1,\ldots ,n\,j=i+1,\dots ,n;\ \sigma \in S_{n}\}$

analogamente un'inversione è definita come la coppia di valori (σ(i),σ(j)) il cui ordine è invertito; tale definizione non varia il numero d'inversioni, e questa coppia (invertita) è anche un'inversione nel senso di una permutazione inversa σ⁻¹ e quindi definire un'antinversione considerando l'insieme

$\operatorname {ainv} (\sigma )=\{\ (i,j)\ \mid \sigma (i)<\sigma (j),\quad i=1,\ldots ,n\,j=i+1,\dots ,n;\ \sigma \in S_{n}\}$

e la somma della loro cardinalià equivale al numero di confronti tra le coppie (i,j), cioè:

$|\operatorname {inv} (\sigma )|+|\operatorname {ainv} (\sigma )|=\sum _{i=1}^{n-1}i={\binom {n}{2}}.$

Il numero di inversioni è una misura importante per valutare il grado di disordine delle entrate di una permutazione; questo è vero per σ e anche per σ⁻¹. Per mettere in ordine una permutazione con |inv(σ)| inversioni (cioè, trasformarla nella permutazione identità), applicando successive moltiplicazioni a destra di trasposizioni adiacenti, richiede una sequenza di |inv(σ)| operazioni. Inoltre, occorre una scelta ragionevole per le trasposizioni: è sufficiente ad ogni passo comporre con il 2-ciclo ( i,i + 1) dove i è una discesa nella permutazione che viene eliminata e quindi studiare la permutazione dopo tale operazione. Ogni composizione con la trasposizione riduce il numero d'inversione di 1; fino a quando |inv(σ)|≠0, la permutazione non è quella identica, quindi ammette almeno un discendente. Gli algoritmi di Bubble sort e insertion sort possono essere interpretati come casi particolari di questa procedura per ordinare una sequenza. Per inciso questa procedura dimostra che qualsiasi permutazione σ può essere scritta come prodotto di trasposizioni adiacenti; cioè si può semplicemente invertire qualsiasi sequenza di tali trasposizioni che trasformi σ nell'identità. Infatti, dallo studio della sequenza di trasposizioni adiacenti che trasformerebbero σ nell'identità, otteniamo (dopo l'inversione) una lista completa delle espressioni di lunghezza minima per scrivere σ come prodotto di trasposizioni adiacenti.

Riprendiamo l'esempio considerando la permutazione:

$S_{7}\ni \sigma =3452167\quad \operatorname {des} (\sigma )=\{3,4\}|D(\sigma )|=2$

allora abbiamo di certo due inversioni per le discese i=3,4 cui corrispondono le coppie (5,2) e (2,1). Operando tutti i confronti di numero $\textstyle \sum _{i=1}^{6}i=1+2+3+4+5+6=21$ si ottiene l'insieme

${\operatorname {inv'} }(\sigma )=\{\ (\ \sigma (i),\sigma (j)\ )\mid 1\leq i<j\leq n,\sigma \in S_{n}\}=\{(2,1),(3,1),(3,2),(4,2),(4,1),(5,2),(5,1)\}\quad |\operatorname {inv} (\sigma )|=7\qquad |\operatorname {inv} (\sigma )|+|\operatorname {ainv} (\sigma )|=7+14=\sum _{i=1}^{6}i=21$

e per riordinare utilizziamo le seguenti composizioni di trasposizioni:

$\sigma _{\text{1-linea}}$	$(i,i+1)_{\text{1-linea}}$	$\operatorname {des} (\sigma )$	$|\operatorname {inv} (\sigma )|$
3452167	1235467	{3,4}	7
3451267	1243567	{3}	6
3415267	1324567	{2,4}	5
3145267	2134567	{1,4}	4
1345267	1235467	{4}	3
1342567	1243567	{3}	2
1324567	1324567	{2}	1
1234567	--	{∅}	0

quindi si ottiene pure la decomposizione a 2-cicli non disgiunti

$[\sigma \circ (5~4)(4~3)(3~2)(2~1)(5~4)(4~3)(3~2)]^{-1}=id^{-1}$

$[(5~4)(4~3)(3~2)(2~1)(5~4)(4~3)(3~2)]^{-1}\circ \sigma ^{-1}=id$

$[(5~4)(4~3)(3~2)(2~1)(5~4)(4~3)(3~2)]^{-1}\circ \sigma ^{-1}\circ \sigma =\sigma$

$\sigma =(2~3)(3~4)(4~5)(1~2)(2~3)(3~4)(4~5)\quad \operatorname {sgn} (\sigma )=(-1)^{|\operatorname {inv} (\sigma )|}=(-1)^{7}=-1$

ed è una permutazione con segno - o che si decompone in 2-cicli di numero dispari, cioè im 7 trasposizioni.

Il numero di permutazioni di n con k inversioni viene espresso da un numero Mahoniano. Questi sono i coefficienti $a_{k}$ di un polinomio nella variabile q ottenuto dal seguente prodotto

$[n]_{q}!=\prod _{i=1}^{n}\sum _{k=0}^{i-1}\ q^{k}=1\left(1+q\right)\left(1+q+q^{2}\right)\cdots \left(1+q+q^{2}+\cdots +q^{n-1}\right)=\sum _{k=0}^{n}\ a_{k}q^{k}$

La notazione $[n]_{q}!$ indica il q-fattoriale. Questa espansione compare nello studio combinatorio di oggetti detti collane.

Ad esempio per n=3 otteniamo il polimonio

$[3]_{q}!=P(q)=1(1+q)(1+q+q^{2})=q^{3}\ +2q^{2}\ +2q^{1}\ +1q^{0}\qquad a_{3}=1,\ a_{2}=a_{1}=2,\ a_{0}=1$

e ci fornisce le seguenti inversioni per le permutazioni di S₃ dove nella prima colonna σ è in notazione 1-linea

$\sigma _{\text{1-linea}}$	$\operatorname {inv} (\sigma )$	$a_{k}$	$|\operatorname {inv} (\sigma )|=k$
$123$	$\emptyset$	1	0
$213,\ 132$	$\{(2,1)\},\ \{(3,2)\}$	2	1
$312,231$	$\{(3,1),(3,2)\},\ \{(2,1),(3,1)\}$	2	2
$321$	$\{(3,2),(3,1),(2,1)\}$	1	3

Relazione Kobayashi

Una permutazione σ si dice Grassmanniana se ha solo un discendente in posizione k, cioè:

$\exists ^{'}k\in \mathbb {Z} \ 1\leqslant k\leqslant n-1\ :\sigma (k)>\sigma (k+1)$

e possiamo introdurre l'insieme delle permutazioni con tale proprietà

$\operatorname {G_{n}} =\{\sigma |\ |\operatorname {des} (\sigma )|=1,\,\sigma \in S_{n}\}$

nel caso delle permutazioni inverse si ha l'insieme $\operatorname {G_{n}^{-1}}$ Una permutazione σ si dice biGrassmanniana se σ e σ^-1 sono entrambi Grassmanniane. Da notare che se σ è Grassmanniana allora σ^-1 ammette al più una valle (dip), cioè

$\exists (i,j),\ 1\leqslant i<j\leqslant n\ :\ \sigma (i)=\sigma (j)+1.$

quindi una permutazione è biGrassmanniana se e solo se ammette al più un discendente e un dip. Indichiamo tale insieme come

$\operatorname {\mathbf {G_{n}} } =\operatorname {G_{n}} \cap \operatorname {G_{n}^{-1}}$

Sia $\sigma \in S_{n},\,i,j\in \{1,2,\dots ,n\}$ per cui $i<j$ e $\sigma (i)>\sigma (j)$. Allora denotiamo peso dell'inversione per $(i,j)$ la quantità $w(i,j)=\sigma (i)-\sigma (j)$. Kobayashi (2011) ha provato la seguente relazione:

$\sum _{i<j,\sigma (i)>\sigma (j)}\ [\sigma (i)-\sigma (j)]\ ={\Big |}\{\tau \ \mid \tau \leq \sigma ,\quad \tau \in \operatorname {\mathbf {G_{n}} } \subseteq S_{n},\,\sigma \in S_{n}\}{\Big |}$

dove $\leq$ denota la relazione d'ordine di Bruhat definita nel gruppo simmetrico. Tale ordine parziale graduato spesso si applica nello studio dei gruppi di Coxeter.

Esempio: consideriamo la seguente permutazione:

$S_{7}\ni \sigma ={\begin{pmatrix}1&2&3&4&5&6&7\\5&6&7&1&2&3&4\\\end{pmatrix}}=(1\ 5\ 2\ 6\ 3\ 7\ 4)=5671234$

ammette i due insiemi

${\begin{aligned}\operatorname {asc} (\sigma )&=\{1,2,4,5,6,7\}&|A(\sigma )|=6\\\operatorname {des} (\sigma )&=\{3\}&|D(\sigma )|=1\\\end{aligned}}$

quindi σ ∈ G_n. Adesso è facile vedere che

$\exists ^{'}(i,j)=(1,7)\ :\sigma (i)=5=\sigma (j)+1=4+1$

quindi σ è biGrassmanniana. Ciò si può vedere pure considerando σ^-1

$S_{7}\ni \sigma ^{-1}={\begin{pmatrix}1&2&3&4&5&6&7\\4&5&6&7&1&2&3\\\end{pmatrix}}=(1\ 4\ 7\ 3\ 6\ 2\ 5)=4567123$

ammette i due insiemi

${\begin{aligned}\operatorname {asc} (\sigma ^{-1})&=\{1,2,3,5,6,7\}&|A(\sigma ^{-1})|=6\\\operatorname {des} (\sigma ^{-1})&=\{4\}&|D(\sigma ^{-1})|=1\\\end{aligned}}$

inoltre

$\operatorname {inv} (\sigma )=\{(1,4),(1,5),(1,6),(1,7);(2,4),(2,5),(2,6),(2,7);(3,4),(3,5),(3,6),(3,7)\}\quad |\operatorname {inv} (\sigma )|=12$

$w_{\operatorname {inv} (\sigma )}=\{4,3,2,1;5,4,3,2;6,5,4,3\}\quad \sum _{}\ w(i,j)=42$

per cui abbiamo 42 permutazioni biGrassmanniane che stanno in relazione secondo Bruhat con la nostra permutazione σ.

Permutazioni nell'informatica

Numbering permutations

One way to represent permutations of n things is by an integer N with 0 ≤ N < n!, provided convenient methods are given to convert between the number and the representation of a permutation as an ordered arrangement (sequence). This gives the most compact representation of arbitrary permutations, and in computing is particularly attractive when n is small enough that N can be held in a machine word; for 32-bit words this means n ≤ 12, and for 64-bit words this means n ≤ 20. The conversion can be done via the intermediate form of a sequence of numbers d_n, d_n−1, ..., d₂, d₁, where d_i is a non-negative integer less than i (one may omit d₁, as it is always 0, but its presence makes the subsequent conversion to a permutation easier to describe). The first step then is to simply express N in the factorial number system, which is just a particular mixed radix representation, where, for numbers less than n!, the bases (place values or multiplication factors) for successive digits are Template:Math, Template:Math, ..., 2!, 1!. The second step interprets this sequence as a Lehmer code or (almost equivalently) as an inversion table.

I codici Lehmer, noti anche come vettori di inversione, sono rappresentazioni vettoriali di permutazioni in cui ciascuna coordinata può assumere valori non limitati dai valori di altre coordinate. This transformation allows for decoupling of the coordinates and for performing aggregation via simple scalar median or mode computations. Nel codice Lehmer per una permutazione σ, il numero d_n rappresenta la scelta fatta per il primo termine σ(1), il numero d_n−1 è associato al termine σ(2) tra i rimanenti n − 1 elementi dell'insieme, e così via. Più precisamente, each d_n+1−i gives the number of remaining ) elements strictly less than the term σ(i). Since those remaining elements are bound to turn up as some later term σ(j), the digit d_n+1−i counts the inversions (i,j) involving i as smaller index (the number of values j for which i < j and σ(i) > σ(j).

Una tabella inversione per σ è abbastanza simile, e viene definita come segue

$\operatorname {I(\sigma )} \ =\ (d_{1},d_{2},\ldots ,d_{k},\ldots ,d_{n}),\quad 0\leqslant d_{k}\leqslant n-k\quad \sum _{k=1}^{n}\ d_{k}=|\operatorname {inv(\sigma )} |$

$d_{k}=|\{\ (i,j)\ \mid \sigma (j)>\sigma (i)=k,\quad i,k=1,2,\ldots ,n\ \ j=1,\ldots ,(i-1)\,\sigma \in S_{n}\}|$

$\sigma =\underbrace {\sigma (1)\sigma (2)\cdots \sigma (i)=k} _{d_{k}}\cdots \sigma (n)$

ma adesso d_n+1−k è il numero d'inversioni (i,j) dove k = σ(i) si verifica come il più piccolo dei due valori visualizzati in ordine invertito. Perhaps the most important fact about inversions is Marshall Hall's observation that an inversion table uniquely determines the corresponding permutation.

Diagramma di Rothe

Diagramma di Rothe $\sigma =638149725$

σ(i)=k i	1	2	3	4	5	6	7	8	9	$\operatorname {L} (\sigma )$
1	×	×	×	×	×	•				d9 = 5
2	×	×	•							d8 = 2
3	×	×		×	×		×	•		d7 = 5
4	•									d6 = 0
5		×		•						d5 = 1
6		×			×		×		•	d4 = 3
7		×			×		•			d3 = 2
8		•								d2 = 0
9					•					d1 = 0
$\operatorname {I} (\sigma )$	3	6	1	2	4	0	2	0	0
$\operatorname {I} (\sigma )=(3,6,1,2,4,0,2,0,0)\quad \operatorname {L} (\sigma )=(0,0,2,3,1,0,5,2,5)$

Entrambe le codifiche possono essere visualizzate da un diagramma di Rothe n by n (named after Heinrich August Rothe) in which dots at (i,σ_i) mark the entries of the permutation, and a cross at (i,σ_j) marks the inversion (i,j); by the definition of inversions a cross appears in any square that comes both before the dot (j,σ_j) in its column, and before the dot (i,σ_i) in its row. The Lehmer code lists the numbers of crosses in successive rows, while the inversion table lists the numbers of crosses in successive columns; it is just the Lehmer code for the inverse permutation, and vice versa.

To effectively convert a Lehmer code d_n, d_n−1, ..., d₂, d₁ into a permutation of an ordered set S, one can start with a list of the elements of S in increasing order, and for i increasing from 1 to n set σ_i to the element in the list that is preceded by d_n+1−i other ones, and remove that element from the list. To convert an inversion table d_n, d_n−1, ..., d₂, d₁ into the corresponding permutation, one can traverse the numbers from d₁ to d_n while inserting the elements of S from largest to smallest into an initially empty sequence; at the step using the number d from the inversion table, the element from S inserted into the sequence at the point where it is preceded by d elements already present. Alternatively one could process the numbers from the inversion table and the elements of S both in the opposite order, starting with a row of n empty slots, and at each step place the element from S into the empty slot that is preceded by d other empty slots.

Converting successive natural numbers to the factorial number system produces those sequences in lexicographic order (as is the case with any mixed radix number system), and further converting them to permutations preserves the lexicographic ordering, provided the Lehmer code interpretation is used (using inversion tables, one gets a different ordering, where one starts by comparing permutations by the place of their entries 1 rather than by the value of their first entries). The sum of the numbers in the factorial number system representation gives the number of inversions of the permutation, and the parity of that sum gives the signature of the permutation. Moreover, the positions of the zeroes in the inversion table give the values of left-to-right maxima of the permutation (in the example 6, 8, 9) while the positions of the zeroes in the Lehmer code are the positions of the right-to-left minima (in the example positions the 4, 8, 9 of the values 1, 2, 5); this allows computing the distribution of such extrema among all permutations. A permutation with Lehmer code d_n, d_n−1, ..., d₂, d₁ has an ascent Template:Math if and only if Template:Math.

Algoritmi che generano permutazioni

In computing it may be required to generate permutations of a given sequence of values. The methods best adapted to do this depend on whether one wants some randomly chosen permutations, or all permutations, and in the latter case if a specific ordering is required. Another question is whether possible equality among entries in the given sequence is to be taken into account; if so, one should only generate distinct multiset permutations of the sequence.

An obvious way to generate permutations of n is to generate values for the Lehmer code (possibly using the factorial number system representation of integers up to n!), and convert those into the corresponding permutations. However, the latter step, while straightforward, is hard to implement efficiently, because it requires n operations each of selection from a sequence and deletion from it, at an arbitrary position; of the obvious representations of the sequence as an array or a linked list, both require (for different reasons) about n²/4 operations to perform the conversion. With n likely to be rather small (especially if generation of all permutations is needed) that is not too much of a problem, but it turns out that both for random and for systematic generation there are simple alternatives that do considerably better. For this reason it does not seem useful, although certainly possible, to employ a special data structure that would allow performing the conversion from Lehmer code to permutation in O(n log n) time.

Generazione casuale di permutazioni

For generating random permutations of a given sequence of n values, it makes no difference whether one applies a randomly selected permutation of n to the sequence, or chooses a random element from the set of distinct (multiset) permutations of the sequence. This is because, even though in case of repeated values there can be many distinct permutations of n that result in the same permuted sequence, the number of such permutations is the same for each possible result. Unlike for systematic generation, which becomes unfeasible for large n due to the growth of the number n!, there is no reason to assume that n will be small for random generation.

The basic idea to generate a random permutation is to generate at random one of the n! sequences of integers d₁,d₂,...,d_n satisfying Template:Math (since d₁ is always zero it may be omitted) and to convert it to a permutation through a bijective correspondence. For the latter correspondence one could interpret the (reverse) sequence as a Lehmer code, and this gives a generation method first published in 1938 by Ronald Fisher and Frank Yates. While at the time computer implementation was not an issue, this method suffers from the difficulty sketched above to convert from Lehmer code to permutation efficiently. This can be remedied by using a different bijective correspondence: after using d_i to select an element among i remaining elements of the sequence (for decreasing values of i), rather than removing the element and compacting the sequence by shifting down further elements one place, one swaps the element with the final remaining element. Thus the elements remaining for selection form a consecutive range at each point in time, even though they may not occur in the same order as they did in the original sequence. The mapping from sequence of integers to permutations is somewhat complicated, but it can be seen to produce each permutation in exactly one way, by an immediate induction. When the selected element happens to be the final remaining element, the swap operation can be omitted. This does not occur sufficiently often to warrant testing for the condition, but the final element must be included among the candidates of the selection, to guarantee that all permutations can be generated.

The resulting algorithm for generating a random permutation of a[0], a[1], ..., a[n − 1] can be described as follows in pseudocode:

for i from n downto 2 do
    di ← random element of { 0, ..., i − 1 }
    swap a[di] and a[i − 1]

This can be combined with the initialization of the array a[i] = i as follows

for i from 0 to n−1 do
    di+1 ← random element of { 0, ..., i }
    a[i] ← a[di+1]
    a[di+1] ← i

If d_i+1 = i, the first assignment will copy an uninitialized value, but the second will overwrite it with the correct value i.

However, Fisher-Yates is not the fastest algorithm for generating a permutation, because Fisher-Yates is essentially a sequential algorithm and "divide and conquer" procedures can achieve the same result in parallel.

Generazione in ordine lessicografico

There are many ways to systematically generate all permutations of a given sequence. One classic, simple, and flexible algorithm is based upon finding the next permutation in lexicographic ordering, if it exists. It can handle repeated values, for which case it generates each distinct multiset permutation once. Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using the factorial number system) and converting those to permutations. It begins by sorting the sequence in (weakly) increasing order (which gives its lexicographically minimal permutation), and then repeats advancing to the next permutation as long as one is found. The method goes back to Narayana Pandita in 14th century India, and has been rediscovered frequently.Template:Sfn

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the largest index k such that Template:Math. If no such index exists, the permutation is the last permutation.
2. Find the largest index l greater than k such that Template:Math.
3. Swap the value of a[k] with that of a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

For example, given the sequence [1, 2, 3, 4] (which is in increasing order), and given that the index is zero-based, the steps are as follows:

1. Index k = 2, because 3 is placed at an index that satisfies condition of being the largest index that is still less than a[k + 1] which is 4.
2. Index l = 3, because 4 is the only value in the sequence that is greater than 3 in order to satisfy the condition a[k] < a[l].
3. The values of a[2] and a[3] are swapped to form the new sequence [1, 2, 4, 3].
4. The sequence after k-index a[2] to the final element is reversed. Because only one value lies after this index (the 3), the sequence remains unchanged in this instance. Thus the lexicographic successor of the initial state is permuted: [1, 2, 4, 3].

Following this algorithm, the next lexicographic permutation will be [1, 3, 2, 4], and the 24th permutation will be [4, 3, 2, 1] at which point a[k] < a[k + 1] does not exist, indicating that this is the last permutation.

This method uses about 3 comparisons and 1.5 swaps per permutation, amortized over the whole sequence, not counting the initial sort.

Generazione con cambi minimi

An alternative to the above algorithm, the Steinhaus–Johnson–Trotter algorithm, generates an ordering on all the permutations of a given sequence with the property that any two consecutive permutations in its output differ by swapping two adjacent values. This ordering on the permutations was known to 17th-century English bell ringers, among whom it was known as "plain changes". One advantage of this method is that the small amount of change from one permutation to the next allows the method to be implemented in constant time per permutation. The same can also easily generate the subset of even permutations, again in constant time per permutation, by skipping every other output permutation.Template:Sfn

An alternative to Steinhaus–Johnson–Trotter is Heap's algorithm, said by Robert Sedgewick in 1977 to be the fastest algorithm of generating permutations in applications.

The following figure shows the output of all three aforementioned algorithms for generating all permutations of length $n=4$, and of six additional algorithms described in the literature.

Ordering of all permutations of length $n=4$ generated by different algorithms. The permutations are color-coded, where Template:Legend-inline, Template:Legend-inline, Template:Legend-inline, Template:Legend-inline.

1. Lexicographic ordering;
2. Steinhaus–Johnson–Trotter algorithm;
3. Heap's algorithm;
4. Ehrlich's star-transposition algorithm:Template:Sfn in each step, the first entry of the permutation is exchanged with a later entry;
5. Zaks' prefix reversal algorithm: in each step, a prefix of the current permutation is reversed to obtain the next permutation;
6. Sawada-Williams' algorithm: each permutation differs from the previous one either by a cyclic left-shift by one position, or an exchange of the first two entries;
7. Corbett's algorithm: each permutation differs from the previous one by a cyclic left-shift of some prefix by one position;
8. Single-track ordering: each column is a cyclic shift of the other columns;
9. Single-track Gray code: each column is a cyclic shift of the other columns, plus any two consecutive permutations differ only in one or two transpositions.
10. Nested swaps generating algorithm in steps connected to the nested subgroups $S_{k}\subset S_{k+1}$. Each permutation is obtained from the previous by a transposition multiplication to the left. Algorithm is connected to the Factorial_number_system of the index.

Generation of permutations in nested swap steps

Explicit sequence of swaps (transpositions, 2-cycles $(pq)$), is described here, each swap applied (on the left) to the previous chain providing a new permutation, such that all the permutations can be retrieved, each only once. This counting/generating procedure has an additional structure (call it nested), as it is given in steps: after completely retrieving $S_{k-1}$, continue retrieving $S_{k}\backslash S_{k-1}$ by cosets $S_{k-1}\tau _{i}$ of $S_{k-1}$ in $S_{k}$, by appropriately choosing the coset representatives $\tau _{i}$ to be described below. Note that, since each $S_{m}$ is sequentially generated, there is a last element $\lambda _{m}\in S_{m}$. So, after generating $S_{k-1}$ by swaps, the next permutation in $S_{k}\backslash S_{k-1}$ has to be $\tau _{1}=(p_{1}k)\lambda _{k-1}$ for some $1\leq p_{1}<k$. Then all swaps that generated $S_{k-1}$ are repeated, generating the whole coset $S_{k-1}\tau _{1}$, reaching the last permutation in that coset $\lambda _{k-1}\tau _{1}$; the next swap has to move the permutation to representative of another coset $\tau _{2}=(p_{2}k)\lambda _{k-1}\tau _{1}$.

Continuing the same way, one gets coset representatives $\tau _{j}=(p_{j}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{i}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{1}k)\lambda _{k-1}$ for the cosets of $S_{k-1}$ in $S_{k}$; the ordered set $(p_{1},\ldots ,p_{k-1})$ ($0\leq p_{i}<k$) is called the set of coset beginnings. Two of these representatives are in the same coset if and only if $\tau _{j}(\tau _{i})^{-1}=(p_{j}k)\lambda _{k-1}(p_{j-1}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{i+1}k)=\varkappa _{ij}\in S_{k-1}$, that is, $\varkappa _{ij}(k)=k$. Concluding, permutations $\tau _{i}\in S_{k}-S_{k-1}$ are all representatives of distinct cosets if and only if for any $k>j>i\geq 1$, $(\lambda _{k-1})^{j-i}p_{i}\neq p_{j}$ (no repeat condition). In particular, for all generated permutations to be distinct it is not necessary for the $p_{i}$ values to be distinct. In the process, one gets that $\lambda _{k}=\lambda _{k-1}(p_{k-1}k)\lambda _{k-1}(p_{k-2}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{1}k)\lambda _{k-1}$ and this provides the recursion procedure.

EXAMPLES: obviously, for $\lambda _{2}$ one has $\lambda _{2}=(12)$; to build $\lambda _{3}$ there are only two possibilities for the coset beginnings satisfying the no repeat condition; the choice $p_{1}=p_{2}=1$ leads to $\lambda _{3}=\lambda _{2}(13)\lambda _{2}(13)\lambda _{2}=(13)$. To continue generating $S_{4}$ one needs appropriate coset beginnings (satisfying the no repeat condition): there is a convenient choice: $p_{1}=1,p_{2}=2,p_{3}=3$, leading to $\lambda _{4}=(13)(1234)(13)=(1432)$. Then, to build $\lambda _{5}$ a convenient choice for the coset beginnings (satisfying the no repeat condition) is $p_{1}=p_{2}=p_{3}=p_{4}=1$, leading to $\lambda _{5}=(15)$.

From examples above one can inductively go to higher $k$ in a similar way, choosing coset beginnings of $S_{k}$ in $S_{k+1}$, as follows: for $k$ even choosing all coset beginnings equal to 1 and for $k$ odd choosing coset beginnings equal to $(1,2,\dots ,k)$. With such choices the "last" permutation is $\lambda _{k}=(1k)$ for $k$ odd and $\lambda _{k}=(1k_{-})(12\cdots k)(1k_{-})$ for $k$ even ($k_{-}=k-1$). Using these explicit formulae one can easily compute the permutation of certain index in the counting/generation steps with minimum computation. For this, writing the index in factorial base is useful. For example, the permutation for index $699=5(5!)+4(4!)+1(2!)+1(1!)$ is: $\sigma =\lambda _{2}(13)\lambda _{2}(15)\lambda _{4}(15)\lambda _{4}(15)\lambda _{4}(15)\lambda _{4}(56)\lambda _{5}(46)\lambda _{5}(36)\lambda _{5}(26)\lambda _{5}(16)\lambda _{5}=$ $\lambda _{2}(13)\lambda _{2}((15)\lambda _{4})^{4}(\lambda _{5})^{-1}\lambda _{6}=(23)(14325)^{-1}(15)(15)(123456)(15)=$$(23)(15234)(123456)(15)$, yelding finally, $\sigma =(1653)(24)$.

Because multiplying by swap permutation takes short computing time and every new generated permutation requires only one such swap multiplication, this generation procedure is quite efficient. Moreover as there is a simple formula, having the last permutation in each $S_{k}$ can save even more time to go directly to a permutation with certain index in fewer steps than expected as it can be done in blocks of subgroups rather than swap by swap.

Applicazioni

Le permutazioni vengono utilizzate come componenti interleaver e sono ampiamente utilizzati negli algoritmi di rilevazione e correzione d'errore negli schemi di codifica su canali bursty, come i turbo codici, per esempio lo standard di telecomuinicazione mobile 3GPP Long Term Evolution usa questo concetto (vedi la specifica tecnica 36.212 3GPP).

Tali applicazioni sollevano la questione della generazione rapida di permutazioni che soddisfino determinate proprietà desiderabili. One of the methods is based on the permutation polynomials. Also as a base for optimal hashing in Unique Permutation Hashing.

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.

Nella cultura indiana la relazione per calcolare il numero di permutazioni di n oggetti se ne fa menzione intorno al 1150 AD. L'opera Lilavati del matematico indiano Bhaskara II contiene la seguente traduzione:

Il prodotto della moltiplicazione della serie aritmetica inizia e aumenta per unità e continua fino al numero di posti, will be the variations of number with specific figures.

Nel 1677, Fabian Stedman studioso inglese del ASCY ha descritto i fattoriali quando calcola il numero di permutazioni per usare il metodo del suono permutato di più campane. A partire da due campane: "primo, 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

Postille

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. (ristampa), New York, Chelsea Pub Co., 1999, ISBN 978-0-8218-1967-8.
• (EN) Marshall Jr. Hall, The Theory of Groups, 1ª ed., New York, The Macmillan Company, 1959, LCCN 59005035.
• (EN) Fabian Stedman, Campanalogia, Londra, ASCY, 1677.
• (EN) Kenneth P. Bogart, Introductory Combinatorics, 2ª ed., Harcourt Brace Jovanovich, 1990, ISBN 978-0-15-541576-8.
• (EN) Larry J. Gerstein, Discrete Mathematics and Algebraic Structures, 2ª ed., W.H. Freeman and Co., 1987, ISBN 978-0-7167-1804-8.
• (EN) Richard P. Stanley, Enumerative Combinatorics: Volume I, Second Edition, 2ª ed., CUP, 2012, ISBN 978-1-107-01542-5.
• (EN) Donald Knuth, The Art of Computer Programming. Sorting and Searching, 2ª ed., Boston, Addison-Wesley, 1973, ISBN 0-201-89685-0.

Voci correlate

• Combinazione
• Convoluzione
• Dismutazione
• Dismutazione parziale
• Disposizione
• Ordine ciclico
• Permutazione alternata
• Probabilità
• Statistica
• Superpermutazione