In quanti modi? Con quale probabilità?

Il principio fondamentale del conteggio

È il mattone di tutto. Se una scelta si compone di più fasi successive e indipendenti, e la prima fase ha \(n_1\) esiti, la seconda \(n_2\), e così via, allora il numero totale di esiti è il prodotto:

Esempio: un menù con 3 antipasti, 4 primi e 2 dolci offre \(3\cdot4\cdot2=24\) pasti completi diversi. Non serve elencarli: si moltiplica. È il principio moltiplicativo, e da qui derivano tutte le formule che seguono.

Il fattoriale

Il fattoriale di un numero naturale \(n\) è il prodotto di tutti gli interi da 1 a \(n\):

Per esempio \(5!=5\cdot4\cdot3\cdot2\cdot1=120\). Si pone per convenzione \(0!=1\) (c'è un solo modo di non scegliere nulla). Proprietà utilissima da ricordare, perché permette di semplificare le frazioni di fattoriali:

Grazie a essa, per esempio, \(\dfrac{8!}{6!}=\dfrac{8\cdot7\cdot6!}{6!}=8\cdot7=56\): non serve calcolare i fattoriali per intero.

Disposizioni

Le disposizioni riguardano scelte in cui l'ordine conta: prendere \(k\) oggetti da \(n\) e disporli in fila (posti distinti).

Disposizioni semplici (senza ripetizione)

Ogni oggetto si può usare una volta sola. Il numero di disposizioni di \(n\) oggetti a gruppi di \(k\) è

Esempio: il podio di una gara con 8 cavalli (1°, 2°, 3° posto) dà \(D_{8,3}=8\cdot7\cdot6=336\) possibili classifiche. L'ordine conta (arrivare primi o secondi è diverso) e non si ripete (un cavallo non occupa due posti).

Disposizioni con ripetizione

Ogni oggetto si può riusare quante volte si vuole. Ci sono \(n\) scelte a ognuno dei \(k\) posti:

Esempio: un PIN di 4 cifre (da 0 a 9, ripetibili) ha \(10^4=10\,000\) possibilità; le colonne del Totocalcio (13 segni, 3 esiti) sono \(3^{13}\).

Permutazioni

Una permutazione è un ordinamento di tutti gli \(n\) oggetti: è il caso particolare delle disposizioni con \(k=n\).

Permutazioni semplici

Esempio: 5 persone in fila si possono ordinare in \(5!=120\) modi.

Permutazioni con ripetizione

Se alcuni oggetti sono identici tra loro (ripetuti \(h_1, h_2, \ldots\) volte), gli ordinamenti distinti sono di meno, perché scambiare oggetti uguali non produce un nuovo ordine:

Esempio classico: gli anagrammi (anche privi di senso) della parola MAMMA. Ci sono 5 lettere con la M ripetuta 3 volte e la A 2 volte: \(\dfrac{5!}{3!\,2!}=\dfrac{120}{12}=10\).

Combinazioni

Nelle combinazioni l'ordine non conta: si scelgono \(k\) oggetti da \(n\) formando un gruppo, indipendentemente dall'ordine in cui li si prende.

Combinazioni semplici

Il "\(k!\)" al denominatore cancella tutti i possibili ordinamenti dello stesso gruppo. Esempio: una commissione di 3 studenti scelta tra 10 dà \(\binom{10}{3}=\dfrac{10\cdot9\cdot8}{3\cdot2\cdot1}=120\). Il numero \(\binom{n}{k}\) si chiama coefficiente binomiale: lo studieremo nel capitolo successivo.

Combinazioni con ripetizione

Se si possono scegliere più volte gli stessi elementi (ma l'ordine resta irrilevante):

Esempio: quanti coni da 3 palline si possono comporre con 5 gusti disponibili (ripetizioni ammesse)? \(\binom{5+3-1}{3}=\binom{7}{3}=35\).

Anagrammi e percorsi su una griglia

Gli anagrammi di una parola sono tutti i modi diversi di riordinarne le lettere (anche senza significato). Sono l'esempio più naturale di permutazione, e mostrano bene la differenza tra "con" e "senza" ripetizione.

Parole con lettere tutte diverse

Se le \(n\) lettere sono tutte distinte, ogni riordino è diverso: gli anagrammi sono le permutazioni semplici, cioè \(n!\). Esempio: la parola ROMA ha 4 lettere diverse, quindi \(4!=24\) anagrammi.

Parole con lettere ripetute

Se alcune lettere si ripetono, scambiare due lettere uguali non produce un anagramma nuovo: bisogna dividere per le permutazioni interne di ciascun gruppo di lettere uguali. Con una lettera ripetuta \(h_1\) volte, un'altra \(h_2\) volte, ecc.:

Esempio: MATEMATICA ha 10 lettere, con la A ripetuta 3 volte, la M 2 volte, la T 2 volte. Gli anagrammi sono \(\dfrac{10!}{3!\,2!\,2!}=\dfrac{3\,628\,800}{24}=151\,200\).

Il ponte: i percorsi su una griglia

Ecco l'applicazione più elegante. Immagina una griglia rettangolare: vuoi andare dall'angolo in basso a sinistra a quello in alto a destra compiendo solo passi verso destra (D) o verso l'alto (A), sempre lungo le linee, senza mai tornare indietro (percorsi minimi). Per una griglia che richiede \(m\) passi a destra e \(n\) passi in alto, ogni percorso è una sequenza di \(m\) lettere D e \(n\) lettere A: cioè un anagramma di una parola fatta di \(m\) D e \(n\) A!

Lo stesso numero, letto in tre modi diversi: un anagramma (permutazione con ripetizione di due lettere), una combinazione (scegliere quali degli \(m+n\) passi sono "a destra"), e un coefficiente binomiale. Tre linguaggi per una sola idea.

Il problema del resto e i numeri di Catalan

Con lo stesso strumento dei percorsi possiamo affrontare un problema famoso, che a prima vista sembra molto più difficile.

Tradurre la condizione

Il resto di uno spettatore R è una banconota da 25 €, che in cassa arriva solo dagli spettatori C. Quindi in ogni istante la cassa può dare il resto solo se i C entrati finora sono almeno quanti gli R. Se leggiamo la fila come una parola di 5 C e 5 R, la condizione è: in ogni prefisso della parola il numero di C è \(\ge\) al numero di R.

Senza vincolo, le disposizioni sarebbero gli anagrammi di 5 C e 5 R, cioè \(\binom{10}{5}=252\). Ma molte non vanno bene (se un R arriva quando la cassa è vuota, niente resto). Dobbiamo togliere quelle "cattive".

Il principio di riflessione

Rappresentiamo la parola come un cammino: ogni C è un passo a destra, ogni R un passo in alto. La condizione "\(C\ge R\) in ogni prefisso" significa che il cammino resta sotto (o sulla) diagonale. Un cammino "cattivo" prima o poi la oltrepassa, toccando la retta appena sopra. Riflettendo la parte di cammino successiva al primo sconfinamento si ottiene una corrispondenza esatta tra i cammini cattivi e tutti i cammini con 6 R e 4 C: sono \(\binom{10}{4}=210\). Quindi le disposizioni valide sono

La risposta al quesito è 42. Il conteggio non dipende dal caso particolare: quei numeri hanno un nome e una teoria propria, i numeri di Catalan, che presentiamo qui sotto.

I numeri di Catalan

I numeri di Catalan \(C_n\) formano una delle successioni più celebri della matematica: \(1, 1, 2, 5, 14, 42, 132, \ldots\) Compaiono ogni volta che si contano oggetti costruiti "bilanciando" due elementi, come nel problema del resto.

Le formule

L'\(n\)-esimo numero di Catalan si può scrivere in due modi equivalenti — come differenza di coefficienti binomiali (dal principio di riflessione) o in forma chiusa:

Esiste anche una comoda formula ricorsiva per passare da un termine al successivo:

Per esempio da \(C_4=14\) si ottiene \(C_5=\dfrac{2\cdot 9}{6}\cdot 14 = 3\cdot 14 = 42\).

I primi valori

Vederli: le 5 file valide con 3 R e 3 C

Per \(n=3\) il numero di Catalan è \(C_3=5\). Ecco tutte e cinque le disposizioni valide (in ogni prefisso i C non sono mai meno degli R): nota che iniziano sempre con C e finiscono con R.

Dove ricompaiono

La stessa successione conta una varietà sorprendente di oggetti diversi — è questo che la rende famosa:

• le sequenze di \(n\) coppie di parentesi correttamente bilanciate (C = "\(($\)", R = "\()$\)");
• i cammini da un angolo all'altro di una griglia \(n\times n\) che non superano mai la diagonale;
• le triangolazioni di un poligono con \(n+2\) lati;
• gli alberi binari con \(n\) nodi interni;
• e, appunto, le disposizioni del problema del resto.

Lo schema che risolve tutto

Prima di applicare una formula, rispondi alle due domande. La risposta ti porta direttamente allo strumento:

Il coefficiente binomiale

Definito come il numero di combinazioni semplici di \(n\) oggetti a gruppi di \(k\):

Si legge "\(n\) su \(k\)" e conta in quanti modi si può scegliere un sottoinsieme di \(k\) elementi da un insieme di \(n\). Casi limite: \(\binom{n}{0}=\binom{n}{n}=1\) (un solo modo di scegliere nessuno o tutti) e \(\binom{n}{1}=n\).

Le proprietà da conoscere

• Simmetria: \(\displaystyle\binom{n}{k}=\binom{n}{n-k}\). Scegliere chi entra equivale a scegliere chi resta fuori.
• Formula di Stifel (regola di costruzione): \(\displaystyle\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\). Ogni coefficiente è la somma dei due che gli stanno sopra.
• Somma di una riga: \(\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^n\). È il numero di tutti i sottoinsiemi di un insieme di \(n\) elementi.
• Somma di una diagonale (bastone da hockey): \(\displaystyle\binom{n}{k}=\sum_{m=k-1}^{n-1}\binom{m}{k-1}\). Ogni numero è la somma di quelli lungo la diagonale che gli sta sopra.

Il triangolo di Tartaglia

Disponendo i coefficienti binomiali in righe (riga \(n\) contiene \(\binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}\)) si ottiene il triangolo di Tartaglia (o di Pascal). La formula di Stifel diventa una semplice regola di costruzione: ogni numero è la somma dei due sopra di lui.

Ogni riga è simmetrica, comincia e finisce con 1, e la somma dei suoi elementi raddoppia a ogni riga (\(1,2,4,8,16,\ldots=2^n\)). La simulazione ti farà cliccare le celle per vedere queste proprietà dal vivo.

La proprietà del "bastone da hockey"

C'è una proprietà meno nota ma molto elegante, che riguarda le diagonali:

• il secondo numero di ogni riga è la somma dei primi numeri delle righe precedenti;
• il terzo numero di ogni riga è la somma dei secondi numeri delle righe precedenti;
• ...e così via: ogni numero è la somma di tutti quelli che stanno sulla diagonale sopra di lui.

In formula, indicando con \(\binom{n}{k}\) il \((k{+}1)\)-esimo numero della riga \(n\):

Esempio: il terzo numero della riga 5 è \(\binom{5}{2}=10\); ed è proprio la somma dei secondi numeri delle righe precedenti: \(1+2+3+4=10\) (cioè \(\binom{1}{1}+\binom{2}{1}+\binom{3}{1}+\binom{4}{1}\)).

Le diagonali notevoli del triangolo

Le diagonali del triangolo di Tartaglia (lette parallelamente al lato sinistro) nascondono successioni famose. La diagonale \(k\) è formata dai numeri \(\binom{k}{k},\binom{k+1}{k},\binom{k+2}{k},\ldots\)

C'è un filo che le collega tutte, ed è la proprietà del bastone da hockey vista prima: ogni diagonale è fatta dalle somme parziali della diagonale precedente. I numeri triangolari sono le somme dei naturali (\(1,\ 1{+}2,\ 1{+}2{+}3,\ldots = 1,3,6,\ldots\)); i tetraedrici sono le somme dei triangolari (\(1,\ 1{+}3,\ 1{+}3{+}6,\ldots = 1,4,10,\ldots\)).

Le diagonali oblique: la sorpresa di Fibonacci

Sommando i numeri lungo le diagonali oblique (quelle "piatte", che salgono verso destra) si ottiene la celebre successione di Fibonacci \(1, 1, 2, 3, 5, 8, 13, \ldots\), in cui ogni termine è la somma dei due precedenti:

In formula, l'\(r\)-esimo numero di Fibonacci è \(\displaystyle F_r=\sum_{k\ge 0}\binom{r-1-k}{k}\): un'altra successione famosa che si nasconde nel triangolo. La simulazione qui accanto ti fa evidenziare una diagonale alla volta e leggerne la somma.

Il binomio di Newton

Qui sta la sorpresa: i numeri del triangolo di Tartaglia sono esattamente i coefficienti che compaiono sviluppando una potenza di un binomio. Vale la formula del binomio di Newton:

Per esempio, con \(n=3\), leggendo la riga \(1,3,3,1\):

Osserva la struttura di ogni termine: l'esponente di \(a\) cala da \(n\) a \(0\), quello di \(b\) sale da \(0\) a \(n\), e la loro somma è sempre \(n\). Lo sviluppo ha \(n+1\) termini. Perché proprio i coefficienti binomiali? Perché il termine con \(b^k\) si ottiene scegliendo la \(b\) da \(k\) dei fattori \((a+b)\): e i modi di scegliere \(k\) fattori su \(n\) sono \(\binom{n}{k}\).

Esperimenti aleatori, spazio campionario, eventi

Un esperimento aleatorio è una prova il cui esito non è prevedibile con certezza (lancio di un dado, estrazione di una carta). L'insieme di tutti gli esiti possibili è lo spazio campionario \(\Omega\); ogni suo elemento è un evento elementare.

Un evento è un sottoinsieme di \(\Omega\): l'insieme degli esiti che lo realizzano. "Esce un numero pari" con un dado è l'evento \(\{2,4,6\}\). Casi speciali: l'evento certo \(\Omega\), l'evento impossibile \(\varnothing\). Due eventi si dicono incompatibili se non possono verificarsi insieme (\(A\cap B=\varnothing\)).

Le concezioni della probabilità

La stessa parola "probabilità" ha ricevuto interpretazioni diverse, ognuna utile in un contesto:

La definizione classica richiede che i casi siano ugualmente possibili (dado non truccato); è quella che si usa nella maggior parte dei problemi combinatori. La frequentista stima la probabilità con l'esperienza, ed è fondata dalla legge dei grandi numeri. La soggettiva serve quando non ci sono simmetrie né esperimenti ripetibili (probabilità di un evento storico). L'assiomatica le unifica tutte.

Gli assiomi di Kolmogorov

Nel 1933 Kolmogorov definì la probabilità come una funzione \(P\) che a ogni evento associa un numero, soddisfacente tre assiomi. Da questi tre soltanto discende tutta la teoria:

1. Non negatività: \(P(A)\ge 0\) per ogni evento \(A\).
2. Normalizzazione: \(P(\Omega)=1\) (l'evento certo ha probabilità 1).
3. Additività: se \(A\) e \(B\) sono incompatibili, \(P(A\cup B)=P(A)+P(B)\).

Conseguenza immediata: \(0\le P(A)\le 1\) per ogni evento, e \(P(\varnothing)=0\).

I primi teoremi

Probabilità dell'evento contrario

L'evento contrario \(\bar A\) ("non \(A\)") ha probabilità complementare:

Strumento potentissimo: spesso è molto più facile calcolare la probabilità del contrario. "Almeno un 6 in due lanci" conviene calcolarlo come \(1-P(\text{nessun 6})\).

Probabilità totale (unione di due eventi)

Si sottrae \(P(A\cap B)\) perché sommando \(P(A)\) e \(P(B)\) l'intersezione verrebbe contata due volte. Se \(A\) e \(B\) sono incompatibili l'intersezione è vuota e si torna a \(P(A\cup B)=P(A)+P(B)\).

Eventi indipendenti

Due eventi sono indipendenti se il verificarsi dell'uno non altera la probabilità dell'altro. In tal caso la probabilità che si verifichino entrambi è il prodotto:

Attenzione a non confondere incompatibili (non possono coesistere: \(A\cap B=\varnothing\)) e indipendenti (uno non influenza l'altro): due eventi incompatibili con probabilità positiva sono anzi fortemente dipendenti, perché sapere che è accaduto uno esclude l'altro.

Definizione frequentista e legge dei grandi numeri

Se ripetiamo molte volte lo stesso esperimento, la frequenza relativa di un evento (successi diviso prove) tende a stabilizzarsi attorno a un valore. La legge dei grandi numeri di Bernoulli garantisce che, al crescere del numero di prove, questa frequenza si avvicina alla probabilità teorica dell'evento.

È il ponte tra teoria ed esperienza: giustifica sia la stima frequentista (misurare \(P\) contando), sia la nostra fiducia che un dado equo dia "circa un sesto" di sei sul lungo periodo. Attenzione però: la legge non dice che i risultati "si compensano" nel breve periodo (è la fallacia dello scommettitore): il dado non ha memoria.

Probabilità condizionata

La probabilità di \(A\) sapendo che \(B\) si è verificato, indicata \(P(A\mid B)\), si ottiene "restringendo" lo spazio campionario a \(B\):

Esempio: estraggo una carta da un mazzo di 40 e mi dicono che è una figura (fante, cavallo o re: 12 carte). Qual è la probabilità che sia un re? Nello spazio ristretto alle 12 figure, i re sono 4: \(P=4/12=1/3\).

Probabilità composta e indipendenza

Riscrivendo la definizione otteniamo la regola del prodotto (probabilità composta), utile per gli eventi "in sequenza":

Se \(A\) e \(B\) sono indipendenti, allora \(P(A\mid B)=P(A)\): sapere di \(B\) non cambia nulla, e la regola si riduce a \(P(A\cap B)=P(A)P(B)\). Questa è, propriamente, la definizione di indipendenza.

Formula della probabilità totale

Se le cause \(H_1, H_2, \ldots, H_n\) formano una partizione (si escludono a vicenda e coprono tutti i casi), la probabilità di un evento \(E\) si ottiene "disintegrando" \(E\) su ciascuna causa:

È la media delle probabilità condizionate, pesata con la probabilità di ciascuna causa. Esempio (controllo qualità): due macchine producono i pezzi con percentuali e tassi di difetto diversi; la probabilità che un pezzo qualsiasi sia difettoso è la somma dei contributi delle due macchine.

Il teorema di Bayes

Bayes inverte il condizionamento: dalla probabilità dell'effetto data la causa, alla probabilità della causa dato l'effetto. È il cuore dell'inferenza:

Al numeratore la causa che ci interessa, al denominatore la probabilità totale dell'effetto. Il risultato, spesso controintuitivo, è protagonista dei test diagnostici.

Prove ripetute: lo schema di Bernoulli

Consideriamo \(n\) prove indipendenti, ciascuna con due soli esiti — "successo" (probabilità \(p\)) e "insuccesso" (probabilità \(q=1-p\)). È lo schema di Bernoulli (o prove ripetute). La probabilità di ottenere esattamente \(k\) successi su \(n\) prove è

Da dove viene? Una specifica sequenza con \(k\) successi e \(n-k\) insuccessi ha probabilità \(p^k(1-p)^{n-k}\); e le sequenze diverse con \(k\) successi sono \(\binom{n}{k}\) (i modi di scegliere quali prove sono successi). Ecco il calcolo combinatorio che ritorna dentro la probabilità. Esempio: la probabilità di ottenere esattamente 2 teste in 5 lanci di moneta è \(\binom{5}{2}(0{,}5)^2(0{,}5)^3=10\cdot\dfrac{1}{32}=\dfrac{10}{32}\approx0{,}31\).

Variabile aleatoria discreta e sua distribuzione

Una variabile aleatoria (v.a.) \(X\) è una funzione che associa un numero a ogni esito dell'esperimento. È discreta se assume un numero finito (o numerabile) di valori \(x_1, x_2, \ldots\). La sua distribuzione di probabilità assegna a ciascun valore la sua probabilità \(p_i=P(X=x_i)\), con il vincolo

Esempio: lanciando due monete, la v.a. "numero di teste" \(X\) assume i valori 0, 1, 2 con probabilità \(1/4,\ 1/2,\ 1/4\).

Valore atteso, varianza, deviazione standard

Il valore atteso (o media) è la media dei valori pesata con le probabilità: il valore "attorno a cui" ci si aspetta stia \(X\).

La varianza misura quanto \(X\) si disperde attorno alla media; la deviazione standard è la sua radice (stessa unità di misura di \(X\)):

Esempio: per un dado equo \(\mu=\dfrac{1+2+\cdots+6}{6}=3{,}5\) e \(\sigma\approx1{,}71\).

La distribuzione binomiale

Conta i successi nello schema di Bernoulli: \(X\sim B(n,p)\) è il numero di successi in \(n\) prove indipendenti con probabilità \(p\). La sua distribuzione è proprio la formula delle prove ripetute:

Ha valore atteso e varianza particolarmente semplici:

Esempio: in 20 lanci di una moneta equa ci si aspettano \(\mu=20\cdot0{,}5=10\) teste, con \(\sigma=\sqrt{20\cdot0{,}5\cdot0{,}5}=\sqrt5\approx2{,}24\).

La distribuzione di Poisson

Descrive il numero di eventi rari che accadono in un intervallo di tempo o spazio fissato (telefonate a un centralino in un'ora, difetti per metro di tessuto), quando gli eventi sono indipendenti e con un tasso medio \(\lambda\) costante:

Caratteristica notevole: media e varianza coincidono, \(\mu=\sigma^2=\lambda\). La Poisson è il limite della binomiale quando \(n\) è molto grande e \(p\) molto piccolo, con \(np=\lambda\) fissato: per questo è la legge degli "eventi rari".

Variabili continue e densità di probabilità

Una v.a. è continua se può assumere tutti i valori di un intervallo (un'altezza, un tempo di attesa). Qui \(P(X=x)=0\) per ogni singolo valore: ha senso solo la probabilità che \(X\) cada in un intervallo, data dall'area sotto una funzione densità \(f(x)\):

L'area totale sotto la densità vale sempre 1, come la somma delle probabilità nel caso discreto.

La distribuzione normale (gaussiana)

È la più importante distribuzione continua: la celebre "campana" simmetrica attorno alla media \(\mu\), con larghezza governata da \(\sigma\). Si scrive \(X\sim N(\mu,\sigma^2)\) e ha densità

Compare ovunque per il teorema del limite centrale: la somma di molti piccoli effetti indipendenti tende a distribuirsi normalmente. Vale la utilissima regola \(68\text{–}95\text{–}99{,}7\): circa il 68% dei dati cade entro \(\mu\pm\sigma\), il 95% entro \(\mu\pm2\sigma\), il 99,7% entro \(\mu\pm3\sigma\).

Standardizzazione e uso delle tavole

Per calcolare le probabilità si passa alla normale standard \(Z\sim N(0,1)\) tramite la standardizzazione, che misura "quante \(\sigma\)" un valore dista dalla media:

Le tavole della normale standard forniscono l'area \(P(Z\le z)\); da lì, con simmetria e complemento, si ricava qualsiasi probabilità. Esempio: se \(X\sim N(170,10^2)\) (altezze in cm), la probabilità che \(X\le 185\) corrisponde a \(z=\dfrac{185-170}{10}=1{,}5\), da cui \(P(Z\le1{,}5)\approx0{,}933\).