Lezione 2. Il calcolo combinatorio

In questa lezione

Perché la probabilità uniforme porta al calcolo combinatorio?
Quali sono le due regole base per contare?
Come si contano disposizioni e combinazioni?
Che cos'è il paradosso dei compleanni?
Come si calcolano le estrazioni da un'urna?
Quando si può usare la re-immissione al posto della non re-immissione?
Quali sono le trappole tipiche per i concetti di questa lezione?
Quiz della lezione (10 domande)

1. Perché la probabilità uniforme porta al calcolo combinatorio?

Su $\Omega=\{\omega_1,\dots,\omega_n\}$ con probabilità uniforme, $P(\{\omega_i\})=\frac1n$ per ogni $i$ . Allora per ogni evento

P(E)=\frac{|E|}{n}=\frac{\text{casi favorevoli}}{\text{casi possibili}}.

Calcolare una probabilità diventa contare gli elementi di un insieme.

2. Quali sono le due regole base per contare?

Regola	Formula	Quando si usa
Somma (partizione)	$\big\|\bigcup_{i=1}^n A_i\big\|=\sum_{i=1}^n\|A_i\|$ , con $A_i$ disgiunti	L'insieme si divide in pezzi disgiunti: «il tutto è la somma delle parti»
Prodotto	$\|A_1\times\dots\times A_n\|=\prod_{i=1}^n\|A_i\|$	Ogni elemento è una sequenza ordinata di scelte

Principio delle scelte successive. Se ogni elemento di $Y$ è determinato in modo unico da $k$ scelte successive, e alla scelta $i$ ci sono $n_i$ possibilità, allora $|Y|=n_1\cdot n_2\cdots n_k$ .

3. Come si contano disposizioni e combinazioni?

Oggetto	L'ordine conta?	Ripetizioni?	Numero
Disposizioni con ripetizione di lunghezza $k$	Sì	Sì	$n^k$
Disposizioni senza ripetizione	Sì	No	$n(n-1)\cdots(n-k+1)$
Permutazioni di $k$ oggetti	Sì	No	$k!=k(k-1)\cdots 2\cdot 1$
Combinazioni (sottoinsiemi di $k$ elementi)	No	No	$\displaystyle\binom nk=\frac{n!}{k!\,(n-k)!}$

Una disposizione con ripetizione è una funzione $f:\{1,\dots,k\}\to\Omega$ ; senza ripetizione è una funzione iniettiva. Per convenzione $0!=1$ .

Perché si divide per $k!$ . Ogni sottoinsieme di $k$ elementi compare in $k!$ disposizioni diverse (i suoi riordinamenti). Quindi $\binom nk=\dfrac{n(n-1)\cdots(n-k+1)}{k!}$ .

Esempi. Parole di 6 lettere sull'alfabeto inglese: $26^6=308\,915\,776$ . Con circa 15 000 parole inglesi sensate di 6 lettere, una sequenza a caso ha senso con probabilità $\approx 4{,}86\cdot10^{-5}$ . Lotto: $\binom{90}{5}=43\,949\,268$ cinquine.

4. Che cos'è il paradosso dei compleanni?

Con $n$ persone e compleanni uniformi su 365 giorni, qual è la probabilità $P(E)$ che almeno due festeggino lo stesso giorno?

Contare $E$ direttamente è difficile: troppi casi (coppie, terne…).
Si passa al complementare $E^c$ = «tutti nati in giorni diversi»: sono disposizioni senza ripetizione.
Risultato: $P(E)=1-\frac{365\cdot364\cdots(365-n+1)}{365^n}.$

Persone $n$	$P(E)$
23	circa 0,507 (più del 50%)
50	circa 0,970

5. Come si calcolano le estrazioni da un'urna?

Urna con $n$ palline, $m$ verdi e $n-m$ rosse. Si estraggono $k$ palline: probabilità di avere $v$ verdi.

Modello	Formula	Significato
Con re-immissione (campionamento indipendente)	$\displaystyle\binom kv\frac{m^v(n-m)^{k-v}}{n^k}=\binom kv p^v(1-p)^{k-v}$ , con $p=\frac mn$	Scelgo le posizioni delle verdi, poi le palline: ogni volta stesse proporzioni
Senza re-immissione (campionamento dipendente)	$\displaystyle\frac{\binom mv\binom{n-m}{k-v}}{\binom nk}$	Si ignora l'ordine: scelgo $v$ verdi e $k-v$ rosse tra i sottoinsiemi di $k$

Esempio svolto. Urna con 4 verdi e 6 rosse; 3 estrazioni. Senza re-immissione, $P(2\text{ verdi})=\binom42\binom61/\binom{10}3=36/120=0{,}3$ . Con re-immissione, $\binom32(0{,}4)^2(0{,}6)=0{,}288$ .

Variante «almeno». Banca di 300 domande, $m$ su argomenti fondamentali; test di 30 domande. Gli eventi $E_v$ = «esattamente $v$ fondamentali» sono disgiunti, quindi $P(\text{almeno 15})=\sum_{v=15}^{30}\frac{\binom mv\binom{300-m}{30-v}}{\binom{300}{30}}.$ Il calcolo numerico mostra che servono $m\ge204$ per superare il 99%.

6. Quando si può usare la re-immissione al posto della non re-immissione?

Se $n$ e $m$ sono grandi, $m/n$ non è troppo piccolo e il campione $k$ è piccolo rispetto a $n$ , le due probabilità quasi coincidono. La dispensa ricava la stima

P_{\text{senza}}(E)\le\Big(1+\frac{k^2}{n}\Big)P_{\text{con}}(E)\qquad\text{se }(k-1)^2<n.

Per popolazioni finite il modello corretto è senza re-immissione; quello con re-immissione è più semplice e l'errore è trascurabile quando $k^2\ll n$ .

Refusi della dispensa: nelle disposizioni senza ripetizione al passo $j$ le scelte sono $n-j+1$ e l'ultimo fattore è $n-k+1$ (non $n-j-1$ , $n-k-1$ ); nella formula con re-immissione le verdi sono $m$ e le rosse $n-m$ .

7. Quali sono le trappole tipiche per i concetti di questa lezione?

Disposizioni o combinazioni? Chiediti se $(1,34,22)$ e $(34,22,1)$ sono lo stesso esito: se sì, combinazioni.
L'ultimo fattore è $n-k+1$ , non $n-k$ : i fattori sono esattamente $k$ .
«Almeno uno» o «almeno due»: spesso conviene passare al complementare.
Gli eventi «esattamente $v$ » sono disgiunti: per «almeno 15» si sommano, non si moltiplicano.
Con e senza re-immissione non sono uguali: quasi uguali solo se il campione è piccolo rispetto alla popolazione.

8. Quiz della lezione (10 domande)

Domande di ripasso create per questa scheda a partire dalla dispensa (non sono il test ufficiale della piattaforma). Scegli una risposta: ricevi subito esito e spiegazione.