9 Ordinare e contare esempio O Descrivi l albero che rappresenta tutte le disposizioni di 5 elementi in 3 posti. Quanti sono i suoi nodi terminali? Dalla radice dell albero partono 5 rami, corrispondenti alle 5 possibili scelte di elementi da mettere al primo posto. Da ognuno di questi nodi, in cui sono rappresentati tutti gli elementi scelti per primi, partono 4 rami, perché sono 4 gli elementi che si possono scegliere per secondi. Segnati tutti gli elementi che si possono scegliere come secondi, da ognuno di essi partono 3 rami che indicano gli elementi scelti per il terzo posto. Complessivamente, i nodi terminali sono 5 4 3 = 60. Generalizzando i ragionamenti fatti in precedenza, arriviamo alla conclusione che il numero delle disposizioni di n elementi in k posti è dato dal prodotto di k fattori, cioè tanti quanti sono i posti. Il primo fattore è n, il secondo n 1, il terzo n 2, e così via, fino ad arrivare al k-esimo fattore, che è n (k 1). Abbiamo, quindi, che il numero delle disposizioni di n elementi in k posti, che indichiamo con Dn,k, è: Dn,k = n (n 1) (n 2) (n (k 1)) ATTENZIONE! A immediato i verificare che se k = n allora Dn,k = n! cioè le permutazioni di n elementi. esempi O Vogliamo disporre gli elementi a, b, c, d, e in 2 posti. Quante disposizioni sono possibili? Quali sono? In questo caso, il numero delle disposizioni è dato dal prodotto di due fattori: 5 4 = 20. Le disposizioni sono: ab ac ad ae ba bc bd be ca cb cd ce da db dc de ea eb ec ed O Ricordi che il numero di telefono di un amico è formato da 7 cifre tutte diverse e la prima cifra è 4. Quanti sono i possibili numeri di telefono di tale amico? Poiché ricordi la prima cifra e le cifre sono tutte tra loro diverse, occorre calcolare il numero delle disposizioni di 9 elementi (le nove cifre rimanenti diverse da 4) in 6 posti (dalla seconda cifra in poi). I possibili numeri di telefono sono perciò ben: 9 8 7 6 5  4 = 60 480 6 fattori PROVA TU P Ot amici, all atto dell acquisto Otto dei biglietti per il teatro, si accorgono che sono rimaste solo tre poltrone in prima fila. In quanti modi diversi gli amici possono scegliere di sedersi in tali posti? Una disposizione di n elementi in k posti viene anche chiamata disposizione di n elementi di classe k. Finora abbiamo analizzato solo i casi in cui le cifre sono tutte tra loro diverse, ma in molti problemi, le cifre (o, più in generale, i simboli) possono anche essere ripetute (è il caso dei numeri telefonici, nei quali una stessa cifra può presentarsi più volte). In questi casi si parla di disposizione con ripetizione (di n elementi di classe k) ed è possibile che il numero k dei posti sia maggiore del numero n degli elementi. KEYWORDS K di disposizione con ripetizione / arrangement with repetition 421