“Bene, adesso parliamo di calcolo combinatorio”.
Silenzio intimorito.
“Chi non sopporta questo argomento?”.
Boato unanime di adesione.
È così che va ogni qualvolta, o quasi, si introduca il calcolo combinatorio in aula perché da tempo immemore sono pochi i temerari che provano simpatia per questo povero ed emarginato capitolo della matematica.
Sarà un caso che l’abbreviazione risulti essere CACO?
Io non credo.
In questa sede cercheremo di definire pochi ma chiari concetti che potrebbero aiutarvi nel trovare il suddetto CACO meno ostile, magari addirittura a renderlo, se non vostro amico, almeno un simpatico conoscente.
PERMUTAZIONI
Per permutazione si intende il modo di ordinare in successione n elementi distinti.
Equivale ad individuare il numero di possibilità nell’avere gli elementi in ordine diverso.
Immaginatevi di avere n elementi sopra una scrivania e allo stesso tempo di avere un’altra scrivania con un numero di scatoline pari al numero degli elementi stessi, che risulteranno ogni volta tutti presenti ma in ordine diverso. L’esempio classico della permutazione è il calcolo dei possibili anagrammi costruibili a partire da una parola.
Permutazione semplice ($P_s$)
Poniamo il caso che gli n elementi presi in considerazione siano tutti diversi, come ad esempio nella parola MANO (n=4). In quanti modi posso ordinarli? Ovvero, quanti anagrammi esistono della parola MANO?
Andando a valutare quali lettere posso “inserire” nelle scatole vediamo che nella prima postazione ho n scelte (nell’esempio n=4: M,A,N,O), nella seconda avrò n-1 scelte (infatti una lettera l’avrò già usata precedentemente), nella terza n-2, nella quarta avrò invece n-3 (che in questo caso rappresenta l’ultima), etc.
Per calcolare quindi i possibili ordini diversi faccio il prodotto tra le scelte in successione:
n*(n-1)*(n-2)*(n-3)…*1=n!
$P_s$=n!
Permutazione con ripetizione ($P_r$)
In questo caso all’interno degli n elementi ce ne saranno alcuni che si ripetono. Di conseguenza, invertendo questi elementi, otteniamo degli anagrammi uguali. Questi anagrammi uguali devono essere tolti dal nostro calcolo e, per far ciò, si divide n! per i fattoriali delle volte in cui un elemento si ripete. Sì, lo so, detto così sembra che non si capisca nulla, ma vediamo in dettaglio la formula per fare un po’ di chiarezza:
$q_1$ è il numero di volte in cui si ripete l’elemento 1, $q_2$ è il numero di volte in cui si ripete l’elemento 2, $q_3$ è il numero di volte in cui si ripete l’elemento 3.
Numero di anagrammi di CARAMELLA: $P_r$(CARAMELLA)=9!/3!2!=30240 (la A si ripete 3 volte, la L si ripete 2 volte).
DISPOSIZIONI
Per disposizione si intende il numero di modi in cui posso ordinare un numero k di elementi selezionati da un insieme più grande di n elementi. Ritornando all’esempio delle scrivanie: abbiamo sulla prima n elementi e posso sceglierne k per volta e metterli in modo ordinato all’interno delle scatoline sulla seconda scrivania (che questa volta saranno di numero inferiore rispetto a n perché, per definizione di disposizione, k).
Disposizione semplice (Ds)
Nella disposizione semplice quando pesco n elementi sulla prima scrivania, ogni elemento potrà esser preso una sola volta.
Poniamo k=3: sulla seconda scrivania avrò solo 3 scatoline in cui inserire i miei elementi. Per la prima postazione pesco dalla prima scrivania e ho n scelte. Per la seconda postazione, poiché posso pescare un elemento una volta sola ho n-1 scelte. Per la terza postazione, nonché ultima visto che abbiamo posto k=3, avrò n-2 scelte. Il calcolo quindi delle disposizioni sarà dato dal prodotto delle possibili scelte in successione:
se k=3 n*(n-1)*(n-2) → questo non è altro che dividere il valore di n! per x!, con x = n-k.
Disposizione con ripetizione ($D_r$)
Nella disposizione con ripetizione posso pescare dal primo insieme di n elementi ogni elemento più volte. Consideriamo ancora k=3.
Per ogni postazione ho sempre n scelte perché gli elementi possono essere pescati anche tutte le volte. La disposizione con ripetizione quindi è calcolata come il prodotto delle mie possibili scelte in successione:
se k=3 Dr=n*n*n ovvero
Dr=nk
COMBINAZIONI
Con le combinazioni introduciamo una terza scrivania con al di sopra una ciotola, la quale può contenere elementi indipendentemente dal loro ordine.
Infatti, dato un insieme di n elementi, una combinazione corrisponde al numero dei possibili sottoinsiemi che ne possono derivare, considerando k elementi alla volta (dove k<n). Nelle combinazioni non è importante l’ordine con cui peschiamo gli elementi dalla prima scrivania, mentre è invece di rilevante importanza se un elemento è presente/non è presente nella ciotola.
Importa la presenza dell’elemento, non la sua posizione.
Per togliere dal nostro calcolo tutti i sottoinsiemi che contengono gli stessi elementi ma in ordine diverso dividiamo il calcolo delle disposizioni semplici per k!
Facciamo un esempio: ho una classe di 25 studenti e voglio istituire due rappresentanti di classe, senza distinzione di grado tra i due. A questo punto se scelgo Maddalena e Roberto oppure Roberto e Maddalena dalla prima scrivania e li metto nella ciotola, il risultato sarà lo stesso.
$C_s$=25!/2!(25-2)!=25!/2!23!=25*24/2=300.
ESERCIZIO 1
La nonna di Pierino ha una scatola contenente 17 cioccolatini, tutti di un gusto diverso. Pierino ha il permesso di mangiarne due al giorno e oggi avrebbe proprio voglia del cioccolatino al burro di arachidi e di quello all’amarena. Ne pesca tre dalla scatola, quant’è la probabilità che tra quei tre ci siano proprio i cioccolatini desiderati da Pierino?
A. 3*$\frac{2}{17}$
B. $\frac{6}{136}$
C. $\frac{2}{17}$
D. $\frac{3}{136}$
E. Impossibile essere così fortunati
Ebbene sì, miei cari, nel test d’ingresso spesso il calcolo combinatorio non è presente fine a se stesso, ma al servizio della probabilità. Sapendo che la probabilità che si verifichi un evento “A” è data dal rapporto tra gli eventi favorevoli e gli eventi totali, andiamo a calcolare questi due numeri.
Eventi totali: tutti i possibili sottoinsiemi contenenti tre cioccolatini diversi → combinazione semplice con k=3 partendo da un insieme di 17 elementi (n=17). Infatti non è importante l’ordine con il quale vengono pescati i cioccolatini, ma quali si trovino nel palmo di Pierino → $E_tot$=$C_s$=17!/3!(17-3)!=17!/3!14!=680.
Ora calcoliamo gli eventi favorevoli, ovvero i sottoinsiemi che contengono il cioccolatino al burro di arachidi e quello all’amarena: l’unico che può variare affinché la richiesta sia accontentata è il terzo cioccolatino e per questa posizione ci sono ancora 15 cioccolatini possibili che possono capitare → eventi favorevoli: 15. Probabilità dell’evento desiderato: 15/680=3/136.
Risposta corretta D.
NB. Non vi deve spaventare il fatto che i fattoriali siano prodotti di molti numeri (magari a due cifre) perché spesso, in gran parte, si possono semplificare.
