Permutazioni

Le permutazioni di $n$ oggetti distinti sono tutti i possibili modi di ordinare tali oggetti. In una permutazione, si utilizzano tutti gli elementi dell’insieme e l’ordine in cui vengono disposti è l’unico fattore che distingue una configurazione dall’altra.

Permutazioni Semplici

Il numero di permutazioni di $n$ oggetti distinti è dato dal fattoriale di $n$: $P_n = n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$

Esempio: Se abbiamo 3 oggetti $\{A, B, C\}$, le permutazioni possibili sono $3! = 6$: $\{ABC, ACB, BAC, BCA, CAB, CBA\}$.

Permutazioni con Ripetizione

Se tra gli $n$ oggetti ve ne sono alcuni identici tra loro (es. $k_1$ oggetti di tipo 1, $k_2$ di tipo 2, ecc.), il numero di permutazioni distinte diminuisce poiché scambiare oggetti identici non produce una nuova configurazione: $P_n^{k_1, k_2, \dots, k_r} = \frac{n!}{k_1! \cdot k_2! \dots k_r!}$

Significato Ingegneristico

• Logistica e Trasporti: Il numero di permutazioni è alla base del problema del commesso viaggiatore (TSP), dove si cerca l’ordine ottimale (permutazione) delle città da visitare per minimizzare il percorso.
• Crittografia: La robustezza di una password o di una chiave crittografica dipende spesso dal numero di permutazioni possibili dei caratteri che la compongono (attacchi brute-force).
• Informatica: Gli algoritmi di ordinamento (sorting) hanno lo scopo di trovare la permutazione specifica degli elementi di un array che soddisfa una relazione d’ordine (es. crescente).
• Schedulazione dei Processi: In ingegneria gestionale, determinare l’ordine di esecuzione di $n$ task su una macchina (job shop scheduling) richiede l’analisi delle permutazioni per minimizzare il tempo totale di completamento (makespan).

Vedi anche: Calcolo Combinatorio, Fattoriale, Disposizioni.