Alcuni esempi classici

Mostriamo ora alcuni esempi classici di applicazioni del calcolo combinatorio:

1. P. Massimo numero intero senza segno rappresentabile con una parola di un computer a 32 bit.

   R. È equivalente al numero di parole di 32 lettere che si possono formare da un alfabeto di 2 lettere (0, 1): $2^{32}=4294967295$.

2. P. Una moneta regolare viene lanciata $50$ volte. È più probabile la sequenza con 50 teste o la sequenza con testa e croce alternate?

   R. Si tratta di r-disposizione di $n=2$ oggetti (``T'', ``C'') con $r = 50$. Il loro numero è $2^{50}\approx 1.13\cdot 10^{15}$. Assumendo l'indipendenza dei lanci ogni sequenza ha la stessa probabilità ( $\approx 8.88 \cdot 10^{-16}$).

3. P. Perché molti sono convinti che la sequenza che ha il $50\,\%$ di teste e il $50\,\%$ di croci sia più probabile di quella con tutte teste?

   R. Si confonde la probabilità della singola sequenza con la probabilità di una qualsiasi sequenza che abbia metà teste e metà croci. Il numero totale di queste è dato da $\binom{50}{25} = 1.26\cdot 10^{14}$. Queste sono in effetti l'11.2% del totale, ma purtroppo per vincere bisogna indovinare quella giusta.

4. P. Calcolare la probabilità di estratto semplice, ambo, terna, quaderna e cinquina su una ruota del lotto (indipendentemente dall'ordine di estrazione).

   R. Il lotto ha $N=90$ ``palline numerate'' (evitiamo di chiamarle ``numeri'' per evitare confusione) delle quali ne vengono sorteggiate $n=5$. Il numero di gruppi di $r$ elementi (con $r=1, 2, 3, \ldots$ per singolo estratto, ambo, terna, etc.) che si possono formare con le $N$ palline è:

   $$\binom{90}{r}\,.$$
   Di questi gruppi possibili, quelli favorevoli per vincere sono quelli che è possibile formare con le 5 palline estratte. Ne segue

   $$P(r) = \frac{\binom{5}{r}} {\binom{90}{r}} = \frac{5\times \cdots \times (5-r+1)} {90\times \cdots \times (90-r+1)}\,,$$ (3.14)

   
   
   da cui segue la formula ricorsiva
   

   $$P(r) = P(r-1)\cdot\frac{6-r}{91-r} \hspace{0.8 cm} r=2, 3, \ldots, 5\,,$$

   
   
   con $P(r=1)=1/18$.

   È interessante mostrare anche un altro modo di ragionare per ottenere lo stesso risultato: ci sono

   $$\binom{90}{5}$$
   possibili cinquine. Di queste ce ne sono
   $$\binom{90-r}{5-r}$$
   che contengono le $r$ palline della scommessa (pari al numero di combinazioni delle rimanenti $90-r$ palline nelle $5-r$ posizioni che non interessano ai fini della scommessa). Ne segue

   $$P(r) = \frac{\binom{90-r}{5-r}} {\binom{90}{5}}\,,$$ (3.15)

   
   
   che ovviamente dà gli stessi risultati della (3.14).
5. P. Quanto vale la probabilità che in un gruppo di $r$ persone ce ne siano almeno due che hanno il compleanno lo stesso giorno? (Si assuma una distribuzione uniforme nelle nascite nei 365 giorni dell'anno e si trascurino per semplicità i bisestili.)
   

   Tabella: Probabilità che in un gruppo di $r$ persone almeno due abbiano il compleanno lo stesso giorno. Il calcolo è basato sull'equiprobabilità delle nascite e trascurando l'effetto degli anni bisestili

   $r$	5	10	15	20	23	30	41	46	57	70
   $P$ (%)	2.7	11.7	25.3	41.1	50.7	70.6	90.3	94.8	99.0	99.9

   
   

   R. Conviene partire dalla probabilità che tutte le $r$ persone abbiano compleanni diversi, ovvero che $r$ giorni estratti fra i 365 giorni dell'anno siano tutti differenti. Essa, data l'ipotesi di equiprobabilità, si riduce al calcolo del numero dei casi possibili (pari alle $r$-disposizioni di $n$ oggetti) e a quello dei casi favorevoli (pari alle $r$-disposizioni semplici di $n$ oggetti):
   

   $$P(E_r) = 1 - P(\overline{E}_r) = 1 - \frac{(n)_r}{n^r}$$ (3.16)

   $$= 1 - \frac{365\times 364 \times \cdots \times (365-r+1)} {365^r}$$

   $$= 1 - \frac{365}{365}\times \frac{364}{365} \times \cdots \times \frac{365-r+1}{365}\,.$$

   
   
   In tabella 3.2 è riportata $P(E_r)$ per alcuni valori di $r$. Si tenga conto che in realtà le nascite non sono distribuite uniformemente, ma si verificano più spesso in alcuni periodi dell'anno. Questo effetto tende a far aumentare la probabilità di coincidenze di compleanno (si immagini se, ad esempio, il 90% delle nascite si verificasse concentrate in un solo mese e il restante 10% negli altri mesi dell'anno).