Eksklusjonsproblemer

Eksklusjonsproblemer er en klasse av telleproblemer innen kombinatorikk og sannsynlighet der målet er å telle objekter som tilhører minst én av flere overlappende grupper, samtidig som man unngår å telle enkelte objekter flere ganger. Slike problemer løses ofte med prinsippet om inklusjon og eksklusjon, som gir en nøyaktig måte å telle unionen av overlappende sett på.

For to sett A og B gir prinsippet formelen |A ∪ B| = |A| + |B| - |A ∩ B|. For tre sett A, B og C blir det |A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|. Generelt, for n sett A1, A2, ..., An: |∪_{i=1}^n Ai| = ∑|Ai| - ∑|Ai∩Aj| + ∑|Ai∩Aj∩Ak| - ... + (-1)^{n+1} |A1∩...∩An|.

Et eksempel: Si at 70 personer har egenskap A og 60 har egenskap B, hvor 20 har begge egenskapene. Antallet som har minst én av egenskapene er 70 + 60 - 20 = 110.

Prinsippet generaliseres til flere sett og brukes også i sannsynlighetsberegninger, der man beregner sannsynligheten for at minst én av hendelsene skjer. Det finnes også variasjoner for kontinuerlige eller uendelige samlinger, og for beregning av antall objekter med visse krav i databaser og grafteori. Eksklusjonsproblemer understreker behovet for å vurdere og korrigere for overintroduksjon og overlapp mellom kategorier når man teller.