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 si definisce come una funzione biiettiva [1].
Elencare e contare le permutazioni
modificaIl numero delle permutazioni di oggetti è pari al fattoriale di :
infatti ci sono modi di scegliere l'oggetto che occupa la prima posizione, per ciascuno di essi ci sono modi di scegliere l'oggetto che occupa la seconda posizione, poi per ogni coppia di oggetti fissati nelle prime due posizioni ci sono 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
modificaSe 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 oggetti, di cui sono di un tipo, di un altro tipo, ecc. fino a , con , il numero di permutazioni distinte o permutazioni con ripetizioni di un insieme di elementi, contenente elementi ripetuti, ossia identici tra loro, è uguale a
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, e , e si ottiene quindi
Dimostrazione
modificaSi inseriscano in una tabella tutte le permutazioni semplici di oggetti in cui solo 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:
Ci saranno quindi tante righe quante permutazioni delle lettere ripetute e tante colonne quante permutazioni con ripetizione
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
Composizione
modificaUna permutazione è una funzione biettiva . Due permutazioni e possono quindi essere composte e il risultato è ancora una permutazione. L'insieme delle permutazioni di 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 cioè si rappresenta con un numero di 1-cicli.
Cicli
modificaSia una successione di elementi distinti di . Il ciclo
è la permutazione che manda in , manda in se e tiene fissi gli elementi di che non appartengono alla successione. Più formalmente è definita nel modo seguente:
- se
L'ordine del ciclo è il numero . Una trasposizione è un ciclo di ordine 2: consiste semplicemente nello scambiare gli elementi e , lasciando fissi tutti gli altri.
Due cicli e sono indipendenti se per ogni e . Due cicli indipendenti e commutano, cioè . 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 e definiscono lo stesso ciclo, mentre e sono cicli diversi.
Notazione
modificaCi sono due notazioni per scrivere una permutazione. La notazione detta a 2 linee[2]:
oppure la notazione detta ciclica:
dove
- è un generico -ciclo con .
Esempio
modificaSi considerino ad esempio le due permutazioni dell'insieme Si può scrivere sotto a ogni numero la posizione in cui questo viene spostato:
Alternativamente, si possono scrivere le stesse permutazioni sfruttando il teorema enunciato sopra, scrivendole come prodotto di cicli indipendenti. Nel caso in esempio si ottengono e
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 si vede che lo manda in 2, non muove 2, e infine manda 2 in 5. Quindi 1 va in 5.
Segno di una permutazione
modificaDefinizione
modificaOgni -ciclo è prodotto di trasposizioni. Infatti, sempre con la composizione da destra verso sinistra, si ha:
In particolare si ha
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 anche come o . Si può dimostrare che se una stessa permutazione può essere scritta sia come prodotto di trasposizioni, sia come prodotto di trasposizioni, allora e hanno la stessa parità, cioè sono entrambi pari o entrambi dispari.
Una permutazione è detta pari o dispari a seconda che sia ottenibile come prodotto di un numero pari o dispari di trasposizioni. Il segno di è definito rispettivamente come e
Proprietà
modificaDefinito il prodotto di due permutazioni come la composizione delle stesse, si può dire che la funzione segno è moltiplicativa, cioè
Ne consegue che
Gruppo alternante
modificaMetà delle permutazioni di un insieme di elementi sono pari. Poiché la funzione segno è moltiplicativa, le permutazioni pari formano un sottogruppo normale di indice due del gruppo simmetrico delle permutazioni dell'insieme , detto gruppo alterno e indicato con Si tratta del nucleo dell'omomorfismo di gruppi
L'immagine è un gruppo ciclico con due elementi.
Formula per il segno
modificaFissiamo un elemento nella notazione a 2 linee:
Consideriamo la coppia con dicesi inversione per se si verifica . Supponendo di ottenere inversioni, allora il segno della permutazione può essere calcolato tramite la formula seguente:
Esempi
modificaTutte le trasposizioni, cioè i 2-cicli del tipo , sono dispari.
Ad esempio nel gruppo simmetrico abbiamo i seguenti 3 casi possibili per le coppie e in diventano 6 casi .
Facciamo vedere che in con 6 elementi vi sono:
- pari;
- dispari.
Infatti per
si ottiene
quindi possiamo anche dire che e . Lo stesso discorso si applica per le restanti riflessioni e
Per si ottiene
quindi possiamo anche dire che e . Lo stesso discorso si applica per le restanti e . Le tre permutazioni pari formano il sottogruppo normale alterno .
Note
modifica- ^ (EN) Neal H. McCoy, Introduction To Modern Algebra, Revised Edition, Boston, Allyn & Bacon, 1968, LCCN 68015225.
- ^ (EN) Lang S., II. Groups, in Undergraduate Algebra, 3ª ed., Springer Verlag, 2005, ISBN 978-0387220253.
Bibliografia
modifica- 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
modificaAltri progetti
modificaWikizionario contiene il lemma di dizionario «permutazione»
Wikimedia Commons contiene immagini o altri file sulla permutazione
Collegamenti esterni
modifica- 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) Denis Howe, permutation, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
- Permutazione, in Grande Dizionario di Italiano, Garzanti Linguistica.
Controllo di autorità | Thesaurus BNCF 32734 · J9U (EN, HE) 987007536403105171 |
---|