9 Ordinare e contare Per alcuni valori di n, calcoliamo n!: 1! = 1 2! = 2 1 = 2 3! = 3 2 1 = 6 4! = 4 3 2 1 = 24 5! = 5 4 3 2 1 = 120 6! = 6 5 4 3 2 1 = 720 7! = 7 6 5 4 3 2 1 = 5040 8! = 8 7 6 5 4 3 2 1 = 40 320 9! = 9 8 7 6 5 4 3 2 1 = 362 880 Come si vede, il valore del fattoriale cresce molto rapidamente all aumentare di n. Poniamo inoltre per definizione 0! = 1. ovvio che nel caso di n elementi, poiché n rappresenta un qualunque numero naturale, l albero non può essere disegnato compiutamente ma può soltanto essere accennato. In un grafo, le linee che collegano i nodi sono generalmente detti archi. esempi O Calcola 10! Il fattoriale di n si può ottenere moltiplicando il fattoriale del numero precedente per n. Poiché 9! = 362 880, allora 10! = 3 628 800. O Una famiglia è costituita dai 2 genitori e da 4 figli. Mentre i genitori mantengono sempre il loro posto, i figli decidono di cambiare il loro posto a tavola a ogni pasto principale (pranzo e cena). Quanti giorni impiegheranno per esaurire tutte le posizioni possibili? Dei 6 posti totali cambiano solo i 4 dei figli e quindi le possibili configurazioni sono in numero di 4! = 24. Cambiando posto sia a pranzo sia a cena ci vorranno dunque 12 giorni per ricoprire tutte le possibili posizioni. O Quanti anagrammi della parola «amico (anche senza senso) si possono realizzare mantenendo affiancate le lettere i e c? Le lettere i e c sono affiancate sia nella configurazione ic (come è in amico) sia in quella ci (come, per esempio, in cioma). Analizziamo la coppia ic e consideriamola come un unica lettera (vedi grafo ad albero); in tal caso la parola a m ic o ha esattamente 4! = 24 anagrammi. a m ic m o a ic o m o m ic ic o ic ic a o o a a ic m o o m a o o a m ic PROVA TU P aa. Calcola il numero di anagrammi, anche privi di significato, della parola «parola . b. Nel primo giorno di scuola 24 studenti entrano nella loro nuova classe con tutti banchi a un posto. Calcola in quanti modi differenti si possono sedere se i posti non sono stati già assegnati. FISSA I CONCETTI Q a m m ic a ic a m Q o ic o m ic m o ic o a ic a o m o a m a ic m ic a m a Un grafo analogo lo possiamo ottenere con la configurazione ci per la parola cioma. Complessivamente avremo quindi 4! + 4! = 24 + 24 = 48 anagrammi. Q Q Ogni permutazione è un diverso ordinamento degli elementi di un insieme. Il numero delle permutazioni di n elementi è: Pn = n! = = n (n + 1) (n + 2) (n + 3) 2 1 n! è un prodotto di n fattori decrescenti a partire da n. 0! = 1 419