De ce contează?
Vrei să numeri elevii din clasă care fac sport SAU muzică. Aduni cei 18 sportivi cu cei 12 muzicieni și obții 30 — dar în clasă sunt doar 25 de elevi. De unde diferența? Cei 5 care fac AMÂNDOUĂ au fost numărați de două ori: o dată la sportivi, o dată la muzicieni. Ca să repari, scazi exact acea suprapunere: 18 + 12 - 5 = 25. Acesta este, în esență, tot principiul includerii și excluderii.
Intuiția
Când vrei să numeri câte elemente sunt în cel puțin una dintre mai multe grupe, prima reacție e să aduni mărimile grupelor. Problema: orice element care apare în două grupe e numărat de două ori, unul din trei grupe e numărat de trei ori, și așa mai departe. Principiul includerii și excluderii (PIE) e rețeta exactă prin care corectezi supranumărarea: aduni grupele, scazi suprapunerile de câte două, adaugi la loc suprapunerile de câte trei, alternând semnele.
Vreau să număr câte numere de la 1 la N sunt divizibile cu 2 SAU cu 3. Cel mai simplu: număr multiplii de 2 și adun multiplii de 3.
Numerele divizibile cu AMÂNDOI (adică multiplii de 6: 6, 12, 18...) apar și în prima listă, și în a doua. Le-am numărat de două ori. Suma simplă supranumără exact suprapunerea — rezultatul iese prea mare.
Principiul includerii și excluderii repară supranumărarea cu un termen de
corecție: |A ∪ B| = |A| + |B| - |A ∩ B|. Pentru k mulțimi alternez semnele —
aduni mărimile câte una, scazi intersecțiile câte două, aduni intersecțiile câte
trei, și tot așa. Semnul unei intersecții de j mulțimi este (-1)^(j+1).
Aplici formula cu semne alternate. Pe k mulțimi, parcurgi toate cele 2^k
submulțimi nevide: pentru fiecare calculezi mărimea intersecției și o adaugi cu
semnul (-1)^(numar de multimi + 1). Tehnica e des combinată cu enumerarea
submulțimilor prin bitmask.