inklusjonseksklusjons

Inklusjonseksklusjonsprinsippet, eller inklusjon–eksklusjon-prinsippet, er et grunnleggende verktøy i sannsynlighet, kombinatorikk og mengdelære. Det brukes til å beregne størrelsen på unionen av flere mengder når disse opptrer overlappende, slik at overtelling ikke kompenseres feil.

For to mengder A og B gjelder:

|A ∪ B| = |A| + |B| − |A ∩ B|.

For tre mengder A, B og C:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Generelt, for n mengder A1, A2, ..., An:

|∪_{i=1}^n A_i| = Σ|A_i| − Σ|A_i ∩ A_j| + Σ|A_i ∩ A_j ∩ A_k| − ... + (−1)^{n+1} |A_1 ∩ ... ∩ A_n|.

Denne mønsteret fortsetter med påvirkning fra høyereordens snitt.

Formålet er å korrigere for overtelling som oppstår når overlapping mellom mengder ikke er disjunkte. Kardinalitetsformlene gir en presis måte å telle felles elementer på uten å telle dem flere ganger.

Anvendelser inkluderer telling av objekter i felles sett, beregning av størrelsen på unioner i graf- og nettverksproblemer, og i sannsynlighet for å finne sannsynligheten for at minst ett av en samling hendelser inntreffer:

P(A1 ∪ ... ∪ An) = ΣP(A_i) − ΣP(A_i ∩ A_j) + ...

Historisk ble prinsippet utviklet og popularisert på 1800-tallet, ofte tilknyttet Thomas de Morgan og senere implementert i kombinatorikk og sannsynlighet. I dag er det en standard teknikk i både teori og praksis, og det finnes generaliseringer for uendelige familier og målte rom.