Le permutazioni

In matematica, una permutazione è un ordinamento degli elementi di un insieme in una sequenza o disposizione specifica.

Ad esempio, questa è una sequenza di palline colorate: rossa, blu, verde. E' una permutazione.

Cambiando l'ordine delle palline nella sequenza otteniamo un'altra permutazione. Ad esempio: blu, verde, rossa.

Se l'insieme è composto da n elementi, una permutazione di questi elementi è una disposizione di tutti gli n elementi in un certo ordine.

Un esempio di permutazione

Ad esempio, consideriamo un insieme composto da tre elementi:

$$ X = \{1, 2, 3\} $$

Le permutazioni di questo insieme sono tutti i possibili modi in cui possiamo ordinare questi tre numeri.

Ci sono 6 permutazioni possibili per tre oggetti distinti.

$$ 3! = 3 \times 2 \times 1 = 6 $$

Ecco tutte le permutazioni dell'insieme $ 1, 2, 3 $:

\(123\)

\(132\)

\(213\)

\(231\)

\(312\)

\(321\)

Ogni permutazione è un'arrangiamento unico degli stessi numeri in un ordine differente.

In generale, se hai un insieme di \(n\) oggetti, ci saranno $ n! $ (n fattoriale) permutazioni, che significa

$$ n! = n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1 $$

Le permutazioni sono molto importanti in diversi campi della matematica e della scienza, comprese le probabilità, la statistica, la teoria dei giochi e la crittografia..

Per rappresentare una permutazione puoi usare questa notazione.

$$ \begin{pmatrix} a_1 & a_2 & a_3 & \dots \\ b_1 & b_2 & b_3 & \dots   \end{pmatrix}  $$

Dove la prima riga (a₁, a₂, ... ) è la configurazione di partenza mentre la seconda riga (b₁, b₂, ... ) è quella finale.

Ogni elemento della prima riga viene sostituito con il corrispondente elemento nella seconda riga che si trova nella stessa colonna.

Ad esempio la transizione da (123) a (213) puoi scriverla:

$$ \begin{pmatrix} 1 & 2 & 3  \\ 2 & 1 & 3  \end{pmatrix}  $$

In questo caso l'elemento 1 viene sostituito con 2 e viceversa, mentre l'elemento 3 resta invariato.

Puoi rappresentare una permutazione anche in un modo più compatto, evitando di indicare gli elementi invariati.

$$ (1,2) $$

o ancora più compatta

$$ (12) $$

In questo modo stai dicendo che l'elemento 1 viene sostituito con 2 e viceversa. L'elemento 3 che resta invariato viene omesso.

Esempio 2

Facciamo un altro esempio di permutazione su un insieme composto da quattro elementi

$$ X = \{1, 2, 3, 4, 5\} $$

Per rappresentare la permutazione da (12345) a (31254) possiamo scrivere:

$$ \begin{pmatrix} 1 & 2 & 3 & 4 & 5  \\ 3 & 1 & 2 & 5 & 4   \end{pmatrix}  $$

In modo più compatto possiamo scrivere la stessa permutazione come prodotto di cicli disgiunti

$$ (132) (45) $$

Dove (132) è un ciclo che vuol dire: 1 sostituisce 3, 3 sostituisce 2, 2 sostituisce 1. Mentre (45) è una semplice trasposizione, ovvero uno scambio di posto, tra 4 e 5.

A sua volta il ciclo (321) possiamo anche vederlo come prodotto di trasposizioni (321)=(32)(31).

$$ (32) (31) (45) $$

In questo caso 3 sostituisce 2, poi 3 sostituisce 2, infine 4 sostituisce 5.

Il risultato finale è sempre lo stesso: (31254).

Verifica. Partiamo dalla permutazione iniziale: $$ (12345) $$ Applichiamo la trasposizione (32) sostituendo 3 con 2 $$ (13245) $$ Ora applichiamo la trasposizione (31) e scambiamo di posto 3 e 1.  $$ (31245) $$ Infine, applichiamo l'ultima trasposizione (45) sostituendo 4 con 5 $$ (31254) $$ Il risultato finale è sempre lo stesso.

Tipi di permutazioni

Ci sono due tipi principali di permutazioni:

• Permutazioni senza ripetizioni
  Sono l'ordinamento di tutti gli elementi di un insieme senza ripetizioni e senza lasciare fuori alcun elemento.

  Per esempio, per l'insieme {1, 2, 3}, le permutazioni possibili sono 123, 132, 213, 231, 312, e 321. Il numero di permutazioni senza ripetizioni di un insieme di nn elementi è n! (fattoriale di n), che è il prodotto di tutti i numeri interi positivi da 1 a n.

• Permutazioni con ripetizioni
  Si verificano quando l'insieme ha elementi ripetuti. In questo caso, il calcolo del numero di permutazioni possibili deve tenere conto delle ripetizioni.

  Per esempio, per l'insieme {1, 1, 2}, ci sono meno permutazioni possibili perché i due '1' non possono essere distinti tra loro. In questo caso le permutazioni possibili sono solo tre: 112, 121, 211. La formula per calcolare il numero di permutazioni con ripetizioni divide n! per il prodotto dei fattoriali h!k! delle frequenze di ogni elemento ripetuto. $$ \frac{n!}{h!k!} $$ Ad esempio, in questo caso l'insieme è composto da n=3 elementi ma un elemento è ripetuto due volte h=2. Quindi, le permutazioni sono $$ \frac{n!}{h!k!} = \frac{3!}{2!} = \frac{3 \cdot 2 \cdot 1}{2 \cdot 1} = \frac{6}{2} = 3 $$

La composizione delle permutazioni

La composizione delle permutazioni implica l'applicazione sequenziale di due o più permutazioni.

Quando si compone una permutazione con un'altra, si sta essenzialmente applicando la prima permutazione e poi applicando la seconda alla sequenza risultante. Il concetto è simile a svolgere due o più mosse in successione.

La composizione delle permutazioni segue l'ordine da destra a sinistra. Questo significa che la permutazione a destra viene applicata per prima. Ecco perché la composizione di permutazioni può essere non commutativa, perché \( p \circ q \) può essere diversa da \( q \circ p \), come si può vedere nel caso delle permutazioni in \( S_3 \) che ho descritto prima. 

Esempio

Per esempio, consideriamo due permutazioni \( p \) e \( q \) dell'insieme \( \{1, 2, 3\} \). La configurazione iniziale degli elementi è \( 123 \).

Supponiamo che \( p \) scambi 1 con 2 e lasci 3 invariato, mentre \( q \) scambi 1 con 3 e lasci 2 invariato. Le permutazioni possono essere scritte come segue:

 \( p = (1 2) \)

 \( q = (1 3) \)

La permutazione p=(1,2) sostituisce l'elemento 1 con 2 e viceversa. La permutazione q=(1,3), invece, sostituisce l'elemento 1 con 3 e viceversa.

La composizione \( p \circ q \) si ottiene applicando prima \( q \) e poi \( p \) all'insieme.

Applicando \( q = (1 3) \) alla configurazione iniziale \( 123 \) otteniamo:

\( q(1) = 3 \)

\( q(2) = 2 \)

\( q(3) = 1 \)

La permutazioni q=(1,3) sostituisce 1 con 3 e viceversa, lasciando invariata la posizione dell'elemento 2. Quindi, partendo da 123 si ottiene come risultato 321.

Ora applichiamo \( p  (1 2) \) al risultato di \( q \) ovvero a \( 321 \):

\( p[q(1)] = p(3) = 3 \)

\( p[q(2)] = p(2) = 1 \)

\( p[q(3)] = p(1) = 2 \)

La permutazioni p=(1,2) sostituisce 1 con 2 e viceversa, lasciando invariata la posizione dell'elemento 3. Quindi, partendo da 321 si ottiene come risultato 312.

In conclusione, la composizione \( p \circ q \) ci dà la permutazione finale \( (1 3 2) \), che scambia 1 con 3 e poi 3 con 2.