Le permutazioni

Cari lettori del Tamburo, oggi parliamo di permutazioni.

Non vi spaventate, l'argomento di cui parleremo è più semplice di quanto si possa pensare di primo acchito.
Incominciamo chiarendo subito cos'è una permutazione.
Una permutazione p di un insieme X di numeri interi positivi {1,2,3,....,n} è una funzione biunivoca che possiamo indicare, in simboli, nel seguente modo:




Ma cosa diavolo significa funzione biunivoca?
Nulla di complicato!
Innanzitutto, una funzione è una certa legge che ad ogni elemento di un insieme, un imput, associa uno e un solo elemento di un altro insieme, un output in sostanza.

Guardate ad esempio questa immagine:

Abbiamo un insieme X di partenza che viene chiamato dominio della funzione, mentre l'insieme Y di arrivo viene detto codominio (non condominio, mi raccomando!).
La funzione rappresentata in figura associa, come potete osservare, tutti gli elementi dell'insieme X (in questo caso 1, 2 e 3) a rispettivi elementi dell'insieme Y (a, c, d).
Trattasi in particolare di una funzione iniettiva (detta anche funzione ingettiva oppure iniezione), dato che ogni elemento dell'insieme Y di arrivo riceve, al massimo, una freccia da un singolo elemento di X.
Esistono infatti funzioni in cui alcuni elementi del codominio ricevono frecce da più elementi del dominio, come avviene, ad esempio, nella funzione rappresentata dalla seguente immagine:

Questa sicuramente non è una funzione iniettiva, bensì viene detta suriettiva (o surgettiva), visto che ogni elemento dell'insieme di arrivo riceve almeno una freccia dall'insieme di partenza.
In altre parole, l'insieme Y viene totalmente "sommerso" da frecce provenienti da X.
Esiste poi un caso particolare in cui una funzione risulta contemporaneamente iniettiva e suriettiva; in tal caso la funzione viene detta biunivoca (o biettiva o bigettiva).
In pratica, una funzione è detta biunivoca quando ad ogni elemento del codominio è associato uno e un solo elemento del dominio, come accade nell'immagine che segue:

Ecco un esempio più particolare di funzione biunivoca:

Ogni singolo bersaglio è associato a un singolo arciere.
Adesso una bella immagine che ben riassume le tipologie di funzioni spiegate:

Se avete ben compreso cos'è una funzione e i vari tipi esistenti, allora non dovrebbe essere difficile capire perché le 2 immagini che seguono non rappresentano funzioni:

Ora possiamo finalmente proseguire con le nostre permutazioni.
Una permutazione è, ripetiamo, una funzione biunivoca che ad un imput fornito da un numero intero fa corrispondere un output costituito sempre da un numero intero.
Ecco un esempio di permutazione:

Per comprendere meglio il concetto, potreste immaginarvi una serie di bustine numerate per esempio da 1 a 7.
Dentro ciascuna bustina dovreste immaginare di trovare un foglietto con sopra scritto un certo numero, sempre compreso tra 1 e 7.
Quella che svelerete una volta aperte in ordine le buste sarà una permutazione tra le tantissime possibili.
Ma quante sono esattamente le permutazioni possibili con un insieme di numeri interi che vanno da 1 a 7?
Prima di rispondere a tale interrogativo, consideriamo un esempio più semplice.
Immaginiamo un insieme di numeri interi formato dai numeri che vanno da 1 a 4.
Le possibili permutazioni sarebbero le seguenti [l'insieme di partenza è sempre quello formato da (1, 2, 3, 4)]:

(1, 2, 3, 4)
(1, 2, 4, 3)
(1, 3, 2, 4)
(1, 3, 4, 2)
(1, 4, 2, 3)
(1, 4, 3, 2)
(2, 1, 3, 4)
(2, 1, 4, 3)
(2, 3, 1, 4)
(2, 3, 4, 1)
(2, 4, 1, 3)
(2, 4, 3, 1)
(3, 1, 2, 4)
(3, 1, 4, 2)
(3, 2, 1, 4)
(3, 2, 4, 1)
(3, 4, 1, 2)
(3, 4, 2, 1)
(4, 1, 2, 3)
(4, 1, 3, 2)
(4, 2, 1, 3)
(4, 2, 3, 1)
(4, 3, 1, 2)
(4, 3, 2, 1) 

Sono 24.
Abbiamo determinato manualmente tutte le possibili permutazioni per un insieme di 4 numeri.
Le cose però si farebbero molto più lunghe e intrecciate già se considerassimo i primi 5 numeri interi.
Esiste un modo per determinare istantaneamente il numero di permutazioni possibili su n oggetti?
Certo!
Infatti, quotando Wikipedia:

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

Questo implica che il numero delle permutazioni di n oggetti è pari al fattoriale di n:

Quindi per un insieme di n = 4 oggetti, abbiamo che il numero di permutazioni possibili è




Appunto quello che avevamo trovato manualmente.
Con 5 oggetti il numero di permutazioni salirebbe a ben




Possiamo ora facilmente rispondere all'interrogativo lasciato in sospeso in precedenza, ovvero quante sono le permutazioni che si possono fare considerando 7 oggetti distinti.
Prima però specifichiamo che si parla di "oggetti" perché, in effetti, le permutazioni ci possono essere anche non relativamente ai numeri: si possono infatti avere le permutazioni delle lettere dell'alfabeto, delle note musicali, ecc.
La risposta alla questione precedente è:




Senza la nozione di fattoriale probabilmente mi ci sarebbero volute ore per illustrarvi la risposta al quesito, rimanendo pressoché in questo stato:

Ergo, sia ringraziato il fattoriale! ;)
Una proprietà importante delle permutazioni è il segno.
Ci sono 2 simpatici modi di stabilire il segno di una permutazione, uno più veloce, uno più lento.
Questi metodi possono esseri anche visti alla stregua di giochini istruttivi per passare del tempo.
Andiamo a scoprire innanzitutto quello più rapido, ma ancor prima 2 definizioni fondamentali.
Si definisce permutazione identica la permutazione che si ottiene associando ad ogni numero intero positivo il medesimo numero.
La permutazione identica può essere rappresentata mediante la matrice

Insomma, 1 è associato a 1, 2 è associato a 2, 3 è associato a 3 e così via, fino a n.
Per semplicità, d'ora in poi, indicheremo la permutazione identica solamente come (1, 2, 3,..., n).
Si definisce inoltre trasposizione (o scambio) il procedimento che consiste nello scambiare di posto 2 elementi lasciando fissi tutti gli altri.
Per trovare il segno di una permutazione, basta solamente determinare quanti scambi sono necessari per trasformare la nostra permutazione nella permutazione identica.
Il segno è infatti dato dalla formula:




in cui m indica appunto il numero di trasposizioni necessarie per ottenere la permutazione identica.
Dalla teoria passiamo alla pratica provando a calcolare il segno della permutazione




Divertiamoci un po' con i numeri!
Portiamo l'1 al primo posto scambiandolo con il 4, che si ritrova nella posizione in cui dovrebbe stare, la quarta:




Poi scambiamo il 2 con il 5.




Infine scambiamo il 5 (che adesso si trova nella terza posizione) con il 3.
In questo modo abbiamo ottenuto la permutazione identica (1, 2, 3, 4, 5).
Ora non resta che contare quante trasposizioni abbiamo effettuato.
Sono 3.
Questo significa che il segno della permutazione di partenza è:




Semplice e divertente, vero?
Saremmo però potuti arrivare allo stesso risultato attraverso un altro metodo, un tantino più lungo e articolato, un metodo che si basa sulle cosiddette coppie in inversione.
Per capire cosa siano le coppie in inversione, fate riaffiorare alla mente l'immagine delle buste numerate con dentro numeri.

Si consideri una coppia di queste bustine, una coppia non scelta a caso, visto che la prima busta dovrà presentare all'esterno un numero inferiore rispetto alla seconda busta (ad esempio, le buste 1 e 3, le buste 2 e 5, le buste 6 e 7, ecc.).
Se il valore (cioè il numero riportato nel fogliettino all'interno) della prima busta è superiore a quello della seconda, allora questa coppia di buste si dice appunto in inversione rispetto alla permutazione p.
Riprendiamo la permutazione precedente, ovvero p = (4, 5, 2, 1, 3) e proviamo a determinare le sue coppie in inversione.
Partiamo dalla coppia di bustine (1, 2) che risponde ai requisiti, poiché il numero 1 all'esterno della prima busta è inferiore al numero 2 nella parte esterna della seconda.
Se aprissimo la busta 1, in base alla permutazione p che abbiamo scelto, troveremmo un foglietto con scritto il numero 4.
Se aprissimo la busta 2 troveremmo invece un foglio con appuntato il numero 5.
4 è minore di 5, quindi la coppia (1, 2) non è in inversione.
Ora si va avanti nel medesimo modo.
Si considera la coppia (1, 3), i cui corrispondenti valori sono 4 e 2.
4 è maggiore di 2, quindi questa è una coppia in inversione.
Anche (1, 4) è una coppia in inversione, dato che i corrispondenti valori sono 4 e 1 (e 4 risulta ovviamente più grande di 1), così come (1, 5) è una coppia in inversione.
Dopodiché si passa direttamente alla valutazione della coppia (2, 3), la quale è una coppia in inversione come (2, 4) e (2, 5), in quanto la bustina con all'esterno il numero 2 contiene all'interno il valore 5, il più grande possibile nella suddetta permutazione.
E poi tocca a (3, 4), anch'essa coppia in inversione, (3, 5), la quale non è una coppia in inversione e, infine, (4, 5), che non è una coppia in inversione.
Riassumendo, sono coppie in inversione le seguenti:

(1, 3)
(1, 4)
(1, 5)
(2, 3)
(2, 4)
(2, 5)
(3, 4)

In totale, la permutazione p = (4, 5, 2, 1, 3) presenta 7 coppie in inversione.
Ebbene, il segno di una permutazione si può valutare anche nel seguente modo:




dove μ(p) indica proprio il numero di coppie in inversione.
Nel nostro caso abbiamo che:




Risultato identico a quello ottenuto col metodo maggiormente rapido.
Giusto per completezza, aggiungo che esistono le permutazioni con ripetizioni, quando nell'insieme di partenza sono presenti elementi che si ripetono.
I dettagli li trovate su Wikipedia.
Concludo lasciandovi una permutazione della quale, magari, vi divertirete a determinare il segno con i 2 metodi illustrati in questo post: p = (6, 8, 1, 7, 5, 3, 4, 2).

Alla prossima!

Questo post partecipa al Carnevale della Matematica n.69, che verrà ospitato dalla tamburista (e tanto altro ancora!) Annarita Ruberto sul suo blog Matem@ticamente.