Cenni di calcolo combinatorio.
“Questa branca della matematica è, credo, l’unica nella quale buoni studiosi spesso ottengono risultati
del tutto errati”
Charles Pierce (1878)
Per affrontare le questioni inerenti al calcolo delle probabilità, dobbiamo ripensare il nostro modo di contare. Di questo si occupa il calcolo combinatorio.
Per esempio, se possediamo due cravatte e quattro camicie, quanti abbinamenti camicia-cravatta possiamo formare? Evidentemente, ognuna delle due cravatte può essere abbinata con ognuna delle quattro camicie:
L’esempio delle camicie e delle cravatte suggerisce una regola generale per contare gli abbinamenti tra gli elementi di un insieme e quelli di un altro insieme. Si tratta del Principio fondamentale del contare:
Se un elemento x viene scelto tra m elementi, ed un elemento y viene scelto tra s elementi, allora le possibili scelte di x e y sono ms.
Consideriamo i seguenti esempi.
Esempio 1.
Quante coppie miste si possono formare da un gruppo contenente 4 ragazzi e 3 ragazze?
Ogni ragazzo può essere abbinato ad una qualsiasi delle 3 ragazze. Poiché i ragazzi sono 4, le scelte saranno 12.
Esempio 2.
Quante targhe “all’italiana” si possono formare?
Una targa all’italiana è una sequenza alfanumerica del tipo LLNNNLL dove L rappresenta una lettera e N un numero. Le lettere vengono
selezionate dall’alfabeto di 22 simboli (alle 21 lettere dell’alfabeto si tolgono le lettere I, O, Q, U e si aggiungono le lettere J, K, W, X, Y), mentre i numeri possono essere formati con le cifre da 0 a 10. Il conteggio è presto fatto:
22⋅22⋅10⋅10⋅10⋅22⋅22 = 234.256.000.
Se ogni anno vengono immatricolate un milione di auto, questo modo di contrassegnare le targhe automobilistiche è sostenibile ancora per molto tempo…
Esempio 3.
Quanti numeri di sei cifre si possono scrivere tali che la prima cifra non sia zero, e che due qualunque cifre consecutive siano distinte?
La prima cifra può essere scelta in 9 modi diversi, così come le restanti 5.
Complessivamente si possono quindi scrivere
96 = 531.441
numeri con le caratteristiche richieste.
Un concetto molto importante in questi processi di conteggio è costituito dal cosiddetto Principio additivo.
Dati due insiemi A e B risulta card( A∪B) = card( A)+ card(B)− card( A∩B) .
Esempio 4.
In una classe di 24 studenti vengono proposti due test. 18 studenti superano il primo test, 17 superano il secondo test, 14 superano
entrambi i test. Quanti studenti superano almeno un test?
Se interpretiamo “almeno un test” come “test 1 o test 2”, dal principio additivo risulta
card(test1∪test2) = card(test1)+ card(test2)− card(test1∩test2) =18+17−14 = 21.
Esempio 5.
Quante targhe all’italiana contengono almeno un 7 ed almeno una A?
Ragioniamo sugli insiemi complementari:
le targhe che contengono nessun 7 sono 224 ⋅93 =170.772.624 , quelle che contengono nessuna A sono 214 ⋅103 =194.481.000, mentre quelle che contengono nessun 7 e nessuna A sono 214 ⋅93 =141.776.649.
A questo punto le targhe cercate si ottengono togliendo dal totale delle targhe che si possono formare quelle che non contengono nessun 7 o nessuna A, che rappresentano il complementare dell’insieme cercato:
234.256.000− (170.772.624 +194.481.000−141.776.649) = 10.779.025.
(367)