17 - Calcolo combinatorio: contare senza elencare

Corso Machine Learning Engineer · Modulo 02 · Matematica e statistica · Lezione 2

Obiettivo. Imparare a contare in quanti modi può accadere qualcosa senza elencarli uno per uno, con quattro attrezzi (principio moltiplicativo, permutazioni, disposizioni, combinazioni) che deriveremo passo per passo. Alla fine saprai calcolare quante combinazioni di iperparametri contiene una ricerca, quante divisioni training/test esistono, e perché in un gruppo di 23 persone è più probabile che no che due compiano gli anni lo stesso giorno.

Falso mito da sfatare. «Se i casi sono tanti, il computer li prova tutti.» I numeri combinatori crescono più in fretta di qualunque computer. Un mazzo di 52 carte si può ordinare in un numero di modi che ha 68 cifre: nessun computer potrà mai elencarli. Contare con una formula non è un'eleganza matematica, è l'unico modo per sapere in anticipo se una strategia di forza bruta è possibile.

Introduzione

Nella lezione precedente abbiamo incontrato i numeri 2ⁿ (i sottoinsiemi di un insieme) e il prodotto cartesiano (le combinazioni di iperparametri). Qui diamo un metodo generale. La combinatoria è anche la base della probabilità «classica»: se tutti gli esiti sono ugualmente possibili, la probabilità di un evento è casi favorevoli / casi possibili, e per ottenere quei due numeri bisogna saper contare.

Il percorso parte dal principio moltiplicativo, passa per permutazioni, disposizioni e combinazioni, arriva al triangolo di Pascal e ai conteggi con ripetizioni, e si chiude con il paradosso dei compleanni, i numeri troppo grandi per un float e le applicazioni al machine learning. Serve solo ciò che hai visto negli insiemi: Insiemi e logica spiega perché un insieme di n elementi ha 2ⁿ sottoinsiemi.

Il principio moltiplicativo

L'analogia: il menù

Un ristorante offre 3 primi (zuppa, pasta, riso) e 2 secondi (pesce, carne). Quanti menù completi? Per ogni primo hai 2 possibili secondi: 3 × 2 = 6. L'idea è disegnabile come un albero: dalla radice partono tante rami quante sono le scelte del primo passo; da ciascun ramo partono tanti rami quante sono le scelte del secondo; i casi finali sono le foglie.

Principio moltiplicativo. Se un risultato si ottiene con k scelte consecutive, e la prima si può fare in n₁ modi, la seconda in n₂ modi qualunque sia stata la prima, e così via, allora i risultati possibili sono

n₁ × n₂ × … × n_k.

La dimostrazione è l'albero stesso: le foglie dopo il primo passo sono n₁; ciascuna si ramifica in n₂, quindi le foglie dopo due passi sono n₁·n₂; si prosegue per induzione. La condizione importante è nelle parole in grassetto: il numero di scelte al secondo passo non deve dipendere dalla scelta fatta al primo (gli elementi possono cambiare, il loro numero no).

Il codice: contare con la formula e con l'elenco

Verifichiamo la formula su un caso piccolo e la usiamo poi su uno enorme, dove l'elenco è impossibile.

from itertools import product

primi = ["zuppa", "pasta", "riso"]
secondi = ["pesce", "carne"]

menu = list(product(primi, secondi))        # elenca tutte le coppie (primo, secondo)
print(len(menu), "menù elencati |", len(primi) * len(secondi), "con la formula")

# Password di 8 caratteri scelti tra 62 simboli (26 minuscole + 26 maiuscole + 10 cifre):
spazio = 62 ** 8
tentativi_al_secondo = 1e9                  # ipotesi dichiarata: un miliardo di tentativi al secondo
giorni = spazio / tentativi_al_secondo / 86400
print(f"password possibili: {spazio:,}".replace(",", "."))
print(f"tempo per provarle tutte a 10^9 al secondo: circa {giorni:.1f} giorni")

Output ottenuto:

6 menù elencati | 6 con la formula
password possibili: 218.340.105.584.896
tempo per provarle tutte a 10^9 al secondo: circa 2.5 giorni

Cosa fa il codice. product(primi, secondi) produce tutte le coppie: la prima parte della stampa mostra che l'elenco e la formula coincidono (6 e 6). La seconda parte applica la stessa idea a una password: ogni posizione ha 62 scelte, indipendenti dalle altre, quindi 62 · 62 · … · 62 = 62⁸. Dividendo per un'ipotesi di velocità (che dichiariamo: non è una misura) otteniamo l'ordine di grandezza del tempo di un attacco a forza bruta. Il punto non è il numero esatto, ma che aggiungere un carattere moltiplica per 62 lo sforzo dell'attaccante: la lunghezza conta più della «complessità».

Il principio additivo, e la trappola del doppio conteggio

Se un risultato si ottiene in alternativa per casi che non si sovrappongono (o scegli un primo, o scegli un dolce, mai entrambi), i modi si sommano: n₁ + n₂. Quando i casi si sovrappongono, la somma conta due volte quelli in comune: è l'inclusione-esclusione della lezione precedente. Ricorda la regola pratica: «e» (una scelta dopo l'altra) → si moltiplica; «o» (casi alternativi disgiunti) → si somma.

Permutazioni: ordinare tutti

L'analogia: la fila

Hai n persone e n posti in fila. Chi occupa il primo posto? Una qualunque delle n. Il secondo? Una delle n − 1 rimaste. Il terzo: n − 2... fino all'ultimo posto, dove resta una sola persona. Per il principio moltiplicativo le file diverse (le permutazioni di n oggetti) sono

n! = n · (n−1) · (n−2) · … · 2 · 1

(si legge «n fattoriale»). Per convenzione 0! = 1: c'è un solo modo di ordinare zero oggetti (la fila vuota), ed è coerente con la regola n! = n · (n−1)! applicata a n = 1, che dà 1! = 1 · 0!.

La crescita è vertiginosa, e il codice la rende tangibile.

import math

for n in (5, 10, 20, 52):
    print(f"{n:>2}! = {math.factorial(n):,}".replace(",", "."))

print("cifre di 52!:", len(str(math.factorial(52))))

Output ottenuto:

 5! = 120
10! = 3.628.800
20! = 2.432.902.008.176.640.000
52! = 80.658.175.170.943.878.571.660.636.856.403.766.975.289.505.440.883.277.824.000.000.000.000
cifre di 52!: 68

Cosa fa il codice. math.factorial calcola con interi esatti (Python non ha un limite di dimensione per gli interi), quindi 52! viene stampato per intero: ha 68 cifre. Le permutazioni di un mazzo di carte sono quindi circa 8 × 10⁶⁷: se mescoli bene, con probabilità praticamente certa produci un ordine che nessuno, in nessun tempo, ha mai visto prima.

Stirling: stimare un fattoriale

Per n grande esiste una stima celebre, la formula di Stirling (1730):

n! ≈ √(2πn) · (n/e)ⁿ

Non la dimostriamo (richiede strumenti di analisi che vedremo più avanti), ma controlliamo quanto è precisa.

for n in (5, 10, 20, 50):
    esatto = math.factorial(n)
    stirling = math.sqrt(2 * math.pi * n) * (n / math.e) ** n
    errore = (stirling / esatto - 1) * 100
    print(f"n = {n:>2}: errore relativo della stima di Stirling = {errore:6.3f} %")

Output ottenuto:

n =  5: errore relativo della stima di Stirling = -1.651 %
n = 10: errore relativo della stima di Stirling = -0.830 %
n = 20: errore relativo della stima di Stirling = -0.416 %
n = 50: errore relativo della stima di Stirling = -0.167 %

Cosa fa il codice. Per ogni n confronta il valore esatto con la stima e stampa lo scarto percentuale. L'errore scende al crescere di n: già a n = 10 la stima sbaglia meno dell'1%, a n = 50 meno dello 0.2%. È la ragione per cui si può lavorare con log n! senza calcolare il fattoriale intero, come vedremo nella sezione sui numeri enormi.

Disposizioni: ordinare solo alcuni

Se invece di ordinare tutti i n oggetti ne scegli k e conta l'ordine (un podio: primo, secondo, terzo), i posti sono k e i candidati calano di uno a ogni passo:

n · (n−1) · … · (n−k+1) = n! / (n−k)!

Il fattore (n−k)! nel denominatore «cancella» la coda di n! che non serve: n! = n·(n−1)·…·(n−k+1) · (n−k)!.

Se invece si può ripetere lo stesso elemento (le cifre di un PIN), a ogni posto hai sempre n scelte: nᵏ.

Combinazioni: scegliere senza ordine

L'analogia: il podio e il comitato

Il podio ha un primo, un secondo e un terzo; il comitato di tre persone no: Ada-Bea-Carlo e Carlo-Ada-Bea sono lo stesso comitato. Per passare dalle disposizioni alle combinazioni basta chiedersi: quante volte ho contato lo stesso comitato? Ogni gruppo di k persone compare in tutti i suoi k! ordinamenti (le file dei suoi membri). Dividendo si ottiene il coefficiente binomiale:

C(n, k) = n! / (k! · (n−k)!)

(si legge «n su k» e si scrive anche (n k)).

Proprietà, con dimostrazione

1. Simmetria: C(n, k) = C(n, n−k). Scegliere i k che entrano equivale a scegliere gli n−k che restano fuori. (Dalla formula: il denominatore k!(n−k)! è simmetrico.)
2. Identità di Pascal: C(n, k) = C(n−1, k−1) + C(n−1, k). Fissa un elemento «speciale»: i gruppi di k che lo contengono si completano scegliendo gli altri k−1 tra gli n−1 rimanenti (C(n−1, k−1) modi); quelli che non lo contengono si scelgono tutti tra gli n−1 rimanenti (C(n−1, k) modi). Le due classi sono disgiunte e coprono tutti i casi: si sommano.
3. Somma di una riga: C(n,0) + C(n,1) + … + C(n,n) = 2ⁿ. Il membro di sinistra conta i sottoinsiemi per dimensione, quello di destra li conta tutti con il metodo «dentro o fuori» della lezione precedente. Sono due conteggi dello stesso insieme.

Le tre proprietà sono lo stesso fatto visto da angoli diversi: contare gruppi equivale a contare il loro complemento (simmetria), un gruppo contiene o non contiene un dato elemento (Pascal), e la somma delle dimensioni possibili esaurisce tutti i sottoinsiemi. La più utile in pratica è Pascal, perché permette di calcolare un coefficiente con sole somme di interi, senza mai formare un fattoriale enorme.

Il triangolo di Pascal

L'identità di Pascal permette di costruire i coefficienti senza fattoriali: ogni numero è la somma dei due sopra di lui.

def triangolo(righe):
    """Costruisce le prime `righe` righe del triangolo di Pascal con la sola somma."""
    t = [[1]]
    for n in range(1, righe):
        precedente = t[-1]
        nuova = [1] + [precedente[k - 1] + precedente[k] for k in range(1, n)] + [1]
        t.append(nuova)
    return t

t = triangolo(8)
for r in t:
    print(r)

print("riga 6 coincide con math.comb:", t[6] == [math.comb(6, k) for k in range(7)])
print("somma riga 6 = 2^6:", sum(t[6]) == 2 ** 6)

Output ottenuto:

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
riga 6 coincide con math.comb: True
somma riga 6 = 2^6: True

Cosa fa il codice. Ogni riga nuova comincia e finisce con 1 e, nel mezzo, somma a coppie gli elementi della riga precedente (è l'identità di Pascal tradotta in una comprehension). Le due ultime righe verificano due fatti: il triangolo coincide con math.comb (i coefficienti calcolati con la formula) e la somma di una riga è 2ⁿ.

Il teorema binomiale

Espandere (a + b)ⁿ significa moltiplicare n fattori (a + b). Da ciascun fattore scegli a oppure b; il termine aᵏ · bⁿ⁻ᵏ compare tante volte quanti sono i modi di scegliere quali k fattori forniscono la a, cioè C(n, k):

(a + b)ⁿ = Σₖ C(n, k) · aᵏ · bⁿ⁻ᵏ (somma per k da 0 a n).

Per a = b = 1 si ritrova 2ⁿ; per a = p, b = 1−p si trova che le probabilità della distribuzione binomiale sommano a 1, come vedrai nella lezione sulle variabili aleatorie.

Con ripetizioni: anagrammi e stelle e barre

Anagrammi

Quante parole si ottengono permutando le lettere di MAMMA? Se le lettere fossero tutte distinte sarebbero 5! = 120. Ma le 3 M sono indistinguibili: ogni parola è stata contata 3! volte (gli scambi tra le M), e ogni scambio delle 2 A altre 2! volte. Quindi

5! / (3! · 2!) = 10.

In generale con n oggetti di cui n₁ uguali di un tipo, n₂ di un altro, ecc., le permutazioni distinte sono il coefficiente multinomiale n! / (n₁! · n₂! · …).

Stelle e barre: scegliere con ripetizione

Quanti modi ci sono di distribuire k palline identiche in n scatole (alcune possono restare vuote)? Disponi le k palline (le «stelle») in fila e inserisci n − 1 separatori (le «barre») per dividere le scatole. Una sequenza è determinata da quali delle k + n − 1 posizioni sono barre: C(n+k−1, k).

from itertools import permutations

n_scatole, k_palline = 3, 5
formula = math.comb(n_scatole + k_palline - 1, k_palline)

# conteggio diretto: le distribuzioni sono tuple (a, b, c) di interi >= 0 con a + b + c = 5
diretto = sum(1 for a in range(k_palline + 1) for b in range(k_palline + 1 - a))
print("stelle e barre:", formula, "| conteggio diretto:", diretto)

anagrammi = len(set(permutations("MAMMA")))
print("anagrammi di MAMMA:", anagrammi, "| formula 5!/(3!2!):", math.factorial(5) // (math.factorial(3) * math.factorial(2)))

Output ottenuto:

stelle e barre: 21 | conteggio diretto: 21
anagrammi di MAMMA: 10 | formula 5!/(3!2!): 10

Cosa fa il codice. Il primo confronto conta le terne (a, b, c) di interi non negativi con somma 5: per ogni a e b il valore di c è determinato (5 − a − b), quindi basta contare le coppie (a, b) valide. Il secondo genera davvero le 120 permutazioni di "MAMMA" e le rende un insieme per eliminare i doppioni (è la lezione sugli insiemi che lavora per noi). Entrambe le formule trovano 21 e 10.

Applicazione al machine learning. Il campione bootstrap (lo incontreremo nella lezione di statistica) estrae n osservazioni con ripetizione da n: i possibili campioni distinti, ignorando l'ordine, sono C(2n−1, n). Per n = 10 sono già 92 378.

Il paradosso dei compleanni

In un gruppo di n persone, qual è la probabilità che almeno due compiano gli anni lo stesso giorno? (Ipotesi semplificatrici: 365 giorni, tutti ugualmente probabili.)

Strategia: contare il complementare. «Almeno due» è difficile da contare (due coppie? tre persone insieme?); «nessuno in comune» è facile. Tutti i compleanni possibili sono 365ⁿ (principio moltiplicativo: ogni persona ha 365 scelte). I casi senza coincidenze sono le disposizioni: la prima persona ha 365 giorni, la seconda 364, ... la n-esima 365−n+1. Quindi

P(almeno una coincidenza) = 1 − (365 · 364 · … · (365−n+1)) / 365ⁿ.

import numpy as np

def p_coincidenza(n, giorni=365):
    return 1 - math.perm(giorni, n) / giorni ** n

for n in (10, 20, 23, 30, 50, 70):
    print(f"n = {n:>2}: P(almeno due compleanni uguali) = {p_coincidenza(n):.4f}")

# verifica per simulazione: 200000 gruppi di 23 persone
rng = np.random.default_rng(0)
gruppi = rng.integers(0, 365, size=(200_000, 23))
ordinati = np.sort(gruppi, axis=1)
con_doppio = (ordinati[:, 1:] == ordinati[:, :-1]).any(axis=1)
print("simulazione n = 23:", round(float(con_doppio.mean()), 4), "| formula:", round(p_coincidenza(23), 4))

Output ottenuto:

n = 10: P(almeno due compleanni uguali) = 0.1169
n = 20: P(almeno due compleanni uguali) = 0.4114
n = 23: P(almeno due compleanni uguali) = 0.5073
n = 30: P(almeno due compleanni uguali) = 0.7063
n = 50: P(almeno due compleanni uguali) = 0.9704
n = 70: P(almeno due compleanni uguali) = 0.9992
simulazione n = 23: 0.5077 | formula: 0.5073

Cosa fa il codice. math.perm(giorni, n) calcola esattamente le disposizioni 365!/(365−n)! senza costruirle. La simulazione genera 200 000 gruppi di 23 date casuali (una riga per gruppo), ordina ogni riga e controlla se due date adiacenti sono uguali: dopo l'ordinamento, un doppione è sempre adiacente. La frazione di righe con un doppione stima la probabilità, e coincide con la formula entro il rumore della simulazione.

Il risultato sorprende: già con 23 persone la probabilità supera il 50%. L'intuizione sbaglia perché confronta «me contro gli altri» (22 coppie) invece di tutte le coppie possibili, che sono C(23, 2) = 253. Il numero di coppie cresce come il quadrato del gruppo, e la probabilità di coincidenza con esso. È lo stesso fenomeno che fa scontrare i valori di una funzione hash molto prima di quanto ci si aspetti (le collisioni, lezione sulle tabelle hash).

Numeri enormi e calcolo numerico

I fattoriali superano presto la capacità di un float. Python gestisce gli interi esatti, ma NumPy e le librerie scientifiche lavorano in virgola mobile (lezione 4 del modulo 01), dove il numero massimo vale circa 1.8 × 10³⁰⁸.

grande = math.factorial(200)
print("200! ha", len(str(grande)), "cifre")
try:
    float(grande)
except OverflowError as e:
    print("conversione in float:", e)

log10_fatt = math.lgamma(201) / math.log(10)      # log10(200!) senza calcolare 200!
print("log10(200!) =", round(log10_fatt, 4), "| cifre =", int(log10_fatt) + 1)

# C(1000, 500) esatto contro via logaritmi
esatto = math.comb(1000, 500)
via_log = math.exp(math.lgamma(1001) - 2 * math.lgamma(501))
print("C(1000,500) ha", len(str(esatto)), "cifre; via logaritmi ≈ 10^", round(math.log10(via_log), 2))

Output ottenuto:

200! ha 375 cifre
conversione in float: int too large to convert to float
log10(200!) = 374.8969 | cifre = 375
C(1000,500) ha 300 cifre; via logaritmi ≈ 10^ 299.43

Cosa fa il codice. 200! esiste come intero (375 cifre) ma non come float: la conversione solleva OverflowError. La soluzione è lavorare con i logaritmi: math.lgamma(n+1) restituisce ln(n!) (la funzione gamma estende il fattoriale: Γ(n+1) = n!), e un prodotto di termini enormi diventa una somma di logaritmi piccoli. È un trucco usato ovunque nella probabilità e nel machine learning (la log-verosimiglianza). Per C(1000, 500) l'ultimo calcolo mostra che il risultato via logaritmi coincide in ordine di grandezza con l'intero esatto.

Applicazioni nel machine learning

• Numero di divisioni training/test: con n esempi e un test di m, ci sono C(n, m) divisioni diverse. Per n = 100, m = 25 il numero ha 24 cifre: due scienziati con lo stesso dataset e un random_state diverso valutano modelli diversi, e questa è la fonte della variabilità dei risultati.
• Sottoinsiemi di caratteristiche: 2ᵈ (lezione precedente).
• Griglia di iperparametri: prodotto dei numeri di valori, n₁·n₂·…, moltiplicato per i k gruppi della validazione incrociata.
• Alberi di decisione e partizioni: il numero di modi di dividere n esempi in due gruppi è 2ⁿ⁻¹ − 1: nessun algoritmo può esaminarli tutti, e per questo gli alberi usano scelte greedy (passo dopo passo).

Le quattro voci hanno in comune la stessa domanda: quanti casi esistono prima di cominciare a cercare. La prima spiega perché due risultati ottenuti con semi diversi non sono confrontabili alla cifra decimale. La seconda e la quarta dicono che esplorare tutto è impossibile e che serve una strategia. La terza, la griglia, è l'unica che puoi calcolare esattamente prima di lanciare il lavoro, ed è quella del listato seguente.

n, m = 100, 25
print("divisioni train/test possibili (n=100, test=25):", f"{math.comb(n, m):,}".replace(",", "."))

valori = [4, 3, 5, 2]                       # 4 iperparametri con 4, 3, 5, 2 valori
griglia = math.prod(valori)
print("configurazioni:", griglia, "| addestramenti con 5 gruppi:", griglia * 5)

Output ottenuto:

divisioni train/test possibili (n=100, test=25): 242.519.269.720.337.121.015.504
configurazioni: 120 | addestramenti con 5 gruppi: 600

Cosa fa il codice. math.comb(100, 25) dà il numero di test set distinti, math.prod moltiplica i valori per iperparametro (principio moltiplicativo) e il fattore 5 conta i gruppi della validazione. Una griglia che sembra piccola (120 configurazioni) richiede già 600 addestramenti.

Errori tipici (sintomo, causa, rimedio)

• Ordine sì o no? Sintomo: risultato troppo grande di un fattore k!. Rimedio: chiediti «scambiare due elementi cambia il risultato?».
• Ripetizioni sì o no? Sintomo: confondere n!/(n−k)! con nᵏ. Rimedio: chiediti se lo stesso elemento può essere scelto due volte.
• Contare due volte (casi sovrapposti). Rimedio: casi disgiunti, oppure inclusione-esclusione.
• «Almeno uno» contato direttamente. Rimedio: 1 − nessuno (come per i compleanni). Esempio: i PIN a 4 cifre con almeno una ripetizione sono 10⁴ − 10·9·8·7 = 4960.
• Float al posto degli interi. Sintomo: inf o OverflowError con fattoriali oltre 170. Rimedio: interi esatti (math.comb) o logaritmi (lgamma).
• Scambiare C(n, k) con C(n, k) · k!. Rimedio: sapere quale dei due serve.
• Errori di un'unità (estremi): range(1, n) non include n. Rimedio: verificare con un caso piccolo.

Quasi tutti questi errori nascono da una sola omissione: non aver dichiarato, prima di scrivere la formula, se l'ordine conta e se gli elementi si possono ripetere. Le quattro combinazioni possibili di risposte corrispondono alle quattro formule della lezione, e scegliere la formula diventa un'operazione meccanica.

Come lavorare nella pratica

Prima di usare una formula su un caso grande, falla girare su uno minuscolo che puoi elencare con itertools: se i due numeri non coincidono, l'errore è nella formula e non nei dati. Scrivi in una riga che cosa stai contando («modi di scegliere 3 persone su 10, senza ordine, senza ripetizione») e disegna l'albero quando non sai se un prodotto è lecito. Controlla l'ordine di grandezza prima di lanciare qualunque ricerca esaustiva, e preferisci math.comb, math.perm e math.prod, che sono esatti e leggibili.

Il lessico è breve. Il fattoriale n! è il prodotto n·(n−1)·…·1, con 0! = 1. Una permutazione ordina tutti gli elementi, una disposizione ne ordina k scelti fra n, una combinazione ne sceglie k senza ordine e il suo conteggio è il coefficiente binomiale C(n, k). Il complementare è tutto ciò che sta fuori da un insieme, e la forza bruta consiste nel provare ogni caso.

Mini-progetto

1. Scrivi una funzione numero_configurazioni(griglia: dict) che, dato un dizionario {nome: lista di valori}, restituisca il numero di configurazioni e verifica che coincida con len(list(product(...))) su una griglia piccola.
2. Stima in anni il tempo per provare una griglia da 8 iperparametri con 10 valori ciascuno, se ogni addestramento dura 30 secondi (ipotesi dichiarata), con 5 gruppi di validazione. Confrontalo con un budget di 100 configurazioni casuali.
3. Calcola la probabilità del paradosso dei compleanni per un anno di 365 giorni e di 12 mesi (gruppi di n persone, mesi di nascita), e spiega la differenza.

Il primo punto è una funzione di una riga con math.prod. Nel secondo il prodotto dei valori dà le configurazioni, il fattore 5 i gruppi di validazione e i 30 secondi il tempo totale: l'ordine di grandezza che ottieni è di secoli, ed è la ragione per cui il budget di 100 configurazioni casuali non è un ripiego ma l'unica scelta praticabile. Il terzo punto cambia solo il numero di «giorni» (12 invece di 365) e mostra che la soglia del 50% scende a pochissime persone.

Una sfida svolta: contare le mani di poker con una coppia

Mettiamo alla prova le formule su un problema classico. Una mano è un insieme di 5 carte estratte da un mazzo di 52 (13 valori, 4 semi); l'ordine non conta. Quante mani contengono esattamente una coppia (due carte dello stesso valore, e le altre tre di valori tutti diversi tra loro e diversi dalla coppia)?

Costruzione, passo per passo (principio moltiplicativo).

1. Scegli il valore della coppia: 13 modi.
2. Scegli quali due semi (tra 4) hanno le carte della coppia: C(4, 2) = 6 modi.
3. Scegli i tre valori diversi per le altre carte, tra i 12 rimasti: C(12, 3) = 220 modi (è una scelta senza ordine).
4. Per ciascuno di quei tre valori scegli il seme (4 possibilità): 4 · 4 · 4 = 64 modi.

Totale: 13 · 6 · 220 · 64 = 1 098 240 mani. Le mani possibili in tutto sono C(52, 5) = 2 598 960, quindi la probabilità classica è casi favorevoli / casi possibili ≈ 0.4226.

import math
import numpy as np

favorevoli = 13 * math.comb(4, 2) * math.comb(12, 3) * 4 ** 3
possibili = math.comb(52, 5)
print("mani con esattamente una coppia:", f"{favorevoli:,}".replace(",", "."))
print("mani possibili                 :", f"{possibili:,}".replace(",", "."))
print("probabilità esatta             :", round(favorevoli / possibili, 5))

# verifica per simulazione: 300 000 mani casuali
rng = np.random.default_rng(1)
prove = 300_000
mazzo = np.arange(52)
valori = mazzo % 13                                    # 13 valori ripetuti per 4 semi
una_coppia = 0
for _ in range(prove):
    mano = rng.choice(mazzo, size=5, replace=False)
    conteggi = np.bincount(valori[mano], minlength=13)
    if sorted(conteggi[conteggi > 0]) == [1, 1, 1, 2]:  # un valore ripetuto due volte, tre valori singoli
        una_coppia += 1
print("frequenza simulata             :", round(una_coppia / prove, 5))

Output ottenuto:

mani con esattamente una coppia: 1.098.240
mani possibili                 : 2.598.960
probabilità esatta             : 0.42257
frequenza simulata             : 0.42254

Come leggere il codice. Le prime tre righe applicano la formula appena costruita (math.comb per i coefficienti binomiali, 4 ** 3 per i semi). La simulazione estrae 300 000 mani: rng.choice(mazzo, size=5, replace=False) pesca cinque carte senza rimettere (senza ripetizioni), valori = mazzo % 13 associa a ogni carta il suo valore (le carte 0, 13, 26, 39 hanno lo stesso valore), np.bincount conta quante carte della mano hanno ciascun valore, e la condizione sorted(...) == [1, 1, 1, 2] riconosce esattamente la configurazione «un valore due volte e tre valori una volta sola» (esclude il tris, la doppia coppia, il full, il poker). La frequenza simulata si avvicina al valore teorico entro il piccolo rumore di una simulazione.

Nota la struttura del conteggio: i passi 1 e 3 sono scelte senza ordine (combinazioni), il passo 4 ha tre scelte indipendenti con 4 opzioni ciascuna (potenza), e il tutto si moltiplica perché ogni scelta si può fare qualunque sia stata la precedente. Un errore frequente è contare due volte la stessa mano, per esempio scegliendo prima «due valori» e poi decidendo quale dei due è la coppia: la costruzione dell'esempio evita il problema perché ogni mano si costruisce in un solo modo. Controllare questa unicità è il test che ogni conteggio combinatorio dovrebbe superare. Il metodo vale come regola generale: costruisci l'oggetto passo per passo, per ogni passo conta le scelte, moltiplica; poi, quando puoi, verifica con una simulazione.

Challenge

• Easy. Quante targhe esistono con 2 lettere (26), 3 cifre e 2 lettere? Verifica il principio moltiplicativo con un sottoinsieme ridotto (2 lettere, 1 cifra).
• Medium. Dimostra con l'identità di Pascal e l'induzione che Σₖ C(n,k) = 2ⁿ, e verifica per n da 0 a 15.
• Hard. Quante mani di 5 carte contengono un full (un tris e una coppia di valori diversi)? Conta con il principio moltiplicativo (valore del tris, semi del tris, valore della coppia, semi della coppia) e verifica con una simulazione come quella svolta nella lezione.
• Expert. Dimostra che la probabilità di coincidenza dei compleanni è approssimata da 1 − exp(−n(n−1)/(2·365)) (suggerimento: ln(1−x) ≈ −x per x piccolo) e confronta numericamente con la formula esatta.
• Enterprise. Per un progetto reale, calcola quante combinazioni conterrebbe la ricerca esaustiva dei suoi iperparametri e dichiara il budget di calcolo; scegli e giustifica una ricerca ridotta.

Le cinque sfide crescono per astrazione, non per quantità di codice: le prime due consolidano il principio moltiplicativo e la somma di una riga del triangolo, la terza e la quarta ti obbligano a contare e a dimostrare, l'ultima ti chiede di decidere quanto budget spendere. Se ne scegli una sola, scegli la Hard: il full si costruisce con gli stessi quattro passi delle mani con una coppia.

Per esercitarti sul torneo simulato del circolo di scacchi trovi lo scheletro con le parti da completare e, in fondo, le soluzioni commentate in esercizi.py: confronta i conteggi del girone con l'enumerazione di itertools, costruisce il coefficiente binomiale con la ricorrenza di Pascal e verifica stelle e barre per enumerazione. Richiede solo Python 3.12 o successivo e si lancia con python3 esercizi.py; il file non è stato eseguito per questo articolo.

Che cosa sai fare adesso

Sai scegliere fra le quattro formule chiedendoti se l'ordine conta e se gli elementi si ripetono, stimare in anticipo se una ricerca esaustiva di iperparametri è praticabile, contare «almeno uno» passando dal complementare e lavorare con i fattoriali enormi tramite interi esatti o logaritmi. Il passo successivo è la probabilità, che usa questi conteggi come numeratore e denominatore, e subito dopo le variabili aleatorie per i casi in cui gli esiti non sono equiprobabili. Come ripasso trasversale, la statistica userà il bootstrap che qui hai incontrato come conto con ripetizione.

Nella stessa serie trovi anche: 15 - scikit-learn: stimatori, pipeline e validazione, 21 - Analisi matematica 1: limiti e derivate (che richiamano questa lezione).