Permutazione

Una permutazione è un modo di ordinare in successione oggetti distinti, come nell'anagramma di una parola. In termini matematici una permutazione di un insieme ${\displaystyle X}$ si definisce come una funzione biiettiva ${\displaystyle p\colon X\rightarrow X}$^[1].

Elencare e contare le permutazioni

Il numero delle permutazioni di ${\displaystyle n}$ oggetti è pari al fattoriale di ${\displaystyle n}$:

${\displaystyle n!=n\cdot (n-1)\cdot (n-2)\cdots 1,}$

infatti ci sono ${\displaystyle n}$ modi di scegliere l'oggetto che occupa la prima posizione, per ciascuno di essi ci sono ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n}$ oggetti, di cui ${\displaystyle n_{1}}$ sono di un tipo, ${\displaystyle n_{2}}$ di un altro tipo, ecc. fino a ${\displaystyle n_{k}}$, con ${\displaystyle n=n_{1}+n_{2}+\cdots +n_{k}}$, il numero di permutazioni distinte o permutazioni con ripetizioni di un insieme di ${\displaystyle n}$ elementi, contenente ${\displaystyle n_{1},n_{2},\ldots ,n_{k}}$ elementi ripetuti, ossia identici tra loro, è uguale a

${\displaystyle {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, ${\displaystyle n=4}$ e ${\displaystyle n_{1}=n_{2}=2}$, e si ottiene quindi

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

Dimostrazione

Si inseriscano in una tabella tutte le permutazioni semplici di ${\displaystyle n}$ oggetti in cui solo ${\displaystyle 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:

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

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

${\displaystyle 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

${\displaystyle 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 ${\displaystyle p\colon X\to X}$. Due permutazioni ${\displaystyle p}$ e ${\displaystyle p'}$ possono quindi essere composte e il risultato è ancora una permutazione. L'insieme ${\displaystyle S(X)}$ delle permutazioni di ${\displaystyle X}$ con l'operazione di composizione forma un gruppo, detto gruppo simmetrico. L'elemento neutro è la permutazione che lascia fissi tutti gli elementi; in notazione ciclica ${\displaystyle \mathrm {id} =(1)(2)\cdots (n)}$ cioè si rappresenta con un numero di ${\displaystyle n}$ 1-cicli.

Cicli

Sia ${\displaystyle a_{1},\ldots ,a_{n}}$ una successione di elementi distinti di ${\displaystyle X}$. Il ciclo

${\displaystyle p=(a_{1}\ a_{2}\ \ldots \ a_{n})}$

è la permutazione che manda ${\displaystyle a_{i}}$ in ${\displaystyle a_{i+1},}$ se ${\displaystyle i=1,\ldots ,n-1,}$ e in ${\displaystyle a_{1},}$ se ${\displaystyle i=n,}$ e tiene fissi gli altri. Più formalmente è definita nel modo seguente:

${\displaystyle p(a_{1})=a_{2},p(a_{2})=a_{3},\ldots ,p(a_{n})=a_{1};}$

${\displaystyle p(a)=a}$ per gli altri ${\displaystyle a.}$

L'ordine del ciclo è il numero ${\displaystyle n}$. Una trasposizione è un ciclo ${\displaystyle (a\ b)}$ di ordine 2: consiste semplicemente nello scambiare gli elementi ${\displaystyle a}$ e ${\displaystyle b}$, lasciando fissi tutti gli altri.

Due cicli ${\displaystyle (a_{1}\ a_{2}\ \ldots \ a_{n})}$ e ${\displaystyle (b_{1}\ b_{2}\ \ldots \ b_{m})}$ sono indipendenti se ${\displaystyle a_{i}\neq b_{j}}$ per ogni ${\displaystyle i}$ e ${\displaystyle j}$. Due cicli indipendenti ${\displaystyle a}$ e ${\displaystyle b}$ commutano, cioè ${\displaystyle a\circ b=b\circ a}$. L'importanza dei cicli sta nel seguente teorema: ogni permutazione si scrive in modo unico come prodotto di cicli indipendenti.

Poiché cicli indipendenti commutano, l'unicità è da intendersi a meno di scambiare l'ordine dei cicli.

Notiamo infine che le notazioni ${\displaystyle (a\ b\ c)}$ e ${\displaystyle (b\ c\ a)}$ definiscono lo stesso ciclo, mentre ${\displaystyle (a\ b\ c)}$ e ${\displaystyle (b\ a\ c)}$ sono cicli diversi.

Notazione

Ci sono due notazioni per scrivere una permutazione. La notazione detta a 2 linee^[2]:

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

oppure la notazione detta ciclica:

${\displaystyle \alpha =\alpha _{1}\alpha _{2}\cdots \alpha _{r},}$

dove

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

Esempio

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

${\displaystyle \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 possono scrivere le stesse permutazioni sfruttando il teorema enunciato sopra, scrivendole come prodotto di cicli indipendenti. Nel caso in esempio si ottengono ${\displaystyle \alpha =(1\ 2\ 5)(3\ 4),}$ ${\displaystyle \beta =(1\ 2\ 3)}$ e ${\displaystyle \alpha \circ \beta =(1\ 2\ 5)(3\ 4)\circ (1\ 2\ 3)=(1\ 5)(2\ 4\ 3).}$

Si noti che nella composizione ciclica si applica prima il ciclo di destra e poi il ciclo di sinistra. Per esempio, per vedere dove viene mandato 1 dalla composizione ${\displaystyle (1\ 2\ 5)(3\ 4)\circ (1\ 2\ 3)}$ si vede che ${\displaystyle (1\ 2\ 3)}$ lo manda in 2, ${\displaystyle (3\ 4)}$ non muove 2, e infine ${\displaystyle (1\ 2\ 5)}$ manda 2 in 5. Quindi 1 va in 5.

Segno di una permutazione

Definizione

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

${\displaystyle \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

${\displaystyle (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 ${\displaystyle (1\ 2)}$anche come ${\displaystyle (2\ 3)(1\ 3)(2\ 3)}$ o ${\displaystyle (1\ 4)(2\ 3)(3\ 4)(2\ 3)(1\ 4)}$. Si può dimostrare che se una stessa permutazione ${\displaystyle p}$ può essere scritta sia come prodotto di ${\displaystyle h}$ trasposizioni, sia come prodotto di ${\displaystyle k}$ trasposizioni, allora ${\displaystyle h}$ e ${\displaystyle k}$ hanno la stessa parità, cioè sono entrambi pari o entrambi dispari.

Una permutazione ${\displaystyle p}$ è detta pari o dispari a seconda che sia ottenibile come prodotto di un numero pari o dispari di trasposizioni. Il segno di ${\displaystyle p}$ è definito rispettivamente come ${\displaystyle +1}$ e ${\displaystyle -1.}$

Proprietà

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

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

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

Gruppo alternante

Metà delle ${\displaystyle n!}$ permutazioni di un insieme di ${\displaystyle n}$ elementi sono pari. Poiché la funzione segno è moltiplicativa, le permutazioni pari formano un sottogruppo normale di indice due del gruppo simmetrico ${\displaystyle S(X)=S_{n}}$ delle permutazioni dell'insieme ${\displaystyle X=\{1,2,\ldots ,n\}}$, detto gruppo alterno e indicato con ${\displaystyle A(X)=A_{n}.}$ Si tratta del nucleo dell'omomorfismo di gruppi

${\displaystyle \operatorname {sgn} \colon S(X)\to \{+1,-1\}.}$

L'immagine è un gruppo ciclico con due elementi.

Formula per il segno

Fissiamo un elemento ${\displaystyle \sigma \in S_{n}}$ nella notazione a 2 linee:

${\displaystyle \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 ${\displaystyle (i,j),}$ con ${\displaystyle 1\leq i<j\leq n,}$ dicesi inversione per ${\displaystyle \sigma }$ se si verifica ${\displaystyle \sigma (i)>\sigma (j)}$. Supponendo di ottenere ${\displaystyle r}$ inversioni, allora il segno della permutazione ${\displaystyle \sigma }$ può essere calcolato tramite la formula seguente:

${\displaystyle \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&\sigma {\text{ pari,}}\\-1&\sigma {\text{ dispari.}}\\\end{cases}}}$

Esempi

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

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

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

${\displaystyle \mathrm {id} ,(1\ 2\ 3),(1\ 3\ 2)}$ pari;

${\displaystyle (1\ 2),(1\ 3),(2\ 3)}$ dispari.

Infatti per

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

si ottiene

${\displaystyle \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 che ${\displaystyle r=3}$ e ${\displaystyle \epsilon (\sigma )=(-1)^{r}=(-1)^{3}=-1}$. Lo stesso discorso si applica per le restanti riflessioni ${\displaystyle \sigma =(1\ 2)}$ e ${\displaystyle \sigma =(2\ 3).}$

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

${\displaystyle \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 che ${\displaystyle r=2}$ e ${\displaystyle \epsilon (\sigma )=(-1)^{r}=(-1)^{2}=+1}$. Lo stesso discorso si applica per le restanti ${\displaystyle (1\ 3\ 2)}$ e ${\displaystyle \mathrm {id} }$. Le tre permutazioni pari formano il sottogruppo normale alterno ${\displaystyle A_{3}}$.

Note

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) 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., Chapman Hall-CRC, 2012, ISBN 978-1-4398-5051-0.
• (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.

Voci correlate

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

Altri progetti

• Wikizionario contiene il lemma di dizionario «permutazione»
• Wikimedia Commons contiene immagini o altri file sulla permutazione

Collegamenti esterni

• Permutazione, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.
• Permutazione, in Dizionario delle scienze fisiche, Istituto dell'Enciclopedia Italiana, 1996.
• Permutazióne, su Vocabolario Treccani, Istituto dell'Enciclopedia Italiana.
• permutazióne, su sapere.it, De Agostini.
• Permutazione, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• Permutazione, in Dizionario di Economia e Finanza, Istituto dell'Enciclopedia Italiana, 2012.
• (EN) permutations and combinations, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Permutazione, su MathWorld, Wolfram Research.
• (EN) Permutation, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) permutation, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL
• Permutazione, in Grande Dizionario di Italiano, Garzanti Linguistica.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Combinatoria
Orientamento generale	Combinatoria · Storia della combinatoria · Matematica discreta · Sezione 05-XX di MSC
Nozioni introduttive	Permutazioni · Disposizioni · Combinazioni · Coefficienti binomiali · Partizioni di interi · Partizioni di insiemi finiti - Identità combinatorie e biiezioni · Principio dei cassetti
Configurazioni	Quadrati latini · Quadrati magici · Disegni a blocchi · Geometrie finite · Matroidi - Tassellazioni · Polimini
Teoria dei grafi	Alberi · Cammini sui grafi (euleriani, hamiltoniani) · Connessione nei grafi - Grafi planari · Colorazione dei grafi e teorema dei quattro colori) · Ipergrafi · Grafi e gruppi · Digrafo · Flussi su grafi · Passeggiate aleatorie su grafi · Omomorfismo fra grafi · Algoritmi sui grafi
Combinatoria algebrica	Tavola di Young · Funzioni simmetriche - Serie formale di potenze · Funzioni generatrici · Polinomi ortogonali · Azioni di un gruppo su strutture combinatorie - Aspetti combinatorici dell'algebra commutativa
Altre aree	Calcolo umbrale (sequenze polinomiali di tipo binomiale · sequenze di Sheffer) - Combinatoria estremale

Controllo di autorità	Thesaurus BNCF 32734 · J9U (EN, HE) 987007536403105171