Calcolo combinatorio per la probabilità

Prima: Spazi di probabilità discreti e uniformiIn uno spazio discreto la probabilità è determinata dalla densità discreta p(ω) = P({ω}), con somma 1, e P(A) è la somma di p(ω) sugli esiti di A; negli spazi uniformi (esiti equiprobabili) P(A) = |A| / |Ω|, casi favorevoli su casi possibili.Spazi di probabilità discreti e uniformi →. Dopo: Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata →. Esercizi svolti: Esercizio 4 · 42 teste in 100 lanci di una moneta, Esercizio 10 · vincita con due estrazioni da un'urna e Esercizio 11 · lotto, numero 33 per 90 settimane (probabilità che il 33 esca in un'estrazione di 5 numeri su 90).

In uno spazio uniformeΩ finito con esiti equiprobabili: P(A) = casi favorevoli / casi possibili.Spazi di probabilità discreti e uniformi → $\mathbb{P}(A) = |A| / |\Omega|$: servono regole per contare gli elementi di $A$ e di $\Omega$ senza elencarli. Le stesse regole sono introdotte, con le stringhe di simboli, in Fattoriale e coefficienti binomialiFattoriale, permutazioni, disposizioni, combinazioni e coefficiente binomiale n su k, con il triangolo di Tartaglia.Fattoriale e coefficienti binomiali → (Analisi 1); qui si riprendono con il linguaggio delle estrazioni e delle sequenze di prove.

Principio di moltiplicazione

Principio (di moltiplicazione). Se una scelta si fa in $k$ passi successivi, e al passo $i$ ci sono $n_i$ possibilità qualunque siano le scelte fatte prima, il numero totale di scelte è $$n_1 \cdot n_2 \cdots n_k$$

Esempio. Un menù con 3 primi, 4 secondi e 2 dolci permette $3 \cdot 4 \cdot 2 = 24$ pasti diversi: per ciascuno dei 3 primi ci sono 4 secondi ($3 \cdot 4 = 12$ coppie primo-secondo), e ognuna di queste 12 coppie si completa con 2 dolci ($12 \cdot 2 = 24$). Una targa con 2 lettere (26 possibili) e 3 cifre: i passi sono 5 (lettera, lettera, cifra, cifra, cifra) con $26, 26, 10, 10, 10$ possibilità, quindi $26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 = 26^2 \cdot 10^3 = 676 \cdot 1000 = 676\,000$.

Attenzione al "qualunque siano le scelte fatte prima". Conta il numero di possibilità a ogni passo, non quali siano: nelle disposizioni semplici (sotto) al secondo passo gli oggetti disponibili cambiano a seconda del primo scelto, ma sono sempre $n - 1$, e questo basta per moltiplicare.

Tutte le formule seguenti sono casi particolari di questo principio.

Le quattro formule fondamentali

Si scelgono $k$ oggetti da un insieme di $n$ oggetti distinti. Le domande da farsi sono due:

1. L'ordine conta? ($(1, 2)$ e $(2, 1)$ sono scelte diverse?)
2. Si possono ripetere gli oggetti? (lo stesso oggetto può essere scelto più volte?)

Esempio per vedere le quattro caselle: $n = 3$ oggetti $\{a, b, c\}$, $k = 2$ scelte. Con ordine e ripetizione: $3^2 = 9$ coppie ($aa, ab, ac, ba, bb, bc, ca, cb, cc$). Con ordine, senza ripetizione: si tolgono le 3 coppie $aa, bb, cc$, restano $\frac{3!}{1!} = 6$. Senza ordine né ripetizione: $ab = ba$ ecc., restano $\binom32 = 3$ ($\{a,b\}, \{a,c\}, \{b,c\}$). Senza ordine, con ripetizione: le 3 coppie non ordinate più $aa, bb, cc$, cioè $\binom{3 + 2 - 1}{2} = \binom42 = 6$.

Da dove viene $\binom{n+k-1}{k}$. Una scelta senza ordine con ripetizione è decisa da quante volte si prende ciascun oggetto. Si scrive come una fila di $k$ pallini (le scelte) e $n - 1$ sbarre (che separano gli $n$ oggetti): con $n = 3$, $k = 2$ la fila $\bullet \mid \mid \bullet$ vuol dire "una $a$, nessuna $b$, una $c$". Le file sono lunghe $n + k - 1$ e sono determinate dalle posizioni dei $k$ pallini, quindi sono $\binom{n+k-1}{k}$. In probabilità si usa poco perché questi esiti, in genere, non sono equiprobabili (ad esempio con due dadi "un 1 e un 2" ha probabilità $\frac{2}{36}$, "due 1" ha probabilità $\frac{1}{36}$).

Disposizioni con ripetizione: $n^k$

Sequenze ordinate di $k$ elementi presi da $n$, con ripetizioni ammesse. Per ogni posizione ci sono $n$ scelte, indipendentemente dalle altre: $n \cdot n \cdots n = n^k$.

Esempi: risultati di $k$ lanci di un dado: $6^k$; sequenze di $100$ lanci di moneta: $2^{100}$; parole binarie di 8 bit: $2^8 = 256$.

Disposizioni semplici: $\frac{n!}{(n-k)!}$

Sequenze ordinate di $k$ elementi distinti presi da $n$ ($k \le n$). Il primo si sceglie in $n$ modi, il secondo in $n - 1$ (non si può ripetere il primo), ..., il $k$-esimo in $n - k + 1$:

Formula (disposizioni semplici). $$n (n-1) \cdots (n - k + 1) = \frac{n!}{(n-k)!}$$

Perché le due scritture sono uguali. I fattori a sinistra sono $k$ (da $n$ fino a $n - k + 1$). Si moltiplica e si divide per $(n-k)! = (n-k)(n-k-1) \cdots 1$: al numeratore il prodotto continua senza buchi da $n$ fino a $1$, cioè diventa $n!$, e resta il denominatore $(n-k)!$. Con $n = 10$, $k = 3$: $\frac{10!}{7!} = \frac{10 \cdot 9 \cdot 8 \cdot 7!}{7!} = 10 \cdot 9 \cdot 8$.

Esempio: podio (oro, argento, bronzo) tra 10 atleti: $10 \cdot 9 \cdot 8 = 720$ (10 possibili ori, poi 9 argenti tra i rimasti, poi 8 bronzi).

Permutazioni: $n!$

Caso $k = n$: modi di ordinare $n$ oggetti distinti, $n! = n (n-1) \cdots 2 \cdot 1$ (con la convenzione $0! = 1$). La formula delle disposizioni con $k = n$ dà $\frac{n!}{0!}$, e deve valere $n!$ (si ordinano tutti gli $n$ oggetti): per questo si pone $0! = 1$. Le proprietà del fattoriale sono in Fattoriale e coefficienti binomialiFattoriale, permutazioni, disposizioni, combinazioni e coefficiente binomiale n su k, con il triangolo di Tartaglia.Fattoriale e coefficienti binomiali →.

Esempio: modi di mescolare un mazzo di 52 carte: $52! \approx 8{,}07 \cdot 10^{67}$. Il fattoriale cresce più in fretta di ogni esponenziale $a^n$ (vedi Limiti notevoli e gerarchia degli infinitiI limiti di base per sciogliere le forme indeterminate delle successioni: potenze, polinomi, il numero e, esponenziali, la gerarchia logaritmi < potenze < esponenziali < fattoriale < n^n e la razionalizzazione.Limiti notevoli e gerarchia degli infiniti →): per questo anche mazzi piccoli danno numeri enormi.

Combinazioni: $\binom{n}{k}$

Sottoinsiemi di $k$ elementi di un insieme di $n$: ordine irrilevante, niente ripetizioni. Si contano le disposizioni semplici, $\frac{n!}{(n-k)!}$, e si osserva che ogni sottoinsieme di $k$ elementi è stato contato $k!$ volte (una per ogni ordine dei suoi elementi, cioè una per ogni permutazione dei suoi $k$ elementi). Esempio: il sottoinsieme $\{a, b, c\}$ compare tra le disposizioni come $abc, acb, bac, bca, cab, cba$, cioè $3! = 6$ volte. Dividendo per $k!$ ogni sottoinsieme resta contato una volta sola:

Formula (combinazioni). $$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$$

È il coefficiente binomialen su k = n! / (k! (n−k)!), lo stesso numero che compare nello sviluppo di (a + b)^n.Fattoriale e coefficienti binomiali → di Analisi 1.

Esempi: mani di 5 carte da un mazzo di 52: $\binom{52}{5} = \frac{52 \cdot 51 \cdot 50 \cdot 49 \cdot 48}{5!} = \frac{311\,875\,200}{120} = 2\,598\,960$; cinquine del lotto da 90 numeri: $\binom{90}{5} = \frac{90 \cdot 89 \cdot 88 \cdot 87 \cdot 86}{120} = 43\,949\,268$. In pratica si usa la forma $\binom{n}{k} = \frac{n (n-1) \cdots (n-k+1)}{k!}$, che si ottiene semplificando $(n-k)!$ come sopra.

Proprietà utili: $\binom{n}{0} = \binom{n}{n} = 1$, $\binom{n}{1} = n$, $\binom{n}{k} = \binom{n}{n-k}$ (scegliere i $k$ da prendere equivale a scegliere gli $n - k$ da lasciare). Inoltre $\sum_{k=0}^{n} \binom{n}{k} = 2^n$: a sinistra si contano i sottoinsiemi di $\{1, \dots, n\}$ raggruppati per numero di elementi, a destra tutti i sottoinsiemi (ogni elemento dentro o fuori); è anche il binomio di Newton(a + b)^n = Σ_{k=0}^{n} (n su k) a^k b^(n−k).Binomio di Newton → con $a = b = 1$.

Sequenze con un numero fissato di successi

Quante sequenze di lunghezza $n$ in $\{T, C\}$ hanno esattamente $k$ teste? Una sequenza è individuata dalle posizioni delle teste, cioè da un sottoinsieme di $k$ posizioni tra le $n$: sono $\binom{n}{k}$.

Esempio: con $n = 4$, $k = 2$: $TTCC, TCTC, TCCT, CTTC, CTCT, CCTT$, cioè $\binom42 = 6$ ✓.

Questo conteggio risolve il problema delle 42 teste su 100 lanci ($\binom{100}{42}$ sequenze favorevoli) e sta alla base del modello binomialeP(k successi in n prove) = (n su k) p^k (1−p)^(n−k).Prove ripetute e modello binomiale →.

Estrazioni da un'urna

Un'urna contiene $N$ palline, di cui $M$ nere e $N - M$ bianche. Se ne estraggono $n$. Le palline si pensano numerate (anche se dello stesso colore), così gli esiti sono equiprobabili.

Con reinserimento

Dopo ogni estrazione la pallina viene rimessa nell'urna: la composizione non cambia. Esiti: sequenze ordinate con ripetizione, $|\Omega| = N^n$. Ogni estrazione dà nera con probabilità $\frac{M}{N}$, indipendentemente dalle altre, e

Formula (estrazioni con reinserimento). $$\mathbb{P}(k \text{ nere}) = \binom{n}{k} \left(\frac{M}{N}\right)^k \left(1 - \frac{M}{N}\right)^{n-k}$$

Da dove viene. Si contano le sequenze favorevoli con il principio di moltiplicazione: si scelgono le $k$ posizioni (tra le $n$ estrazioni) in cui esce una nera, in $\binom{n}{k}$ modi; poi in ciascuna di quelle $k$ posizioni si sceglie quale nera, $M$ modi ciascuna ($M^k$), e in ciascuna delle altre $n - k$ quale bianca ($(N - M)^{n-k}$). Dividendo per $|\Omega| = N^n = N^k \cdot N^{n-k}$: $$\mathbb{P}(k \text{ nere}) = \frac{\binom{n}{k} M^k (N-M)^{n-k}}{N^k \, N^{n-k}} = \binom{n}{k} \left(\frac{M}{N}\right)^k \left(\frac{N-M}{N}\right)^{n-k},$$ e $\frac{N - M}{N} = 1 - \frac{M}{N}$. È la densità binomiale con $p = \frac{M}{N}$, ritrovata in Prove ripetute e modello binomialen prove indipendenti, ciascuna con probabilità di successo p: una sequenza con k successi ha probabilità p^k (1−p)^(n−k), e la probabilità di esattamente k successi è (n su k) p^k (1−p)^(n−k) (modello binomiale); il primo successo alla prova k ha probabilità (1−p)^(k−1) p.Prove ripetute e modello binomiale →.

Esempio. Urna con $M = 8$ nere su $N = 14$, $3$ estrazioni con reinserimento: $\frac{M}{N} = \frac{8}{14} = \frac47$, $1 - \frac47 = \frac37$, e $\mathbb{P}(2 \text{ nere}) = \binom{3}{2} \left(\frac{4}{7}\right)^2 \frac{3}{7} = 3 \cdot \frac{16}{49} \cdot \frac37 = \frac{144}{343} \approx 0{,}420$.

Senza reinserimento

Le palline estratte non vengono rimesse. Conviene guardare l'insieme delle $n$ palline estratte (ordine irrilevante): $|\Omega| = \binom{N}{n}$, e questi sottoinsiemi sono equiprobabili (nessun gruppo di palline numerate è favorito). Per avere $k$ nere si scelgono $k$ nere tra le $M$, in $\binom{M}{k}$ modi, e $n - k$ bianche tra le $N - M$, in $\binom{N-M}{n-k}$ modi; per il principio di moltiplicazione ogni scelta delle nere si combina con ogni scelta delle bianche, quindi i casi favorevoli sono il prodotto:

Formula (estrazioni senza reinserimento, distribuzione ipergeometrica). $$\boxed{\mathbb{P}(k \text{ nere}) = \frac{\binom{M}{k} \binom{N - M}{n - k}}{\binom{N}{n}}} \qquad \text{(distribuzione ipergeometrica)}$$

I valori di $k$ possibili sono quelli con $k \le M$ e $n - k \le N - M$; per gli altri uno dei due coefficienti binomiali è $0$ (non si possono scegliere più nere di quante ce ne siano).

Esempio numerico: 8 nere e 6 bianche, 3 estrazioni

$N = 14$, $M = 8$, $n = 3$; probabilità di estrarre esattamente 2 nere.

• Senza reinserimento: $\binom82 = \frac{8 \cdot 7}{2} = 28$, $\binom61 = 6$, $\binom{14}3 = \frac{14 \cdot 13 \cdot 12}{6} = 364$, quindi $\dfrac{\binom82 \binom61}{\binom{14}3} = \dfrac{28 \cdot 6}{364} = \dfrac{168}{364} = \dfrac{6}{13} \approx 0{,}462$ (si divide sopra e sotto per $28$). Controllo con le sequenze ordinate: la sequenza $NNB$ ha probabilità $\frac{8}{14} \cdot \frac{7}{13} \cdot \frac{6}{12}$ (ogni pallina estratta cambia l'urna), e le posizioni della bianca sono 3: $3 \cdot \frac{8 \cdot 7 \cdot 6}{14 \cdot 13 \cdot 12} = \frac{1008}{2184} = \frac6{13}$ ✓. Contare con o senza ordine dà lo stesso risultato, purché si faccia la stessa scelta al numeratore e al denominatore.
• Con reinserimento: $\binom32 \left(\frac8{14}\right)^2 \frac6{14} = 3 \cdot \frac{16}{49} \cdot \frac37 = \frac{144}{343} \approx 0{,}420$.

Facendo lo stesso conto per tutti i $k$ si ottengono le due densità:

Senza reinserimento i valori estremi ($0$ o $3$ nere) sono meno probabili: dopo una nera l'urna ha meno nere, e questo "spinge" verso un campione misto. Se $N$ è grande rispetto a $n$ togliere poche palline cambia poco l'urna e le due densità si avvicinano.

La stessa urna (8 nere, 6 bianche, 2 estrazioni con reinserimento) compare nell'esercizio 3 del I parziale: Esercizio 10 · vincita con due estrazioni da un'urna.

Esempio: il lotto

Si estraggono 5 numeri su 90 senza ripetizione. Probabilità che tra questi ci sia il 33:

$$\mathbb{P} = \frac{\binom{89}{4}}{\binom{90}{5}} = \frac{5}{90} = \frac1{18} \approx 0{,}056$$

Perché: $\Omega$ è l'insieme delle cinquine (sottoinsiemi di 5 numeri tra 90, ordine irrilevante), $|\Omega| = \binom{90}{5}$. Le cinquine che contengono il 33 si ottengono fissando il 33 e scegliendo gli altri 4 numeri tra gli 89 rimanenti, in $\binom{89}{4}$ modi. La semplificazione: dividere per una frazione è moltiplicare per la reciproca, quindi $$\frac{\binom{89}{4}}{\binom{90}{5}} = \frac{89!}{4!\,85!} \cdot \frac{5!\,85!}{90!} = \frac{89!}{90!} \cdot \frac{5!}{4!} = \frac{1}{90} \cdot 5 = \frac{5}{90},$$ dove $85!$ si cancella, $90! = 90 \cdot 89!$ e $5! = 5 \cdot 4!$. Interpretazione: ciascuno dei 90 numeri ha la stessa probabilità di essere tra i 5 estratti, e in media ne escono 5 su 90, quindi $\frac{5}{90}$. Il seguito (90 settimane di gioco) è nell'Esercizio 11 · lotto, numero 33 per 90 settimane.

Esempio: il problema dei compleanni

In una classe di $k$ persone (365 giorni equiprobabili, niente anni bisestili), probabilità che almeno due compiano gli anni lo stesso giorno?

• $\Omega =$ sequenze ordinate di $k$ compleanni, con ripetizione: $|\Omega| = 365^k$.
• Il complementare "tutti i compleanni diversi" è fatto di disposizioni semplici: il primo compleanno ha 365 possibilità, il secondo 364 (diverso dal primo), ..., il $k$-esimo $365 - k + 1$, in tutto $365 \cdot 364 \cdots (365 - k + 1)$.

$$\mathbb{P}(\text{almeno due uguali}) = 1 - \frac{365 \cdot 364 \cdots (365 - k + 1)}{365^k}$$

"Almeno due uguali" comprende molti casi diversi (due uguali, tre uguali, due coppie...), "tutti diversi" uno solo: per questo si conta il complementare. È un buon esempio di passaggio al complementareP(A) = 1 − P(Aᶜ): "almeno due uguali" è difficile da contare, "tutti diversi" è facile.Misura di probabilità e sue proprietà →.

Con $k = 23$ si ottiene già $\approx 0{,}507$: più di una possibilità su due. Altri valori: $k = 10$: $0{,}117$; $k = 30$: $0{,}706$; $k = 50$: $0{,}970$.

Perché cresce così in fretta: una stima. Si scrive la frazione come prodotto di $k$ fattori $\frac{365 - i}{365} = 1 - \frac{i}{365}$ per $i = 0, \dots, k-1$. Per $x$ piccolo $1 - x \approx e^{-x}$ (è lo sviluppo $e^{-x} = 1 - x + o(x)$, vedi Sviluppi di Mac-Laurin notevoliTabella degli sviluppi di Mac-Laurin da sapere a memoria (e^x, sin, cos, log(1+x), (1+x)^alpha, arctan, sinh, cosh, tan) e regole per combinarli: algebra degli o piccoli, prodotti, funzioni composte, quanti termini tenere.Sviluppi di Mac-Laurin notevoli →), e un prodotto di esponenziali è l'esponenziale della somma (Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →): $$\prod_{i=0}^{k-1} \Big(1 - \frac{i}{365}\Big) \approx \exp\Big(-\frac{1}{365} \sum_{i=0}^{k-1} i\Big) = \exp\Big(-\frac{k(k-1)}{730}\Big),$$ dove $\sum_{i=0}^{k-1} i = \frac{(k-1)k}{2}$ è la somma di Gauss (vedi SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →). Il numero di coppie di persone, $\binom{k}{2} = \frac{k(k-1)}{2}$, cresce come $k^2$: con 23 persone le coppie sono già 253, e ciascuna ha probabilità $\frac{1}{365}$ di coincidere. Con $k = 23$ la stima dà $1 - e^{-253/365} \approx 0{,}500$, vicina al valore esatto $0{,}507$.

Come scegliere la formula

1. Fissare $\Omega$ in modo che gli esiti siano equiprobabili (oggetti numerati, sequenze ordinate se c'è un ordine naturale).
2. Chiedersi se l'ordine conta e se ci sono ripetizioni → tabella sopra.
3. Contare $A$ con la stessa convenzione usata per $\Omega$.
4. Se $A$ è "almeno uno", provare a contare il complementare.

Errori comuni

• Mescolare convenzioni: contare $\Omega$ con l'ordine e $A$ senza (o viceversa).
• Confondere con e senza reinserimento: con reinserimento le estrazioni sono indipendenti e si usa la binomiale; senza, l'ipergeometrica.
• Dimenticare di moltiplicare per il numero di posizioni (es. $3$ posizioni per la bianca in $NNB$, $NBN$, $BNN$).
• Trattare come non distinguibili palline dello stesso colore: gli esiti "per colore" non sono equiprobabili.