permutazione

Tutte e sei le permutazioni di tre palline colorate

Per permutazione (dal latino permutare , rovescio' ) si intende nella combinatoria una disposizione di oggetti in un ordine specifico . A seconda che alcuni oggetti possano o meno apparire più volte, si parla di una permutazione con ripetizione o di una permutazione senza ripetizione. Il numero di permutazioni senza ripetizione risulta fattoriale , mentre il numero di permutazioni con ripetizione è dato tramite coefficienti multinomiali .

Nella teoria dei gruppi , una permutazione senza ripetizione è un'automappatura biunivoca di un insieme solitamente finito , per cui i primi numeri naturali sono solitamente usati come insiemi di riferimento . L'insieme delle permutazioni dei primi numeri naturali forma il gruppo simmetrico di grado con l' esecuzione consecutiva come collegamento . L' elemento neutro di questo gruppo rappresenta la permutazione identica, mentre l' elemento inverso è la permutazione inversa. I sottogruppi del gruppo simmetrico sono i gruppi di permutazione . ${\ stile di visualizzazione n}$${\ stile di visualizzazione n}$

Parametri importanti delle permutazioni sono il loro tipo di ciclo , il loro ordine e il loro segno . Con l'aiuto delle posizioni mancanti di una permutazione, si può definire un ordine parziale sull'insieme delle permutazioni di lunghezza fissa . Utilizzando la sua tabella di inversione , a ciascuna permutazione può anche essere assegnato un numero univoco in un sistema di numerazione basato sulla facoltà . Importanti classi di permutazioni sono le permutazioni cicliche , prive di punto fisso , auto-inverse e alternate .

Le permutazioni hanno una vasta gamma di usi all'interno e all'esterno della matematica , ad esempio in algebra lineare ( formula di Leibniz ), analisi ( riorganizzazione delle righe ), teoria dei grafi e teoria dei giochi , crittografia ( metodo di crittografia ) , informatica ( metodo di ordinamento ) e quantistica. meccanica ( principio di Pauli ).

Basi combinatorie

Permutazioni di quattro palline colorate senza ripetizione (sinistra) e con ripetizione (centro e destra).

Problema

Una permutazione è una disposizione di oggetti in un certo ordine o una riorganizzazione di oggetti da un dato ordine. Esempi di permutazioni sono:

• Un anagramma è una permutazione delle lettere in una parola, come GRANDSON e CARNATION.
• La miscelazione delle carte in un gioco di carte dà una permutazione (idealmente) casuale delle carte.
• Nella pallavolo , cambiare posizione dopo aver conquistato il diritto di servire è una permutazione ciclica dei giocatori.
• Molti metodi di ordinamento funzionano con trasposizioni successive, cioè permutazioni che scambiano esattamente due oggetti.

Se non tutti gli oggetti sono selezionati in una tale disposizione, si parla di una variazione invece di una permutazione ; la sequenza nella selezione non ha importanza, di una combinazione . Nel conteggio combinatorio , sorge la questione del numero di possibili permutazioni. Qui viene fatta una distinzione tra il caso in cui tutti gli oggetti sono diversi e il caso in cui alcuni degli oggetti sono identici.

Permutazione senza ripetizione

Una permutazione senza ripetizione è una disposizione di oggetti che sono tutti distinguibili. Poiché ci sono opzioni di posizionamento per il primo oggetto, ci sono solo opzioni per il secondo oggetto , solo per il terzo oggetto e così via fino all'ultimo oggetto, che ha solo uno spazio libero rimasto. Il numero di possibili permutazioni degli oggetti è quindi dato dal fattoriale${\ stile di visualizzazione n}$${\ stile di visualizzazione n}$${\ stile di visualizzazione n-1}$${\ stile di visualizzazione n-2}$${\ stile di visualizzazione n}$

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

specificato.

Ad esempio, sono possibili disposizioni di quattro palline di colore diverso in fila. ${\ displaystyle 4! = 4 \ volte 3 \ volte 2 \ volte 1 = 24}$

Permutazione con ripetizione

Una permutazione con ripetizione è una disposizione di oggetti, alcuni dei quali sono indistinguibili. Se esattamente gli oggetti sono identici, questi possono essere scambiati al loro posto senza che venga creato un nuovo ordine. In questo modo, le disposizioni sono esattamente le stesse. Il numero di permutazioni di oggetti, di cui sono identici, è quindi dato dal fattoriale decrescente${\ stile di visualizzazione n}$${\ stile di visualizzazione k}$${\ displaystyle k!}$${\ stile di visualizzazione n}$${\ stile di visualizzazione k}$

${\ displaystyle {\ frac {n!} {k!}} = n \ cdot (n-1) \ cdot \ ldots \ cdot (k + 1) = n ^ {\ sottolinea {nk}}}$

dato. Se non c'è solo uno, ma gruppi, ciascuno con oggetti identici, allora tutti questi oggetti possono essere scambiati al loro posto senza creare nuove disposizioni. Se si contano anche gli oggetti che si verificano una sola volta con una molteplicità , allora vale quanto segue e il numero di possibili permutazioni è dato dal coefficiente multinomiale${\ stile di visualizzazione}$${\ displaystyle k_ {1}, \ ldots, k_ {s}}$${\ stile di visualizzazione 1}$${\ displaystyle k_ {1} + \ ldots + k_ {s} = n}$

${\ displaystyle {\ frac {n!} {k_ {1}! \ cdot \ ldots \ cdot k_ {s}!}} = {\ binom {n} {k_ {1}, \ ldots, k_ {s}} }}$

specificare.

Ad esempio, ci sono possibili disposizioni di quattro palline colorate in fila se esattamente due delle palline hanno lo stesso colore e possibili disposizioni se due palline sono ciascuna dello stesso colore . ${\ displaystyle {\ tfrac {4!} {2! \, 1! \, 1!}} = {\ tfrac {24} {2}} = 12}$${\ displaystyle {\ tfrac {4!} {2! \, 2!}} = {\ tfrac {24} {4}} = 6}$

Algoritmi

Esistono numerosi algoritmi per la generazione sistematica di tutte le permutazioni di n elementi, che spesso possono essere formulati in modo ricorsivo. Questi includono l' algoritmo Steinhaus-Johnson-Trotter e l' algoritmo heap .

definizione

Sia un insieme con elementi , quindi una permutazione a -digit (senza ripetizione) è una mappatura biunivoca${\ displaystyle X = \ {x_ {1}, x_ {2}, \ ldots, x_ {n} \}}$${\ stile di visualizzazione n}$ ${\ stile di visualizzazione n}$

${\ displaystyle \ pi \ due punti X \ freccia destra X}$,

che assegna un elemento dello stesso insieme a ciascun elemento dell'insieme. Vividamente prende ogni elemento della permutazione per il luogo del suo elemento associato uno. A causa della biiettività della mappatura, due elementi diversi non vengono mai mappati sullo stesso elemento. Anche il caso è ammissibile ed è quindi l' insieme vuoto . ${\ displaystyle x_ {i}}$${\ displaystyle i = 1, \ ldots, n}$${\ displaystyle \ pi (x_ {i})}$${\ stile di visualizzazione n = 0}$${\ stile di visualizzazione X}$

Poiché, per definizione, ogni insieme finito è uguale a un insieme della forma {1, 2, ..., n} , ci si può sempre limitare ai primi numeri naturali come insieme di riferimento quando si considerano matematicamente le permutazioni . Una permutazione è quindi una mappatura biunivoca${\ stile di visualizzazione n}$

${\ displaystyle \ pi \ due punti \ {1,2, \ ldots, n \} \ freccia destra \ {1,2, \ ldots, n \}}$,

che assegna ogni numero naturale compreso tra ed esattamente un numero nello stesso intervallo. Se immagini tutti i numeri in una lista, il numero prende il posto del numero attraverso la permutazione . ${\ stile di visualizzazione 1}$${\ stile di visualizzazione n}$${\ stile di visualizzazione n}$${\ displaystyle j \ in \ {1, \ ldots, n \}}$${\ displaystyle \ pi (j)}$

notazione

Modulo a due righe

Nella rappresentazione dettagliata di una permutazione -digit , questa è scritta come una matrice con due righe e due colonne. Nella riga superiore ci sono i numeri da a (in qualsiasi ordine). Il valore della funzione si trova quindi sotto ogni numero nella seconda riga : ${\ stile di visualizzazione n}$${\ displaystyle \ pi}$${\ stile di visualizzazione n}$${\ stile di visualizzazione 1}$${\ stile di visualizzazione n}$${\ displaystyle j \ in \ {1, \ ldots, n \}}$${\ displaystyle \ pi (j)}$

${\ displaystyle \ pi = {\ begin {pmatrix} 1 & 2 & \ cdots & n \\\ pi \ left (1 \ right) & \ pi \ left (2 \ right) & \ cdots & \ pi \ left ( n \ destra) \ fine {pmatrix}}}$

La seconda riga contiene anche ogni numero da a esattamente una volta. ${\ stile di visualizzazione 1}$${\ stile di visualizzazione n}$

esempio

La permutazione con ed è nella forma a due righe di ${\ displaystyle \ pi \ due punti \ {1,2,3,4 \} \ freccia destra \ {1,2,3,4 \}}$${\ displaystyle \ pi (1) = 2, \ pi (2) = 4, \ pi (3) = 3}$${\ displaystyle \ pi (4) = 1}$

${\ displaystyle \ pi = {\ begin {pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \ end {pmatrix}}}$

scritto.

notazione tupla

Con la notazione di tupla più compatta, scrivi semplicemente i valori della funzione in una riga: ${\ displaystyle \ pi (j)}$

${\ displaystyle \ pi = \ left (\ pi (1), \ pi (2), \ dotsc, \ pi (n) \ right)}$

Questa notazione quindi utilizza solo la seconda riga della forma a due righe. Poiché le informazioni sul numero a cui è mappato vengono perse, la notazione della tupla può essere utilizzata solo se è nota la sequenza dei numeri della prima riga. Di solito questo è l'ordine naturale. La notazione della tupla può essere facilmente confusa con la notazione del ciclo (vedi sezione seguente), soprattutto perché alcuni autori omettono le virgole. ${\ stile di visualizzazione j}$${\ displaystyle \ pi (j)}$

esempio

Per la permutazione dell'esempio sopra si ottiene la notazione della tupla

${\ displaystyle \ pi = (2, ~ 4, ~ 3, ~ 1)}$.

Notazione del ciclo

Anche la notazione del ciclo richiede solo una riga. Inizi con qualsiasi numero e scrivi ${\ displaystyle a \ in \ {1, \ ldots, n \}}$

${\ displaystyle \ left (a \; \ pi (a) \; \ pi ^ {2} (a) \; \ cdots \; \ pi ^ {\ ell _ {a} -1} (a) \ right) }$,

dove l' esecuzione -fold consecutiva di denota e il numero naturale più piccolo è con . Tale parentesi è chiamata ciclo ed è la sua lunghezza. Se ci sono altri numeri che non sono ancora stati annotati, scegli un tale numero e scrivi un altro ciclo di lunghezza dopo di esso. Continui finché non annoti ogni numero esattamente una volta. Le parentesi contenenti un solo numero possono quindi essere nuovamente eliminate. Questa rappresentazione non è chiara, perché l'ordine dei cicli può essere selezionato a piacere e i numeri possono essere scambiati ciclicamente in ogni ciclo. ${\ displaystyle \ pi ^ {k}}$${\ stile di visualizzazione k}$${\ displaystyle \ pi}$${\ displaystyle \ ell _ {a}}$${\ displaystyle \ pi ^ {\ ell _ {a}} (a) = a}$${\ displaystyle \ ell _ {a}}$${\ stile di visualizzazione b}$${\ displaystyle (b \; \ pi (b) \; \ cdots \; \ pi ^ {\ ell _ {b} -1} (b))}$${\ displaystyle \ ell _ {b}}$

esempio

La seguente notazione del ciclo viene utilizzata per la permutazione di esempio sopra:

${\ displaystyle \ pi = (1 ~ 2 ~ 4) (3) = (1 ~ 2 ~ 4) = (2 ~ 4 ~ 1) = (4 ~ 1 ~ 2)}$

Ulteriori rappresentazioni

Rappresentazione grafica

Grafico della permutazione ${\ stile di visualizzazione (1 ~ 2 ~ 4 ~ 3) (5) (6 ~ 7)}$

Il grafo di una permutazione a -digit è un grafo diretto con un insieme di nodi e un insieme di archi ${\ stile di visualizzazione n}$${\ displaystyle \ pi}$ ${\ stile di visualizzazione (V, E)}$${\ displaystyle V = \ {1,2, \ ldots, n \}}$

${\ displaystyle E = \ {(i, \ pi (i)) \ mid i = 1, \ ldots, n \}}$.

In un tale grafo, ogni nodo ha esattamente un arco in uscita ed esattamente un arco in entrata. I cicli del grafico sono precisamente i cicli della permutazione, con i numeri che sono tenuti dalla permutazione creando loop ai nodi associati. Il grafico di una permutazione è connesso solo se la permutazione consiste in un unico ciclo di lunghezza . ${\ stile di visualizzazione n}$

Matrici di permutazione

${\ displaystyle {\ begin {pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\\ end {pmatrix} }}$ Matrice di permutazione della permutazione ${\ stile di visualizzazione (2,4,3,1)}$

La matrice di permutazione di una permutazione a -digit è data da ${\ displaystyle P _ {\ pi} \ in \ {0,1 \} ^ {n \ volte n}}$${\ stile di visualizzazione n}$${\ displaystyle \ pi}$

${\ displaystyle P _ {\ pi} = {\ begin {pmatrix} p_ {11} & \ punti & p_ {1n} \\\ vdots & \ ddots & \ vdots \\ p_ {n1} & \ punti & p_ { nn} \ end {pmatrix}} \ quad {\ text {with}} \ quad p_ {ij} = \ delta _ {\ pi (i), j} = {\ begin {cases} 1, & {\ text { if}} \ pi (i) = j \\ 0, & {\ text {altrimenti}} \ end {casi}}}$

definito, dove il delta di Kronecker denota. Se il numero è mappato sul numero da una permutazione , allora la matrice di permutazione associata nella riga -esima ne ha una nella colonna . Gli elementi di un vettore colonna sono in algebra lineare permutati caratterizzati dal fatto che il vettore da sinistra per la matrice di permutazione moltiplicato è: ${\ displaystyle \ delta _ {ij}}$${\ stile di visualizzazione i}$${\ displaystyle \ pi (i)}$${\ stile di visualizzazione i}$${\ stile di visualizzazione 1}$${\ displaystyle \ pi (i)}$ ${\ stile di visualizzazione (x_ {1}, \ puntic, x_ {n}) ^ {T}}$${\ displaystyle P _ {\ pi}}$

${\ displaystyle (x _ {\ pi (1)}, \ ldots, x _ {\ pi (n)}) ^ {T} = P _ {\ pi} \ cdot (x_ {1}, \ dotsc, x_ {n} ) ^ {T}}$.

Permutazioni come gruppo

Le permutazioni dell'insieme formano un gruppo con l'esecuzione sequenziale come collegamento , il gruppo simmetrico . I gruppi simmetrici giocano un ruolo importante in matematica. Ad esempio, secondo il teorema di Cayley, ogni gruppo finito è isomorfo a un sottogruppo di un gruppo simmetrico . I sottogruppi del gruppo simmetrico sono chiamati gruppi di permutazione . ${\ displaystyle \ {1,2, \ dotsc, n \}}$ ${\ displaystyle S_ {n}}$

Il gruppo di Galois nella teoria (classica) di Galois è un tale sottogruppo del gruppo simmetrico: Gli zeri dei polinomi sono permutati . Le proprietà del gruppo di Galois forniscono informazioni sulla risolubilità di un'equazione polinomiale per radicali, i. h. per espressioni radice. Questo può essere usato per dimostrare, ad esempio, che l'equazione polinomiale generale di quinto grado o superiore non può essere risolta per radicali ( teorema di Abel-Ruffini ).

composizione

Le permutazioni a due cifre possono essere eseguite una dopo l'altra applicando prima la prima permutazione e poi applicando la seconda permutazione al risultato. L'esecuzione consecutiva si scrive come ${\ stile di visualizzazione n}$${\ displaystyle \ pi, \ tau \ in S_ {n}}$

${\ displaystyle \ tau \ circ \ pi}$,

applicando prima e poi . Questa esecuzione sequenziale è anche chiamata composizione , collegamento o prodotto di due permutazioni e il risultato è di nuovo una permutazione a cifre. La composizione delle permutazioni non è commutativa , cioè generalmente e dà risultati diversi. Il gruppo simmetrico non è quindi abeliano . Tuttavia, la composizione è associativa, cioè si applica a tutte le permutazioni${\ displaystyle \ pi}$${\ displaystyle \ tau}$${\ stile di visualizzazione n}$${\ displaystyle \ tau \ circ \ pi}$${\ displaystyle \ pi \ circ \ tau}$${\ displaystyle S_ {n}}$${\ stile di visualizzazione n> 2}$${\ displaystyle \ pi, \ tau, \ sigma \ in S_ {n}}$

${\ displaystyle \ sigma \ circ (\ tau \ circ \ pi) = (\ sigma \ circ \ tau) \ circ \ pi}$.

Esempi

È per esempio

${\ displaystyle {\ begin {pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \ end {pmatrix}} \ circ {\ begin {pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \ end { pmatrix}} = {\ begin {pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \ end {pmatrix}}}$.

Per ottenere il risultato si applicano le permutazioni da destra a sinistra e si segue il percorso dei singoli numeri. Questo è mappato su se stesso nella seconda permutazione e poi su , cioè nel suo insieme nella prima permutazione . La via è di conseguenza , così . Alla fine va la strada , nel risultato . ${\ stile di visualizzazione 1}$${\ stile di visualizzazione 3}$${\ displaystyle 1 \ mapsto 1 \ mapsto 3}$${\ displaystyle 1 \ mapsto 3}$${\ stile di visualizzazione 2}$${\ displaystyle 2 \ mapsto 3 \ mapsto 2}$${\ displaystyle 2 \ mapsto 2}$${\ stile di visualizzazione 3}$${\ displaystyle 3 \ mapsto 2 \ mapsto 1}$${\ displaystyle 3 \ mapsto 1}$

Nella visualizzazione del ciclo, la procedura è analoga, per cui vengono registrati i numeri che non compaiono in un ciclo. Ad esempio è

${\ displaystyle (1 ~ 2 ~ 3) \ circ (2 ~ 3 ~ 4) = {\ begin {pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \ end {pmatrix}} = ( 1 ~ 2) (3 ~ 4)}$.

Qui abbiamo determinato i percorsi , , e . ${\ displaystyle 1 \ mapsto 1 \ mapsto 2}$${\ displaystyle 2 \ mapsto 3 \ mapsto 1}$${\ displaystyle 3 \ mapsto 4 \ mapsto 4}$${\ displaystyle 4 \ mapsto 2 \ mapsto 3}$

Permutazione identica

L' elemento neutro del gruppo simmetrico è la permutazione identica${\ displaystyle S_ {n}}$

${\ displaystyle \ operatorname {id} = {\ begin {pmatrix} 1 & 2 & 3 & \ ldots & n \\ 1 & 2 & 3 & \ ldots & n \ end {pmatrix}} \ in S_ {n}}$,

cioè, la permutazione che lascia tutti i numeri al loro posto. Quindi per ogni permutazione${\ displaystyle \ pi \ in S_ {n}}$

${\ displaystyle \ operatorname {id} \ circ \, \ pi = \ pi \ circ \ operatorname {id} = \ pi}$.

La permutazione identica è anche annotata come parentesi vuote , come o come . La matrice di permutazione della permutazione identica è la matrice identità . Il grafico di permutazione identico ha un solo ciclo in ogni nodo. L'identica permutazione di lunghezza uno è anche conosciuta come permutazione banale . ${\ stile di visualizzazione ()}$${\ stile di visualizzazione (1)}$${\ displaystyle \ epsilon}$

permutazione inversa

Per ogni permutazione esiste esattamente un elemento inverso , la permutazione inversa , con, ${\ displaystyle \ pi \ in S_ {n}}$${\ displaystyle \ pi ^ {- 1}}$

${\ displaystyle \ pi \ circ \ pi ^ {- 1} = \ pi ^ {- 1} \ circ \ pi = \ operatorname {id}}$.

La permutazione inversa si ottiene scambiando le righe superiore e inferiore nella forma a due righe:

${\ displaystyle \ pi ^ {- 1} = {\ begin {pmatrix} \ pi \ left (1 \ right) & \ pi \ left (2 \ right) & \ cdots & \ pi \ left (n \ destra) \ \ 1 & 2 & \ cdots & n \ end {pmatrix}}}$

Nella notazione del ciclo, la permutazione inversa si ottiene scrivendo i numeri in ordine inverso in ogni ciclo. Nel grafico della permutazione inversa, sono invertite solo le direzioni di tutti gli archi. La matrice di permutazione della permutazione inversa è la matrice trasposta della permutazione iniziale.

esempio

La permutazione inversa di

${\ displaystyle \ pi = {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 5 & 1 & 3 \ end {pmatrix}} = (1 ~ 2 ~ 4) (3 ~ 5 )}$

è

${\ displaystyle \ pi ^ {- 1} = {\ begin {pmatrix} 2 & 4 & 5 & 1 & 3 \\ 1 & 2 & 3 & 4 & 5 \ end {pmatrix}} = {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 1 & 5 & 2 & 3 \ end {pmatrix}} = (4 ~ 2 ~ 1) (5 ~ 3)}$.

coniugazione

Due permutazioni si dicono coniugate tra loro se esiste una permutazione tale che ${\ displaystyle \ sigma, \ pi \ in S_ {n}}$${\ displaystyle \ tau \ in S_ {n}}$

${\ displaystyle \ sigma = \ tau \ circ \ pi \ circ \ tau ^ {- 1}}$   o.   ${\ displaystyle \ sigma \ circ \ tau = \ tau \ circ \ pi}$

si applica. La permutazione è il numero al numero visualizzato, quindi la permutazione è il numero al numero da. La coniugazione rappresenta una relazione di equivalenza sull'insieme delle permutazioni di lunghezza fissa, cioè è riflessiva ( ), simmetrica (da segue ) e transitiva (da e segue ). L'insieme di tutte le permutazioni coniugate a una permutazione forma una classe di equivalenza (la classe di coniugazione ), che si nota da. ${\ displaystyle \ pi}$${\ stile di visualizzazione i}$${\ stile di visualizzazione j}$${\ displaystyle \ sigma}$${\ displaystyle \ tau (i)}$${\ displaystyle \ tau (j)}$ ${\ displaystyle \ sim}$${\ displaystyle \ pi \ sim \ pi}$${\ displaystyle \ pi \ sim \ sigma}$${\ displaystyle \ sigma \ sim \ pi}$${\ displaystyle \ pi \ sim \ sigma}$${\ displaystyle \ sigma \ sim \ tau}$${\ displaystyle \ pi \ sim \ tau}$${\ displaystyle \ pi \ in S_ {n}}$${\ displaystyle \ sinistra [\ pi \ destra]}$

esempio

Il gruppo simmetrico ha le tre classi di coniugazione: ${\ displaystyle S_ {3}}$

${\ displaystyle [\ operatorname {id}] = \ {\ operatorname {id} \}}$

${\ displaystyle [(1 ~ 2)] = \ {(1 ~ 2), (1 ~ 3), (2 ~ 3) \}}$

${\ displaystyle [(1 ~ 2 ~ 3)] = \ {(1 ~ 2 ~ 3), (1 ~ 3 ~ 2) \}}$

Parametri

Tipo di ciclo

${\ stile di visualizzazione n}$	Tipo di ciclo	Struttura del ciclo	numero
1	1 1	(•)	1
2	1 2	(•) (•)	1
	2 1	(• •)	1
3	1 3	(•) (•) (•)	1
	1 1 2 1	(• •) (•)	3
	3 1	(• • •)	2
4°	1 4	(•) (•) (•) (•)	1
	1 2 2 1	(• •) (•) (•)	6°
	2 2	(• •) (• •)	3
	1 1 3 1	(• • •) (•)	8°
	4 1	(• • • •)	6°

Indicato per il numero di cicli di lunghezza in una permutazione , allora il tipo di ciclo di questa permutazione è l'espressione formale ${\ displaystyle b_ {j}}$${\ displaystyle j = 1, \ ldots, n}$${\ stile di visualizzazione j}$${\ displaystyle \ pi \ in S_ {n}}$

${\ displaystyle \ operatorname {typ} (\ pi) = 1 ^ {b_ {1}} 2 ^ {b_ {2}} \ ldots n ^ {b_ {n}}}$,

per cui i termini non devono essere elencati. Formale qui significa che il prodotto e le potenze non sono effettivamente calcolati. Il numero di possibili tipi di ciclo con permutazioni a -cifre corrisponde esattamente al numero di partizioni del numero . Il numero di permutazioni per tipo di ciclo può essere calcolato dalla descrizione del tipo. La permutazione inversa ha sempre lo stesso tipo di ciclo della permutazione iniziale. Inoltre, il risultato della composizione di due permutazioni ha lo stesso tipo di ciclo indipendentemente dall'ordine degli operandi. Di conseguenza, due permutazioni sono coniugate tra loro se e solo se sono dello stesso tipo di ciclo. Le permutazioni dello stesso tipo di ciclo formano quindi le classi di coniugazione del gruppo simmetrico . Le permutazioni con lo stesso numero di cicli si contano con i numeri di Stirling della prima specie. ${\ displaystyle b_ {j} = 0}$${\ stile di visualizzazione n}$${\ stile di visualizzazione n}$${\ displaystyle S_ {n}}$

ordine

L'ordine di una permutazione è il più piccolo numero naturale tale che l' esecuzione uno dopo l' altro risulti nella permutazione identica: ${\ displaystyle \ pi}$${\ stile di visualizzazione k}$${\ stile di visualizzazione k}$${\ displaystyle \ pi}$

${\ displaystyle \ operatorname {ord} (\ pi) = \ min \ {k \ in \ mathbb {N} \ mid \ pi ^ {k} = \ operatorname {id} \}}$.

L'ordine di una permutazione è quindi l'ordine degli elementi di come elemento di gruppo del gruppo simmetrico. Dalla rappresentazione del ciclo di una permutazione, l'ordine può essere determinato come il minimo comune multiplo delle lunghezze dei cicli disgiunti . Ad esempio, l'ordine della permutazione è il minimo comune multiplo di tre e due, cioè sei. ${\ displaystyle \ pi}$${\ displaystyle \ pi}$${\ stile di visualizzazione (124) (35)}$

carenze

Una coppia di numeri è chiamata errore o inversione di una permutazione , se e si applica. Quindi due numeri formano un errore se e solo se, dopo aver applicato la permutazione, il maggiore precede il minore. L'insieme degli errori in una permutazione è quindi attraverso ${\ stile di visualizzazione (i, j)}$${\ displaystyle \ pi}$${\ stile di visualizzazione i <j}$${\ displaystyle \ pi (i)> \ pi (j)}$${\ displaystyle \ pi \ in S_ {n}}$

${\ displaystyle \ operatorname {inv} (\ pi) = \ left \ {(i, j) \ in \ {1, \ ldots, n \} ^ {2} \ mid i <j ~ {\ text {and} } ~ \ pi (i)> \ pi (j) \ destra \}}$

dato. Il numero di errori in una permutazione è chiamato numero di errore o numero di inversione della permutazione. Il numero mancante può essere visto come una misura del disordine dei numeri scambiati dalla permutazione. ${\ displaystyle | \ nomeoperatore {inv} (\ pi) |}$

cartello

Il segno di una permutazione è il numero ${\ displaystyle \ pi \ in S_ {n}}$

${\ displaystyle \ operatorname {sign} (\ pi) = \ left (-1 \ right) ^ {| \ operatorname {inv} (\ pi) |}}$.

Una permutazione ha quindi segno se il suo numero mancante è pari, altrimenti ha segno . Nel primo caso si parla di permutazione pari e nel secondo caso di permutazione dispari. L'insieme delle permutazioni pari forma un sottogruppo del gruppo simmetrico , il gruppo alternato . ${\ stile di visualizzazione +1}$${\ stile di visualizzazione -1}$${\ displaystyle S_ {n}}$ ${\ displaystyle A_ {n}}$

Salite e discese

Un aumento in una permutazione è un numero che vale per. L'insieme degli incrementi in una permutazione è quindi attraverso ${\ displaystyle \ pi \ in S_ {n}}$${\ stile di visualizzazione i}$${\ displaystyle \ pi (i + 1)> \ pi (i)}$

${\ displaystyle \ operatorname {asc} (\ pi) = \ left \ {i \ in \ {1, \ ldots, n-1 \} \ mid \ pi (i + 1)> \ pi (i) \ right \ }}$

dato. Lo stesso vale per una discesa . Il numero di permutazioni con incrementi o decrementi esatti è dato dai numeri di Eulero . Un massimo, vale a dire non più estensibile su entrambi i lati ${\ displaystyle \ pi (i + 1) <\ pi (i)}$${\ displaystyle S_ {n}}$${\ stile di visualizzazione k}$ ${\ displaystyle \ textstyle \ left \ langle \! {n \ atop k} \! \ right \ rangle}$

${\ displaystyle (\ pi (i), \ pi (i + 1), \ ldots, \ pi (i + l))}$

successivamente aumentando o diminuendo il numero in una permutazione è chiamato aumentando o diminuendo corsa di lunghezza . Per tale sequenza può consistere solo di un numero. Se una permutazione ha un totale di salite o discese, è composta da piste discendenti e ascendenti. Di conseguenza, il numero di permutazioni con esecuzioni esattamente crescenti o decrescenti è dato da. ${\ stile di visualizzazione l + 1}$${\ stile di visualizzazione l = 0}$${\ stile di visualizzazione k}$${\ stile di visualizzazione k + 1}$${\ displaystyle S_ {n}}$${\ stile di visualizzazione k}$${\ displaystyle \ textstyle \ left \ langle \! {n \ atop k-1} \! \ right \ rangle}$

Proprietà dell'ordine

preparativi

Diagramma di Hasse delle permutazioni in S ₄ . I bordi blu, verde e rosso corrispondono agli scambi vicini (1 2), (2 3) e (3 4), che, visti dal basso verso l'alto, producono sempre esattamente una posizione mancante.

Usando gli oggetti sbagliati può essere sul set di uno permutazioni -bit ordine parziale da ${\ stile di visualizzazione n}$

${\ displaystyle \ pi \ leq \ tau \ Leftrightarrow \ operatorname {inv} (\ pi) \ subseteq \ operatorname {inv} (\ tau)}$,

definire, dove sono. L'elemento minimo rispetto a questo ordine è la permutazione identica, mentre l'elemento massimo è la permutazione che inverte l'ordine di tutti i numeri. Nel diagramma di Hasse associato , due permutazioni sono collegate da un bordo se emergono l' una dall'altra attraverso uno scambio vicino . I nodi e gli archi del diagramma di Hasse formano un grafo di Cayley che è isomorfo al grafo degli archi del corrispondente permutaedro . Il permutaedro è un politopo convesso nello spazio -dimensionale, che nasce dal fatto che le permutazioni dell'insieme sono interpretate come vettori di coordinate e quindi si forma l' inviluppo convesso di questi punti. ${\ displaystyle \ pi, \ tau \ in S_ {n}}$${\ stile di visualizzazione n}$${\ displaystyle \ {1, \ ldots, n \}}$

enumerazione

La tabella di inversione o vettore di inversione di una permutazione assegna a ciascun numero il numero di guasti che genera. Indica il numero di numeri che si trovano a sinistra di nella rappresentazione della tupla e sono maggiori di , quindi il vettore di inversione di una permutazione è attraverso ${\ displaystyle \ pi \ in S_ {n}}$${\ displaystyle 1 \ leq j \ leq n}$${\ displaystyle b_ {j}}$${\ displaystyle \ pi}$${\ stile di visualizzazione j}$${\ stile di visualizzazione j}$

${\ displaystyle I (\ pi) = (b_ {1}, b_ {2}, \ ldots, b_ {n})}$

dato. Al contrario, la permutazione sottostante può essere chiaramente determinata dal vettore di inversione . Sommando il vettore di inversione come un numero in un sistema numerico basato sulla facoltà , ogni permutazione può essere un numero univoco per ${\ stile di visualizzazione I (\ pi)}$${\ displaystyle \ pi}$${\ displaystyle \ pi \ in S_ {n}}$${\ displaystyle z (\ pi) \ in \ {0, \ ldots, n! -1 \}}$

${\ displaystyle z (\ pi) = \ sum _ {i = 1} ^ {n} b_ {i} \ cdot (ni)!}$

assegnare. Invece del vettore di inversione, viene utilizzato anche il codice Lehmer per numerare le permutazioni.

simmetrie

La permutazione complementare a una permutazione è ${\ displaystyle \ pi \ in S_ {n}}$

${\ displaystyle \ pi ^ {-} = (n- \ pi (1) +1, \ ldots, n- \ pi (n) +1)}$.

La permutazione complementare viene creata rispecchiando orizzontalmente la matrice di permutazione. La permutazione inversa è simile

${\ displaystyle \ pi '= (\ pi (n), \ pi (n-1), \ ldots, \ pi (1))}$

ed è creato dalla riflessione verticale. Le permutazioni complementari e inverse hanno lo stesso tipo di ciclo e lo stesso ordine della permutazione iniziale. Tuttavia, il numero di salite e discese è invertito nel caso di permutazioni complementari e inverse. Inoltre, il segno è invertito per permutazioni complementari e per permutazioni inverse con lunghezza 2 modulo 4 o lunghezza 3 modulo 4. L'inverso della permutazione complementare è uguale all'inverso inverso e l'inverso della permutazione inversa è uguale all'inverso complementare.

Permutazioni speciali

permutazioni cicliche

Grafico di una permutazione ciclica di lunghezza 6

Una permutazione che scambia ciclicamente i numeri e lascia fissi i numeri rimanenti è chiamata permutazione ciclica o ciclo ed è scritta come un singolo ciclo di lunghezza . Un ciclo, cioè uno scambio di due numeri, è anche chiamato trasposizione. La concatenazione delle permutazioni cicliche è commutativa se hanno portatori disgiunti. Anche l'inverso di una permutazione ciclica è sempre ciclico, così come le potenze di una permutazione ciclica la cui lunghezza è un numero primo. Ogni permutazione ciclica può essere scomposta in singole trasposizioni (non disgiunte) e ha segno pari se e solo se la sua lunghezza è dispari. ${\ stile di visualizzazione k}$${\ stile di visualizzazione k}$${\ stile di visualizzazione k}$${\ stile di visualizzazione 2}$

Permutazioni senza punto fisso

Grafico di una permutazione libera a punto fisso dei numeri da 1 a 8

I numeri che sono tenuti da una permutazione sono chiamati punti fissi della permutazione. Nella forma a due righe, i punti fissi possono essere riconosciuti dal fatto che le voci superiore e inferiore della rispettiva colonna sono le stesse. Nella notazione del ciclo, i punti fissi sono esattamente i cicli delle unità oi numeri che non compaiono. Nella matrice di permutazione, gli elementi assegnati ai punti fissi sono la diagonale principale . Una permutazione senza punti fissi non contiene nessuno dei numeri ed è anche chiamata squilibrio. Il numero di permutazioni a punto fisso dei numeri da a può essere calcolato dalla sub-facoltà . Per l'aumento , la proporzione delle permutazioni senza punto fisso tende molto rapidamente contro il reciproco del numero di Eulero . Se alcuni degli elementi di una permutazione devono rimanere al loro vecchio posto, si parla di uno squilibrio parziale, il cui numero può essere determinato utilizzando i numeri di Rencontres . ${\ stile di visualizzazione 1}$${\ stile di visualizzazione 1}$${\ stile di visualizzazione n}$ ${\ displaystyle {!} n}$${\ stile di visualizzazione n}$ ${\ stile di visualizzazione e}$

Permutazioni autoinverse

Grafico di una permutazione autoinversa dei numeri da 1 a 8

Una permutazione con o equivalente ad essa è chiamata involuzione o autoinversa. Le involuzioni sono precisamente le permutazioni dell'ordine due così come l'identità stessa (l'unica permutazione dell'ordine uno). Una permutazione è un'involuzione se e solo se la sua rappresentazione del ciclo contiene un massimo di cicli di lunghezza due, cioè trasposizioni. La matrice di permutazione di una permutazione autoinversa è sempre simmetrica . Le permutazioni auto-inverse svolgono un ruolo importante nella crittografia , vale a dire se un messaggio viene crittografato utilizzando una permutazione auto-inversa, il messaggio può anche essere nuovamente decifrato utilizzando la stessa permutazione. ${\ displaystyle \ pi}$${\ displaystyle \ pi ^ {2} = {\ mbox {id}}}$${\ displaystyle \ pi ^ {- 1} = \ pi}$

Un esempio di permutazione autoinversa è il mirroring

${\ displaystyle \ sigma _ {n} = {\ begin {pmatrix} 1 & 2 & \ cdots & n \\ n & n-1 & \ cdots & 1 \ end {pmatrix}} = (1 ~ n) (2 ~ (n-1)) ( 3 ~ (n-2)) \ cdots}$,

vedi anche la parola (Informatica Teorica) §Spiegelung und Palindrome .

permutazioni alternate

Una permutazione è detta alternata se non c'è nessun numero nella sua rappresentazione tupla in termini di dimensione tra il numero precedente e il numero successivo . In una permutazione alternata, i numeri scambiati dalla permutazione sono quindi sempre alternativamente maggiori e minori del numero precedente. Se la sequenza di numeri inizia con un aumento, si parla di una permutazione su-giù, e inizia con una diminuzione in una permutazione verso l'alto. Ogni permutazione alternata di lunghezza dispari corrisponde a un albero binario parzialmente ordinato e ogni permutazione alternata di lunghezza pari corrisponde a un tale albero quasi completo. I numeri di permutazione alternata di lunghezza fissa appaiono come coefficienti della serie Maclaurin del le secans e le funzioni tangente e sono strettamente correlate alle Eulero e numeri di Bernoulli . ${\ displaystyle \ pi (j)}$${\ displaystyle \ pi (j-1)}$${\ displaystyle \ pi (j + 1)}$

Permutazioni separabili

Le permutazioni separabili sono permutazioni che possono essere rappresentate come una somma diretta o distorta di permutazioni banali. Tale somma di due permutazioni risulta in una nuova permutazione, la cui lunghezza è la somma delle lunghezze delle due permutazioni iniziali. Nel caso di somma diretta, la seconda permutazione è attaccata alla prima in modo traslato; nel caso di somma inclinata, la prima permutazione è spostata davanti alla seconda. Il numero di permutazioni separabili di lunghezza fissa è dato dai numeri di Schröder . Le permutazioni separabili sono caratterizzate da una speciale struttura a blocchi ricorsiva delle matrici di permutazione associate. Tra le altre cose, vengono esaminati nella teoria dell'ordinamento .

Permutazioni casuali

Una permutazione casuale è una permutazione scelta a caso dall'insieme delle permutazioni. In stocastica , le permutazioni casuali sono viste come variabili casuali da uno spazio di probabilità discreto . In questo modo, le cifre chiave delle permutazioni casuali, come il numero di punti fissi, carenze o cicli, possono essere viste come variabili casuali discrete, le cui distribuzioni di probabilità vengono poi esaminate. Le permutazioni casuali possono essere generate in modo efficiente nel computer utilizzando il metodo Fisher-Yates . Le permutazioni casuali vengono esaminate , tra l'altro, nell'analisi dei processi di ordinamento , nella crittografia e nella teoria dei codici , nonché nel contesto degli algoritmi randomizzati . Il problema dei 100 prigionieri è un puzzle matematico basato su permutazioni casuali. ${\ displaystyle S_ {n}}$

Permutazione in musica

Permutazioni della serie Lulu (Alban Berg)

Sulla permutazione nella composizione della fuga vedere sotto Fuga .

Nella tecnica dodecafonica , una permutazione è la derivazione di ulteriori righe da una riga dodecafonica in quanto, secondo una specifica modalità di selezione numerica, i singoli toni vengono estratti uno dopo l'altro fino a creare una nuova riga dodecafonica completa . Così procede Alban Berg nella sua opera Lulu .

Osservazioni

1. ↑ Occasionalmente anche come mappatura biunivoca

   ${\ displaystyle \ pi \ due punti \ {1,2, \ ldots, n \} \ operatorname {\ twoheadrightarrow \! \! \! \! \! \! \! \! \! \! \! \; \; \ rightarrowtail } \; \ {1,2, \ ldots, n \}}$

   scritto, vedi funzione (matematica) §Simbolismo .
2. ↑ Horst Weber: Article Permutation , in: Das große Lexikon der Musik , a cura di Marc Honnegger e Günter Massenkeil , Herder Verlag Freiburg / Brsg. 1978/1987, Volume 6, ISBN 3-451-20948-9 , pp. 243f

letteratura

• Martin Aigner : Matematica Discreta . Vieweg, 2006, ISBN 3-8348-9039-1 . 
• Michael Artin : Algebra . Birkhäuser, 1998, ISBN 3-7643-5938-2 . 
• Albrecht Beutelspacher : Algebra lineare . 6a edizione riveduta e integrata. Vieweg, 2003, ISBN 3-528-56508-X . 
• Konrad Jacobs , Dieter Jungnickel : Introduzione alla combinatoria . de Gruyter, 2003, ISBN 3-11-016727-1 . 
• Hans Kurzweil, Bernd Stellmacher : Teoria dei gruppi finiti: un'introduzione . Springer, 1998, ISBN 3-540-60331-X . 
• Kristina Reiss , Gernot Stroth : Strutture Finite . Springer, 2011, ISBN 3-642-17181-8 . 

link internet

Wikizionario: Permutazione  - spiegazioni di significati, origini delle parole, sinonimi, traduzioni

• DA Suprunenko: Permutazione di un insieme . In: Michiel Hazewinkel (a cura di): Enciclopedia della matematica . Springer-Verlag e EMS Press, Berlino 2002, ISBN 978-1-55608-010-4 (inglese, online ). 
• alozano, Pedro Sanchez, Raymond Puzio, J. Pahikkala: Permutation . In: PlanetMath . (Inglese)
• Eric W. Weisstein : Permutazione . In: MathWorld (inglese).