Pillole Testbusters e Matematica: calcolo combinatorio

Introduzione

“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 ilcalcolo combinatorioin 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 essereCACO?

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

Perpermutazionesi intende il modo di ordinare in successionenelementi distinti.

Equivale adindividuare il numero di possibilitànell’avere gli elementi inordine diverso.

Immaginatevi di averenelementi 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 possibilianagrammicostruibili a partire da una parola.

Permutazione semplice($P_s$)Poniamo il caso che glinelementi 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 honscelte (nell’esempio n=4: M,A,N,O), nella seconda avròn-1scelte (infatti una lettera l’avrò già usata precedentemente), nella terzan-2, nella quarta avrò invecen-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 conripetizione($P_r$)

In questo caso all’interno deglinelementi ce ne saranno alcuni che siripetono. Di conseguenza, invertendo questi elementi, otteniamo degli anagrammi uguali. Questi anagrammi uguali devono essere tolti dal nostro calcolo e, per far ciò, si dividen! 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 possoordinareun numerokdi elementiselezionatida un insieme più grande dinelementi. Ritornando all’esempio delle scrivanie: abbiamo sulla primanelementi e posso scegliernekper volta e metterli in modo ordinato all’interno delle scatoline sulla seconda scrivania (che questa volta saranno di numero inferiore rispetto anperché, per definizione di disposizione,k).

Disposizione semplice(Ds)Nella disposizione semplice quando pesco n elementi sulla prima scrivania, ogni elemento potrà esser presouna sola volta.

Poniamok=3: sulla seconda scrivania avrò solo 3 scatoline in cui inserire i miei elementi. Per la prima postazione pesco dalla prima scrivania e honscelte. Per la seconda postazione, poiché posso pescare un elemento una volta sola hon-1scelte. Per la terza postazione, nonché ultima visto che abbiamo postok=3, avròn-2scelte. Il calcolo quindi delle disposizioni sarà dato dal prodotto delle possibili scelte in successione:sek=3 n*(n-1)*(n-2)→ questo non è altro che dividere il valore din! perx!, conx = n-k.

Disposizione con ripetizione ($D_r$)Nella disposizione con ripetizione posso pescare dal primo insieme dinelementi ogni elementopiù volte. Consideriamo ancorak=3.

Per ogni postazione ho semprenscelte 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:sek=3 Dr=n*n*novvero

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 dinelementi, una combinazione corrisponde al numero dei possibilisottoinsiemiche ne possono derivare, considerandokelementi alla volta (dovek<n). Nelle combinazioninon è importante l’ordine con cui peschiamo gli elementidalla 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 perk!

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, neltest d’ingressospesso il calcolo combinatorio non è presente fine a se stesso, ma alservizio 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 conk=3partendo 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 glieventi 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.

Ebbene sì, miei cari, neltest d’ingressospesso il calcolo combinatorio non è presente fine a se stesso, ma alservizio 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 conk=3partendo 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 glieventi 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.