CALCOLO COMBINATORIO
La combinatoria si occupa degli insiemi finiti e del conteggio degli elementi di particolari insiemi.
Prima di affrontare questo argomento, c'è bisogno di chiarire una distizione:
- per insieme intendiamo una collezione di elementi, dove non diamo importanza all'ordine con cui gli elementi vengono elencati: l'insieme {a,b,c} è uguale all'insieme {b,c,a} e all'insieme {c,b,a} etc.
-
per sequenza invece, intendiamo un elenco di elementi, considerando che due sequenze sono diverse se due elementi occupano un posto diverso: la sequenza abc è diversa dalla sequenza bca e dalla sequenza cba.
I principi fondamentali della combinatoria sono i seguenti:
-
Principio moltiplicativo: ci sono $n\times m$ sequenze di due simboli il cui primo è scelto tra $n$ e il secondo tra $m$.
-
Principio additivo: se A e B sono due insiemi che non hanno elementi in comune, allora il numero di elementi che sono in A oppure in B è dato dalla somma del numero di elementi di A e del numero di elementi di B.
Vediamo qualche esempio.
Supponiamo che in un gioco di costruzioni per bambini ci siano tre mattoncini colorati, uno rosso, uno giallo e uno blu. Quante diverse torri composte dai tre mattoncini si possono formare?
Dati questi tre rettangoli colorati :
 |  |  | |||||||||||
Otteniamo le seguenti combinazioni :
Questo è un esempio di una permutazione di 3 elementi (diversi tra loro).
Per contare quante permutazioni di tre elementi si possono fare, possiamo ragionare così: il primo mattoncino lo possiamo scegliere di tre
colori diversi. Il secondo lo possiamo scegliere di due colori, perché uno dei tre colori lo avremo sicuramente già utilizzato
prima. Il terzo elemento sarà l'unico mattonicino rimasto. Quindi ci sono $3\times 2 \times 1=6$ diverse permutazioni.
In genere una
permutazione di $n$ elementi è una sequenza di questi n elementi. Ci sono $n!=n\times(n-1)\times(n-2)\times...\times 1$
permutazioni di $n$ elementi, infatti al primo posto posso scegliere tra n elementi diversi, al secondo posto non posso
più scegliere l'elemento che è stato messo al primo posto, quindi potrò scegliere tra n-1 e così
via.
Disposizioni semplici
Una disposizione di $n$ elementi su $h$ posti è una sequenza di $h$ elementi scelti tra $n$
(dove non è permesso ripetere gli oggetti già utilizzati).
Se per esempio voglio scrivere tutte le sequenze di tre oggetti scelti tra i cinque pallini colorati
, 
, 
,
, 
, potrò scegliere il primo simbolo tra i 5 disponibili, il secondo
tra i 4 che rimangono e il terzo tra i 3 che rimangono togliendo il primo e il secondo. In totale $5\times4\times3$.
In genere, se vogliono scrivere le sequenze di $h$ elementi scelti tra $n$, avrò $n\times(n-1)\times...\times(n-h+1)$
sequenze.
Inserisci un numero k (compreso tra 1 e 5), indicante la classe delle disposizioni con ripetizione che si vogliono ottenere:
Disposizioni con ripetizione
Se invece si permette la ripetizione dei simboli, allora di hanno le disposizioni con ripetizione. Il numero di disposizioni con ripetizione di $n$ elementi su $h$ posti è dato da $n^h$: infatti il primo elemento è scelto tra tutti i possibili $n$, il secondo tra tutti gli $n$ e così via fino ad ottenere il prodotto di $n$ con se stesso per $h$ volte.
Inserisci il numero k, indicante la classe delle disposizioni con ripetizione che si vogliono ottenere:
Combinazioni
Nei casi visti finora, abbiamo costruito sequenze di simboli, cioè ci siamo interessati a contare degli oggetti in cui è importante l'ordine dei simboli che vi compare (contando le disposizioni abbiamo assunto che la disposizione *+ è diversa da +*).Cosa succede invece se non siamo interessati a distinguere l'ordine con cui si succedono i simboli, cioè se vogliamo contare gli insiemi?
Supponiamo di voler ordinare una pizza scegliendo qualcuno dei seguenti ingredienti: pomodori, mozzarella, funghi, salame, prosciutto, wurstel.
Chiaramente la pizza con mozzarella e funghi è uguale a quella con funghi e mozzarella, non importa l'ordine con cui scelgo gli elementi.
Se per esempio voglio solo tre ingredienti, quante diverse pizze potrò fare? Qui il calcolo è un po' più complicato: il primo ingrediente potrà essere scelto tra 6, il secondo tra i 5 rimanenti e il terzo tra 4, ma contando in questo modo si ripetono le pizze con gli stessi ingredienti in ordine diverso. Devo quindi eliminarle e per fare questo divido il numero ottenuto per 6.
Ecco gli ingredienti tra cui puoi scegliere per creare la tua pizza:
 |
 |
 |
 |
 |
 |
Inserisci il numero di ingredienti che vorresti nella tua pizza:
In genere ci si può trovare di fronte a situazioni in cui non si può semplicemente applicare una formula, ma bisogna ragionare sul tipo di oggetto che si ha davanti. Il consiglio è di chiedersi prima di tutto se bisogna contare delle sequenze o degli insiemi, cioè se conta l'ordine dei simboli come nel caso delle disposizioni, oppure se l'ordine non importa, come nel caso delle combinazioni.
Supponiamo di voler contare quante targhe formate da 4 lettere e 3 cifre esistono (supponiamo che le targhe siano formate da due lettere, tre cifre e poi di nuovo due lettere).
Pensiamo a quanti modi ci sono per scegliere i vari simboli:
il primo simbolo della targa può essere scelto tra tutti i simboli dell'alfabeto, quindi in 26 modi possibili.
Il secondo simbolo può essere ancora scelto in 26 modi diversi, e allora in quanti modi possono scegliere i primi
due simboli insieme?
Per ognuna delle scelte del primo simbolo posso scegliere il secondo in 26 modi:
se il primo simbolo è A, il secondo può essere A,B,C,etc.
Se il primo simbolo è B, il secondo può essere A,B,C, etc.
e così via.
Quindi ho $26\times26$ modi di scegliere i primi due simboli.
Andando avanti, posso scegliere il terzo simbolo (che deve essere una cifra) in 10 modi diversi, quindi ci sono
$26\times26\times10$ triplette.
Continuando questo ragionamento, posso concludere che ci saranno
$26 \times 26 \times 10 \times 10 \times 10 \times 26 \times 26$
targhe diverse che contengano 4 lettere e 3 cifre.
Facciamo un altro esempio:
in un ristorante si può ordinare un menù scegliendo un primo, un secondo e un contorno.
Il ristorante offre tre tipi di primi, quattro tipi di secondi e due contorni. Se voglio provare ogni giorno un menu
diverso, quante volte devo andare in questo ristorante? Posso scegliere tre primi, per ognuno dei quali posso scegliere
quattro secondi, quindi ho $3\times4$ modi diversi di scegliere un primo e un secondo. Per ognuna di queste scelte ho
la possibilità di abbinare due contorni, quindi in tutto ho $3\times4\times2$ possibili menù.
Supponiamo invece che un pasto sia composto o da un primo o da un secondo: allora il numero di pasti è dato dalla somma dei primi e dei secondi. Questo è un esempio in cui utilizzare il principio additivo.
Per esempio, proviamo a contare quanti pasti si possono formare scegliendo o un primo e un secondo o un secondo e un contorno, supponendo sempre che ci siano tre tipi di primi, quattro tipi di secondi e due contorni. Ci sono $3\times 4$ possibili combinazioni di primi e secondi e $4\times 2$ combinazioni di secondi e contorni, quindi in tutto $20=12+8$ possibili pasti.
Nota che nel principio additivo è importante specificare che i due insiemi A e B non hanno elementi in comune. Infatti se per esempio vogliamo contare i numeri interi maggiori di zero e minori di 10 che sono pari o multipli di 3, non possiamo semplicemente sommare il numero di numeri pari (che sono 2,4,6,8) e quello dei multipli di 3 (che sono 3,6,9) perché avremmo 7, mentre invece la risposta giusta è 6 (sono i numeri 2, 3, 4, 6, 8, 9). Il numero 6 non deve essere contato due volte.
Il principio moltiplicativo ci accompagna anche per capire alcuni semplici esempi di probabilità, ma prima di vedere come, abbiamo appunto bisogno di dare qualche elemento elementare di questa disciplina.
Probabilità
Vedremo ora qualche nozione elementare di probabilità, ricordando che questa è una disciplina molto complessa e interessante che non può essere certo ridotta a queste poche righe.
Quello che ci interessa adesso è capire alcuni semplici casi, nei quali è facile calcolare la probabilità utilizzando la formula:
Il più semplice (e anche il più noto) è quello della famosa moneta: qual è la probabilità che lanciando una moneta (chiaramente non truccata) esca testa? Dobbiamo confontare i casi possibili con i casi favorevoli: il nostro caso favorevole è "esce testa", i casi possibili sono "esce testa" e "esce croce". Quindi un caso favorevole su due casi possibili, quindi la probabilità che esca testa è 1 su due.
Vediamo un po' un altro esempio: la probabilità che lanciando un dado esca 4. Quindi un caso favorevole (esce 4) su 6 casi possibili (i sei possibili lati del cubo), la probabilità è 1 su 6.
Rendiamo le cose più complicate: ho due dadi, qual è la probabilità che lanciandoli, il primo dado dia 4 e il secondo 6? Sappiamo calcolare la probabilità che il primo lancio dia 4, è 1 su 6, e che da solo il secondo dia 6, è ancora 1 su 6. Ma qual è la probabilità che i due eventi accadano insieme?
Ci viene incontro il principio moltiplicativo: dobbiamo moltiplicare le probabilità dei due eventi, quindi otteniamo che la probabilità è 1 su 36 (Nota, stiamo considerando il semplice caso che i due eventi siano indipendenti, cioè che non influiscano uno sull'altro).
E se ho un cesto con 10 palline bianche e 20 palline rosse, qual è la probabilità che si estragga una pallina
bianca?
I casi favorevoli sono 10 (le palline bianche), i casi possibili sono 30 (tutte le palline) quindi la probabilità
richiesta è $\frac{10}{30}$ cioè $\frac{1}{3}$.
E se voglio sapere la probabilità che la seconda estratta sia rossa, non rimettendo nel cesto la prima?
Dipende dal fatto di sapere o no il colore della prima. Infatti se so che la prima pallina estratta è bianca,
allora nel cesto rimangono 9 palline bianche e 20 palline rosse, quindi la probabilità che la seconda sia rossa
è 20/29.
Ma se non conosco il colore della prima pallina, devo considerare due casi: o la prima pallina è
bianca o è rossa. Nel primo caso, come detto prima, la probabilità che la seconda sia rossa è 20/29,
invece se la prima pallina estratta è rossa, la probabilità che anche la seconda sia rossa è 19/29
(sono rimaste 19 palline rosse su un totale di 29).
Per avere una unica stima della probabilità possiamo ragionare in questo modo: i casi favorevoli sono "prima pallina
bianca, seconda pallina rossa" e "prima pallina rossa, seconda pallina rossa", mentre i casi possibili sono tutte le
possibili coppie di palline.
Quante coppie di palline si possono formare? Ci sono inizialmente 30 palline, quindi (per il principio moltiplicativo)
possiamo formare $30\times 30$ coppie di palline.
Invece di coppie "pallina bianca, pallina rossa" ce ne sono $10\cdot20$ mentre di coppie "pallina rossa, pallina rossa" ce ne sono $20\cdot20$. In totale quindi la probabilità che la seconda sia rossa è esattamente la stessa probabilità che la prima pallina estratta sia rossa!!!
Possiamo ragionare anche in un altro modo, ricorrendo al principio additivo. La probabilità è la somma dei due casi possibili: o la prima è rossa e la seconda è rossa oppure la prima è bianca e la seconda è rossa.
Quindi $\frac{20}{30} \times \frac{19}{29} + \frac{10}{30} \cdot \frac{20}{29} = \frac{2}{3}$.