DATI E PREVISIONI Esercizi da pag. 434 1 Le permutazioni Ogni volta che vogliamo ordinare ed elencare gli elementi appartenenti a un insieme finito o sceglierne alcuni, si pone il problema di calcolare quanti siano gli ordinamenti o le scelte possibili. Quanti codici PIN (un codice utilizzato per attivare un dispositivo) da 4 cifre si possono formare? Quante targhe automobilistiche si possono comporre secondo la codifica corrente? In quanti modi diversi puoi decidere di vestirti alternando le tue magliette, i pantaloni e le scarpe che hai in casa? Quante parole di 5 lettere si possono formare con le 21 lettere dell alfabeto? Problemi di questo genere sono piuttosto frequenti, sia nella vita quotidiana sia all interno della matematica. I grafi ad albero per rappresentare ordinamenti Il primo problema, che esamineremo in questo paragrafo, riguarda in quanti modi si possono ordinare n elementi di un insieme, essendo n un qualunque numero naturale. Consideriamo dapprima, come esempio, un insieme di 3 elementi, che indichiamo con le prime tre lettere dell alfabeto: A = {a, b, c} Per ordinare questi tre elementi, dobbiamo innanzitutto scegliere l elemento da collocare per primo; poiché gli elementi sono 3, vi sono 3 scelte possibili: I elemento a b c Occorre ora scegliere l elemento da collocare per secondo: Q se il primo elemento scelto è stato a, il secondo può essere b oppure c; Q se il primo elemento scelto è stato b, il secondo può essere a oppure c; Q se il primo elemento scelto è stato c, il secondo può essere a oppure b. Rappresentiamo queste possibilità utilizzando un grafo ad albero: a I elemento II elemento b b c a c c a b Avendo soltanto tre elementi da ordinare, una volta che ne siano stati collocati due, il terzo è anche l ultimo e la scelta è obbligata. L albero completo è il seguente: a I elemento b c b c a c a b III elemento c b c a b a II elemento Ognuno dei percorsi che va dalla radice (il punto da cui partono i primi rami) dell albero a un nodo terminale (i punti d arrivo) dà un possibile ordinamento. 416