Italiano
English
Français
Español
16.2. Permutazioni#
Una permutazione di \(n\) oggetti è, in sostanza, un elenco ordinato che contiene ognuno di essi una e una sola volta. In italiano, d'altronde, permutare è sinonimo di scambiare, o riordinare. In questo contesto, le configurazioni considerate dipendono strettamente dall'ordine degli elementi, e non è permesso il riutilizzo di uno stesso oggetto. In altri termini, si tratta di disporre \(n\) oggetti in altrettanti posti disponibili. Ciò equivale a fissare un criterio per ordinare gli oggetti, per poi elencarli dal «più piccolo» al «più grande».
Per calcolare il numero di permutazioni possibili dobbiamo distinguere tra due situazioni:
nella prima, gli oggetti sono tutti diversi,
nella seconda, esistono oggetti differenti che sono però indistinguibili tra loro.
A seconda dei due casi, si parla di permutazioni semplici o con ipetizione, che approfondiamo di seguito.
16.2.1. Permutazioni semplici#
Quando gli oggetti da permutare sono gli elementi di un insieme, per definizione sono tutti diversi, cioè distinguibili tra loro. In questo caso si parla di permutazione semplice (o più brevemente di permutazione) come descritto dalla seguente definizione.
Definizione 2 (Permutazione semplice)
Consideriamo un insieme \(A = \{ a_1,\dots a_n \}\) contenente \(n\) oggetti. Chiamiamo permutazione semplice (permutazione) di questi oggetti una qualsiasi sequenza ordinata
in cui compaiono tutti e soli gli \(n\) elementi di \(A\). Indichiamo con \(p_n\) il numero di tali permutazioni semplici.
In generale, descriverò una permutazione elencando i suoi elementi nell'ordine corrispondente, separati da virgole e racchiundendo l'elenco tra parentesi tonde. Vale la pena osservare che, partendo da una permutazione semplice, è sufficiente scambiare tra loro due elementi qualsiasi per ottenerne una nuova.
Esempio 9 (I Fantastici 4)
Consideriamo l'insieme \(Q = \{ f, i, t, c \}\) dei Fantastici 4: mister fantastic (\(f\)), la donna invisibile (\(i\)), la torcia umana (\(t\)) e la cosa (\(c\)): le possibili permutazioni semplici dei suoi oggetti sono elencate nella 12.
Permutazione |
Permutazione |
|---|---|
\((f, i, t, c)\) |
\((t, f, i, c)\) |
\((f, i, c, t)\) |
\((t, f, c, i)\) |
\((f, t, i, c)\) |
\((t, i, f, c)\) |
\((f, t, c, i)\) |
\((t, i, c, f)\) |
\((f, c, i, t)\) |
\((t, c, f, i)\) |
\((f, c, t, i)\) |
\((t, c, i, f)\) |
\((i, f, t, c)\) |
\((c, f, i, t)\) |
\((i, f, c, t)\) |
\((c, f, t, i)\) |
\((i, t, f, c)\) |
\((c, i, f, t)\) |
\((i, t, c, f)\) |
\((c, i, t, f)\) |
\((i, c, f, t)\) |
\((c, t, f, i)\) |
\((i, c, t, f)\) |
\((c, t, i, f)\) |
Il principio fondamentale del calcolo combinatorio ci aiuta a calcolare facilmente il numero \(p_n\) di differenti permutazioni di \(n\) oggetti:
l'oggetto da mettere nella prima posizione dell'elenco si può selezionare in \(n\) modi diversi, potendo scegliere tra tutti gli oggetti disponibili;
la seconda posizione può essere occupata da \(n-1\) oggetti distinti, in quanto non è possibile considerare quello utilizzato al punto precedente, così che esistono \(n \cdot (n-1)\) modi differenti per scegliere i primi due elementi della sequenza;
procedendo analogamente per ogni posizione successiva, il numero di opzioni diminuisce di un'unità a ogni passo, creando così un albero in cui il livello \(i\) è associato alla \(i\)-esima posizione; per riempire questa posizione, sono rimasti \(n-(i-1)\) elementi di \(A\) tra cui scegliere, dunque vi sono \(n\cdot(n-1) \cdot \ldots \cdot(n-(i-1))\) modi possibili per elencare i primi \(i\) elementi della sequenza;
arrivati all'ultima posizione, va obbliagatoriamente scelto l'unico elemento di \(A\) rimasto disponibile.
Si può quindi costruire un albero di profondità \(n\) che ha un numero di foglie pari a \(n(n-1)(n-2)\ldots 1=n!\), ognuna delle quali corrisponde a una delle possibili permutazioni semplici. Riassumendo, il numero di permutazioni di \(n\) oggetti è uguale a \(p_n = n!\). Guardando ad esempio la 12, si verifica facilmente che essa contiene tutte le possibili \(4! = 24\) permutazioni dei quattro oggetti dell'insieme \(Q\) introdotto nell’Esempio 9.
16.2.2. Permutazioni con ripetizione#
Consideriamo ora il caso in cui alcuni degli oggetti da permutare siano indistinguibili, ma restino distinguibili a gruppi. Più precisamente,
esistono \(r \in \mathbb N\) versioni possibili per gli oggetti, che possiamo indicare come \(a_1, \ldots, a_r\), e
per ogni \(j = 1, \dots, r\), la versione \(a_j\) è ripetuta \(n_j\) volte (il che implica \(\sum_{j=1}^r n_j = n\)).
Per ogni versione \(a_j\) esiste dunque un gruppo di oggetti indistinguibili la cui numerosità è \(n_j\). Questi oggetti formano un multiinsieme (una collezione non ordinata in cui ogni elemento può comparire una o più volte) che contiene \(n_1\) occorrenze della versione \(a_1\), \(n_2\) occorrenze di \(a_2\) e così via. Riassumendo, possiamo scrivere gli elementi di questo multiinsieme uno dopo l'altro ottenendo la sequenza
Cambiando l'ordine degli elementi, non sempre si ottiene una sequenza diversa: infatti, se si scambiasse la posizione di due oggetti indistinguibili la sequenza resterebbe invariata. In queste situazioni si considerano solo le permutazioni che producono sequenze effettivamente distinguibili, come descritto dalla definizione che segue.
Definizione 3 (Permutazione con ripetizione)
Consideriamo un multiinsieme \(A = \{ a_1,\dots a_n \}\) contenente \(n\) oggetti distinguibili a gruppi di numerosità \(n_1, \ldots, n_r\). Una permutazione di oggetti distinguibili a gruppi (più semplicemente, permutazione con ripetizione) di questi oggetti una qualsiasi loro sequenza ordinata che sia distinguibile dalle altre, e indichiamo con \(P_{n; n_1, \ldots, n_r}\) il numero di tali configurazioni.
Indicherò le permutazioni con ripetizione usando la medesima sintassi di quelle semplici, separando dunque i loro elementi con virgole e usando delle parentesi tonde come delimitatori.
Esempio 10 (Dupli-Kate e Multi-Paul)
Consideriamo i gemelli Kate e Paul Cha che appaiono in Invincible. Entrambi sono dotati del potere di autoreplicarsi a piacimento e noti come Dupli-Kate e Multi-Paul. In particolare, ogni versione di Dupli-Kate è contrassegnata da un numero intero progressivo che compare sul suo costume, così che possiamo indicare con \(k_1\), \(k_2\) e così via i suoi cloni presenti in un dato momento. Immaginiamo che lo stesso valga per Multi-Paul, le cui repliche indicheremo con \(p_1, p_2, \ldots\), e che di fronte a noi ci siano due versioni di Kate e tre di Paul, così che il quintetto risultante sia descritto dal multiinsieme \(A= \{ k_1, k_2, p_1, p_2, p_3 \}\).
Per calcolare in quanti modi si possano mettere in fila queste cinque versioni di Kate e Paul senza tenere conto del loro numero progressivo, bisogna ricavare il numero di permutazioni con ripetizione di \(n = 5\) oggetti divisi in due gruppi distinti: uno che comprende le \(n_1 = 2\) copie di Kate e un altro con \(n_2 = 3\) cloni Paul. In questo contesto, \((k_1, k_2, p_1, p_2, p_3)\) e \((k_2, k_1, p_1, p_2, p_3)\) indicano due diverse permutazioni semplici a cui corrisponde però la stessa permutazione con ripetizione: nelle prime due posizioni compare Kate, nelle ultime tre compare Paul. Al contrario, \((k_1, k_2, p_1, p_2, p_3)\) e \((k_1, p_1, k_2, p_2, p_3)\) indicano permutazioni con ripetizione differenti, perché nel primo caso la seconda posizione è occupata da Kate e la terza da Paul, mentre nel secondo accade il contrario.
Prima di calcolare il numero totale di permutazioni con ripetizione di \(n\) oggetti distinguibili a gruppi di numerosità \(n_1, n_2,\dots n_r\), analizziamo preliminarmente il caso particolare dell’Esempio 10. Concentriamoci su di una possibile permutazione con ripetizione, stabilendo le posizioni di Kate e quelle di Paul. Per esempio, ipotizziamo che la prima e 'ultima posizione siano dedicate a Kate e quelle rimanenti a Paul:
Kate Paul Paul Paul Kate
Ora, a questa permutazione con ripetizione corrispondono varie permutazioni semplici di cinque oggetti (le due copie di Kate e le tre di Paul). La 13 elenca tutti le permutazioni in cui Kate si trova agli estremi della fila, cioè nella permutazione con ripetizione che abbiamo fissato.
Permutazione |
|---|
\((k_1, p_1, p_2, p_3, k_2)\) |
\((k_1, p_3, p_1, p_2, k_2)\) |
\((k_1, p_2, p_3, p_1, k_2)\) |
\((k_1, p_3, p_2, p_1, k_2)\) |
\((k_1, p_2, p_1, p_3, k_2)\) |
\((k_1, p_1, p_3, p_2, k_2)\) |
\((k_2, p_1, p_2, p_3, k_1)\) |
\((k_2, p_3, p_1, p_2, k_1)\) |
\((k_2, p_2, p_3, p_1, k_1)\) |
\((k_2, p_3, p_2, p_1, k_1)\) |
\((k_2, p_2, p_1, p_3, k_1)\) |
\((k_2, p_1, p_3, p_2, k_1)\) |
Le righe della 13 sono state ottenute permutando le due copie di Kate nella prima e nell'ultima posizione e le tre copie di Paul nelle posizioni restanti. Se consideriamo Kate, abbiamo solo due possibilità: \(k_1\) e \(k_2\) rispettivamente in prima e ultima posizione, o viceversa, e queste due possibilità corrispondono alle \(2!\) permutazioni semplici delle due versioni di Kate. In altre parole, avremmo potuto considerare tutte le permutazioni semplici di queste due versioni e per ognuna di esse prendere il primo elemento e posizionarlo nella prima colonna della tabella, per poi inserire nell'ultima colonna il secondo elemento. In questo modo avremmo ottenuto due template per le righe della tabella, rispettivamente per quelle dalla prima alla sesta e per quelle dalla settima alla dodicesima. In entrambi i casi, le righe si completano con un ragionamento analogo che coinvolge le \(3!\) possibili permutazioni semplici delle versioni di Paul. Possiamo allora applicare il principio fondamentale del calcolo combinatorio: siccome abbiamo \(2!\) modi di riempire le posizioni in testa e in coda e \(3!\) modi per riempire le posizioni centrali, alla singola configurazione considerata corrispondono \(n_1! \cdot n_2! = 2! \cdot 3! = 12\) permutazioni semplici dei cinque oggetti a disposizione.
Questo ragionamento non dipende dalla particolare permutazione con ripetizione che abbiamo analizzato: a ognuna delle \(P_{5; 2,3}\) permutazioni con ripetizione corrispondono \(2! \cdot 3! = 12\) permutazioni semplici, e se le consideriamo tutte è facile vedere che, nel loro insieme, individuano la totalità delle permutazioni semplici. Pertanto deve valere l'uguaglianza \(P_{5; 2,3} \cdot 2! \cdot 3! = 5!\), il che ci permette di ricavare
Va notato che \(P_{5; 2,3} = \binom{5}{2}\), e in effetti il numero di permutazioni con ripetizione coincide con il numero di modi in cui si possono selezionare le due posizioni in cui inserire Kate tra le cinque a disposizione.
Nel caso generale, avremo \(n\) oggetti divisi in \(r\) gruppi di numerosità \(n_1, \ldots, n_r\), e ripetendo il ragionamento precedente si ottiene \(n! = P_{n; n_1,\dots, n_r} \cdot n_1! \cdot n_2! \cdot \ldots \cdot n_r!\), che implica
La quantità \(P_{n; n_1, \dots, n_r}\) è anche detta coefficiente multinomiale e indicata come
perché rappresenta una generalizzazione del coefficiente binomiale: in effetti, \(\binom{n}{k} = \binom{n}{k, n-k}\) indica in quanti modi è possibile suddividere \(n\) oggetti in due gruppi, rispettivamente contenenti \(k\) e \(n-k\) elementi; analogamente \(\binom{n}{n_1, \ldots, n_r}\) indica in quanti modi è possibile suddividere \(n\) oggetti in \(r\) gruppi nei quali il primo contiene \(n_1\) elementi, il secondo ne contiene \(n_2\) e così via.
16.2.3. Vero o falso?#
Analizzate ciascuna delle seguenti affermazioni, che riguardano le permutazioni, e dite se è vera o falsa, motivando il vostro ragionamento. Cliccate su di essa per visualizzare la risposta corretta.
Scambiare due elementi qualsiasi in una permutazione semplice produce sempre una nuova permutazione.
Vera. Nelle permutazioni semplici, si considerano elementi di un insieme, che sono quindi tutti distinti tra loro. Poiché l'ordine è significativo in una permutazione, qualsiasi scambio altera la sequenza e produce una configurazione diversa.
Il numero di permutazioni semplici di \(n\) oggetti è \(n!\).
Vera. Applicando il principio fondamentale del calcolo combinatorio: la prima posizione può essere occupata da \(n\) oggetti, la seconda da \(n-1\), e così via fino all'ultima posizione, che può essere riempita con il solo oggetto rimasto. Il numero totale di permutazioni è quindi \(n \cdot (n-1) \cdot \ldots \cdot 1 = n!\)
In una permutazione con ripetizione, è possibile usare un oggetto quante volte si vuole.
Falsa. Nelle permutazioni con ripetizione le molteplicità degli oggetti sono fissate dal multiinsieme di partenza: la versione \(a_j\) compare esattamente \(n_j\) volte, dove \(\sum_{j} n_j = n\) è il numero totale di posizioni. Non si può scegliere liberamente quante volte usare ciascun oggetto. Questa libertà caratterizza invece le disposizioni con ripetizione (nelle quali in ogni caso è possibile utilizzare un oggetto al più per un numero di volte uguale al numero di posti considerati).
Le permutazioni di \(\{1, 2, 3, 4\}\) e di \(\{a, b, c, d\}\) sono in numero uguale, perché i due insiemi hanno la stessa cardinalità.
Vera. Il numero di permutazioni semplici di \(n\) oggetti è \(p_n = n!\) e dipende solo dalla cardinalità \(n\), non dalla natura degli elementi. Come sottolineato a proposito del principio fondamentale, i risultati del calcolo combinatorio dipendono dalla numerosità degli oggetti considerati. Entrambi gli insiemi hanno \(n = 4\) elementi, quindi in entrambi i casi vi sono \(4! = 24\) permutazioni semplici.
Se tutti gli \(n\) oggetti di un multiinsieme appartengono allo stesso gruppo (sono cioè tutti indistinguibili tra loro), le permutazioni con ripetizione sono esattamente \(1\).
Vera. Se esiste un unico gruppo di numerosità \(n_1 = n\), applicando (16.2) si ottiene \(P_{n;\,n} = n!/n! = 1\). Intuitivamente, se tutti gli oggetti sono indistinguibili l'uno dall'altro, qualsiasi riorganizzazione produce la stessa sequenza visibile e si conta come un'unica permutazione con ripetizione.
Per calcolare il numero di anagrammi di una parola con alcune lettere ripetute si usa la formula delle permutazioni semplici \(p_n = n!\).
Falsa. La formula \(n!\) vale solo quando tutte le lettere sono distinte (come per SUPERMAN nell'Esercizio 54). Quando almeno una lettera si ripete, le permutazioni semplici sovrastimano il numero di anagrammi distinti, contando più volte le sequenze che differiscono solo per lo scambio di copie indistinguibili. In quel caso si usa la formula delle permutazioni con ripetizione: per ANTMAN (Esercizio 55), con A e N ripetute due volte ciascuna, si ottiene \(P_{6;\,2,2,1,1} = 6!/(2!\cdot 2!) = 180\), non \(6! = 720\).
16.2.4. Esercizi#
Esercizio 49 (••)
Gli X-Men nella formazione originale sono cinque: Ciclope, Marvel Girl, Bestia, Angelo e Uomo Ghiaccio. In quanti modi si possono disporre in fila in modo che Ciclope sia sempre in testa (come leader della squadra)?
Solution to Esercizio 49 (••)
Se Ciclope deve stare in prima posizione, i rimanenti quattro eroi possono occupare le restanti quattro posizioni in \(p_4 = 4! = 24\) modi.
Esercizio 50 (••)
I Thunderbolts originali sono stati formati da Citizen V, criminale sotto falso nome che aveva convinto altri cinque cattivi a cambiare identità e fingere di essere degli eroi. Al gruppo si era poi aggiunta Jolt, ignara di questo inganno. In quanti modi si possono disporre in fila tutti i membri del gruppo, in modo che i cinque ex cattivi originariamente convocati occupino le prime posizioni?
Solution to Esercizio 50 (••)
I cinque ex cattivi possono occupare le prime posizioni in \(p_5 = 5! = 120\) modi, e &mdsh; per ognuno di questi ordinamenti — i due membri rimasti possono occupare le ultime posizioni in \(p_2 = 2! = 2\) modi. Per il principio fondamentale, il numero di configurazioni possibili è \(120 \cdot 2 = 240\).
Esercizio 51 (••)
In quanti modi i Sinistri Sei (Doctor Octopus, Avvoltoio, Electro, Mysterio, Kraven il Cacciatore e Uomo Sabbia) possono occupare altrettante sedie, in modo che Doctor Octopus ed Electro non siano mai uno accanto all'altro?
Solution to Esercizio 51 (••)
A ogni abbinamento dei personaggi alle sedie corrisponde una particolare permutazione dei Sei Sinistri, ma non tutte le permutazioni sono da considerare. Per risolvere questo problema, conviene ragionare in modo complementare, sottraendo dalle \(p_6 = 6! = 720\) permutazioni tutte quelle in cui Doctor Octopus ed Electro sono vicini. Il conteggio di queste ultime si effettua considerando i due cattivi come un blocco unico, ottenendo cinque oggetti (quattro personaggi, più la coppia) da permutare in \(p_5 = 5! = 120\) modi; bisogna però tener conto del fatto che scambiando i due elementi della coppia si ottengono due diverse permutazioni tra quelle originali, quindi ci sono \(240\) modi di piazzare Doctor Octopus ed Electro uno accanto all'altro. Concludendo, ci sono \(720 - 240 = 480\) disposizioni accettabili.
Esercizio 52 (••)
La Legione degli Eroi Sostituiti comprende Polar Boy, Night Girl, Fire Lad, Stone Boy e Chlorophyll Kid. Le loro classifiche settimanali di potenza vengono stilate nel modo seguente: Night Girl e Polar Boy si trovano sempre nelle prime due posizioni (in un ordine qualsiasi), mentre Stone Boy è sempre l'ultimo. In quanti modi distinti può essere compilata una classifica?
Solution to Esercizio 52 (••)
Stone Boy deve apparire sempre all'ultimo posto, quindi il numero di classifiche si ottiene applicando il principio fondamentale del calcolo combinatorio, moltiplicando:
i \(p_2 = 2! = 2\) modi nei quali Night Girl e Polar Boy possono occupare le prime due posizioni, e
i \(p_2 = 2\) modi possiili di distribuire Fire Lad e Chlorophyll Kid nelle nelle rimanenti posizioni centrali.
Risulta perciò possibile stilare la classifica in quattro modi distinti.
Esercizio 53 (••)
Iron Man, Capitan America e la Donna Invisibile hanno un'identità che è nota a tutti; al contrario, Daredavil, Spider-Man e Ant-Man operano nell'anonimato. Se consideriamo indistinguibili tra loro i supereroi con identità pubblica, e analogamente quelli con identità segreta, in quanti modi distinti è possibile ordinarli?
Solution to Esercizio 53 (••)
In questo caso, bisogna considerare le permutazioni di sette oggetti, organizzati in due gruppi di tre e quattro eroi indistinguibili. Applicando la formula (16.2), si ottiene
Esercizio 54 (••)
In quanti modi si possono formare gli anagrammi della parola SUPERMAN, intendendo per anagramma una qualunque riorganizzazione delle lettere della parola di partenza, anche quando il risultato ottenuto non ha significato?
Solution to Esercizio 54 (••)
SUPERMAN è una parola che contiene otto lettere, tutte diverse tra loro. Il numero di anagrammi coincide quindi con il numero di permutazioni semplici di \(8\) oggetti, che è uguale a \(p_8 = 8! = 40\,320\).
Esercizio 55 (••)
In quanti modi si possono formare gli anagrammi della parola ANTMAN, nella stessa accezione dell'esercizio precedente?
Solution to Esercizio 55 (••)
La parola ANTMAN contiene sei lettere, due delle quali occorrono in due diverse posizioni. Il numero di anagrammi distinti è quindi una permutazione con ripetizione: più precisamente, T e M appartengono ognuna a un gruppo con molteplicità \(1\), mentre A ed N fanno riferimento a due gruppi con molteplicità \(2\). Pertanto il numero di anagrammi distinti è
Esercizio 56 (•••)
Nella sua formazione originale, la Justice Society of America schiera una formazione di otto eroi: tre con poteri magici o alieni (Lanterna Verde, Spettro e Dottor Fate), tre che utilizzano tecnologie segrete (Atomo, Hourman e Flash) e due che fanno uso di tecnologie note e facilmente riconoscibili (Sandman e Hawkman). In quanti modi possono intervenire uno dopo l’altro in battaglia, mantenendo sempre consecutivi gli eroi della stessa categoria?
Solution to Esercizio 56 (•••)
Immaginiamo di fare intervenire prima tutti gli eroi con poteri magici, poi quelli che usano tecnologie segrete e infine quelli rimanenti. Siccome i primi due gruppi possono essere permutati in \(p_3 = 3!\) modi e il terzo si può ordinare in \(p_2 = 2!\) configurazioni, Per il principio fondamentale del calcolo combinatorio, esistono quindi \(6 \cdot 6 \cdot 2 = 72\) modi di interventire. Se modificassimo l'ordine dei gruppi, il risultato sarebbe lo stesso. Quindi il risultato si ottiene moltiplicando \(72\) per il numero di permutazioni dei gruppi, che è \(p_3 = 3!\). Concludendo, vi saranno \(432\) diversi modi di fare intervenire i membri della Justice Society, uno dopo l'altro.
16.2.5. Concetti fondamentali#
Pensate ai concetti fondamentali illustrati in questo paragrafo ed elencateli. Nella lista qui sotto sono già presenti gli stessi concetti, ma nascosti. Cliccate sul pulsante per mostrarli sotto forma di parole chiave, quindi confrontateli con la vostra lista. Provate infine a descrivere ciascun concetto con parole vostre.