Permutazioni
Le permutazioni contano il numero di modi in cui è possibile ordinare (permutare) un certo numero di oggetti.
Se gli oggetti sono tutti
distinti si ha una
permutazione semplice. Se ci sono degli oggetti uguali (e dunque interscambiabili senza che cambi qualcosa) si ha una
permutazione con ripetizioni.
Permutazioni semplici
Usiamo le permutazioni semplici quando dobbiamo calcolare il numero di modi in cui è possibile ordinare \(n\) oggetti
distinti, formando cioè una
sequenza ordinata in cui ognuno degli \(n\) oggetti compare una e una sola volta.
Il numero di queste permutazioni è dato da
$$P_n = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1 = n!$$
Dove \(n!\) è il fattoriale di \(n\) ("\(n\) fattoriale"), definito appunto come il numero \(n\) moltiplicato per tutti i numeri che lo precedono fino ad 1.
Per capire intuitivamente la formula pensiamo all'atto di disporre \(n\) oggetti in ordine. Il primo oggetto della sequenza possiamo sceglierlo tra tutti gli \(n\) disponibili. A questo punto il secondo oggetto da mettere nell'ordine possiamo sceglierlo tra \(n-1\) oggetti perché uno lo abbiamo già utilizzato. Proseguendo nel ragionamento il terzo elemento si può scegliere tra \(n-2\) possibilità e così via fino al penultimo elemento che si può scegliere tra i \(2\) rimasti, e l'ultimo la cui scelta è obbligata.
Per il
principio di moltiplicazione i numeri di scelte possibili ad ogni passo vengono moltiplicati.
In quanti modi è possibile anagrammare (anche senza senso) la parola SOLE?
Anagrammare una parola equivale a permutare l'ordine delle sue lettere. Poiché tutte le lettere della parola SOLE sono distinte (nessuna si ripete) usiamo le permutazioni semplici con \(n=4\)
$$P_4=4!=4 \cdot 3 \cdot 2 \cdot 1 = 24$$
In quanti modi è invece possibile anagrammare la parola ALA?
In questo caso abbiamo una lettera che si ripete (la A) quindi la formula delle permutazioni semplici non va bene (dovremmo usare le permutazioni con ripetizione che vediamo più avanti) infatti essa conterebbe come anagrammi diversi ad esempio le parole \(\color{blue}{A}L\color{green}{A}\) e \(\color{green}{A}L\color{blue}{A}\) ottenute scambiando le due A quando invece esse sono in realtà la stessa parola.
Permutazioni con ripetizioni
Quando gli \(n\) oggetti da ordinare invece di essere tutti distinti si possono
ripetere usiamo le permutazioni con ripetizioni.
Se ci sono ad esempio due oggetti uguali, essi si possono scambiare nella sequenza senza che vi sia alcuna differenza, essendo i due oggetti indistinguibili. Quindi alla fine il numero di permutazioni possibili sarà minore di quello che si ottiene applicando la formula delle permutazioni semplici perché alcune delle sequenze risultano uguali tra loro.
Supponiamo che ci sia un elemento che si ripete \(k_1\) volte, uno che si ripete \(k_2\) volte e così via fino ad un elemento che si ripete \(k_m\) volte. Allora il numero di permutazioni con ripetizioni possibili è
$$P_n^{k_1,k_2,\ldots,k_m} = \frac{n!}{k_1!\cdot k_2! \cdot \ldots \cdot k_m!} $$
ovvero è uguale al numero di permutazioni semplici \(n!\) diviso per il numero \(k_1!\) di modi in cui si possono permutare tra loro i \(k_1\) oggetti uguali, diviso il numero \(k_2!\) in cui si possono permutare tra loro i \(k_2\) oggetti uguali e così via.
In quanti modi è possibile anagrammare la parola ALA?
Il problema è equivalente a chiedersi in quanti modi è possibile ordinare le tre lettere A,L,A considerando però che due di esse sono uguali tra loro quindi scambiandole non si ottiene una nuova sequenza diversa dalla precedente.
Applicando la formula con \(n=3\) e con \(k_1 =2\) (c'è un solo elemento che si ripete, la A, e si ripete due volte) si ottiene
$$P_3^{2} = \frac{3!}{2!} = \frac{3 \cdot 2\cdot 1}{2 \cdot 1} = 3$$
È molto facile in questo caso elencare esplicitamente i tre possibili anagrammi: ALA, LAA, AAL.
\(\require{cancel}\)
In quanti modi è possibile anagrammare la parola COCCO?
Dobbiamo permutare le 5 lettere della parola notando però che ci sono due lettere uguali tra loro (le O) e tre uguali tra loro (le C).
Si ha quindi che il numero possibile di permutazioni con ripetizioni è
$$P_5^{3,2} = \frac{5!}{3! \cdot 2!} = \frac{5 \cdot 4 \cdot \cancel{3!}}{\cancel{3!} \cdot 2!} = 10$$