La regola della somma funziona solo per casi disgiunti. Quando gli insiemi si sovrappongono, sommare le loro dimensioni conta più volte gli elementi comuni. Il principio di inclusione-esclusione corregge l'errore in modo sistematico: si aggiungono le dimensioni, si tolgono le sovrapposizioni a due a due, si riaggiungono quelle a tre a tre, e così via. È uno strumento semplice che risolve problemi di conteggio altrimenti scomodi.
Due insiemi
|A ∪ B| = |A| + |B| − |A ∩ B|
Gli elementi che stanno sia in A sia in B vengono contati due volte da |A| + |B|; sottraendo |A ∩ B| li si conta una volta sola.
Esempio: in un'azienda 40 dipendenti usano il portatile aziendale, 25 usano il telefono aziendale e 10 usano entrambi. Quanti usano almeno uno dei due dispositivi? 40 + 25 − 10 = 55.
Tre insiemi
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Perché si riaggiunge l'intersezione tripla? Seguiamo un elemento che sta in tutti e tre gli insiemi: viene contato 3 volte nella prima riga, tolto 3 volte nelle intersezioni a coppie, e quindi alla fine sarebbe contato 0 volte. L'ultimo termine lo riporta a 1.
Esempio: numeri divisibili per 2, 3 o 5
Quanti numeri tra 1 e 1000 sono divisibili per almeno uno tra 2, 3 e 5?
Il numero di multipli di d tra 1 e 1000 è ⌊1000/d⌋, e un numero è divisibile per due primi distinti se e solo se è divisibile per il loro prodotto.
| Termine | Calcolo | Valore |
|---|---|---|
| |A₂| + |A₃| + |A₅| | 500 + 333 + 200 | 1033 |
| − coppie | − (166 + 100 + 66) | − 332 |
| + tripla | + ⌊1000/30⌋ | + 33 |
| Totale | 734 |
Di conseguenza i numeri tra 1 e 1000 non divisibili né per 2, né per 3, né per 5 sono 1000 − 734 = 266.
La formula generale
Per n insiemi A₁, …, Aₙ:
|A₁ ∪ … ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| − … + (−1)ⁿ⁺¹ |A₁ ∩ … ∩ Aₙ|
Le somme sono estese a tutte le scelte di 1, 2, 3, … insiemi distinti. I segni si alternano. La correttezza si dimostra osservando che un elemento che appartiene a esattamente m insiemi viene contato C(m, 1) − C(m, 2) + C(m, 3) − … volte, e questa somma alternata vale esattamente 1.
Spesso interessa il complemento, cioè gli elementi che non stanno in nessuno degli insiemi:
|nessuno| = |U| − |A₁ ∪ … ∪ Aₙ|
Applicazione: gli scombussolamenti
Uno scombussolamento (in inglese derangement) è una permutazione in cui nessun elemento resta al suo posto. Il problema classico: n persone lasciano il cappello all'ingresso e lo riprendono a caso; in quanti modi nessuno riprende il proprio?
Sia Aᵢ l'insieme delle permutazioni in cui la persona i riprende il proprio cappello. Fissare k persone al loro posto lascia (n − k)! permutazioni degli altri, e i modi di scegliere le k persone sono C(n, k). Per inclusione-esclusione, il numero di permutazioni senza punti fissi è:
Dₙ = n! − C(n,1)(n − 1)! + C(n,2)(n − 2)! − … = n! · (1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n!)
I primi valori sono D₁ = 0, D₂ = 1, D₃ = 2, D₄ = 9, D₅ = 44. La somma tra parentesi converge rapidamente a 1/e ≈ 0,3679, quindi la frazione di permutazioni senza punti fissi è circa il 36,8% già per n piccoli, e resta praticamente costante al crescere di n.
Un'applicazione concreta: in un'estrazione per uno scambio di regali, la probabilità che nessuno peschi il proprio nome è circa 0,37 indipendentemente dal numero di partecipanti. Per questo i sistemi che organizzano scambi di questo tipo non si limitano a mescolare, ma rimescolano finché non ottengono uno scombussolamento, oppure costruiscono direttamente un ciclo.
Applicazione: la funzione di Eulero
La funzione φ di Eulero conta gli interi tra 1 e n che non hanno fattori comuni con n. Se i fattori primi distinti di n sono p₁, …, pᵣ, l'inclusione-esclusione sui multipli di ciascun primo dà:
φ(n) = n · (1 − 1/p₁) · (1 − 1/p₂) · … · (1 − 1/pᵣ)
Esempio: 1000 = 2³ · 5³, quindi φ(1000) = 1000 · 1/2 · 4/5 = 400. La funzione φ è centrale nell'aritmetica modulare, perché conta gli elementi che ammettono un inverso modulo n.
Un controllo in Python
Per piccoli valori conviene sempre verificare con la forza bruta:
n = 1000
diretto = sum(1 for x in range(1, n + 1)
if x % 2 == 0 or x % 3 == 0 or x % 5 == 0)
assert diretto == 734
In sintesi
- Per due insiemi: |A ∪ B| = |A| + |B| − |A ∩ B|.
- Con più insiemi si alternano somme e sottrazioni delle intersezioni di 1, 2, 3, … insiemi.
- Spesso interessa il complemento: gli elementi che non stanno in nessun insieme.
- Circa il 37% delle permutazioni non ha punti fissi, qualunque sia n.
- La funzione di Eulero è un caso di inclusione-esclusione sui fattori primi.
