Principen om inklusion/exklusion

I kombinatoriken ger principen om inklusion/exklusion ett sätt att räkna antalet element i en union av flera mängder. Principen är av stor nytta i många kombinatoriska problem, där man genom att införa rätt mängder kan reducera problemet till att beräkna antalet element i en union; se exempel nedan.

Pricipen säger att om $A_1\dots A_n$ är ändliga mängder så gäller att:

$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{i=1}^n\left|A_i\right|-\sum _{i,j:i<j}|A_i\cap A_j|$$+\sum _{i,j,k:i<j<k}|A_i\cap A_j\cap A_k|-\cdots \cdots \pm |A_1\cap \cdots \cap A_n|$

där $|A_n|$ är antalet element i mängden $A_n$.

Specialfall

Inklusion/exklusion med tre mängder

n=2

Då det bara finns två mängder och man vill ha reda på antalet element i unionen av dessa mängder, summerar man först antalet element i dessa båda mängder. Nu har man räknat vissa element dubbelt, nämligen alla element som finns i båda mängderna och man måste därför subtrahera antalet element som finns i båda mängderna.

$|A\cup B|=|A|+|B|-|A\cap B|$

n=3

Har man tre mängder blir formeln lite mer komplicerad. Först summeras antalet element i de tre mängderna, varvid flertalet element räknas flera gånger. Subtraheras alla element som finns i två av mängderna blir det bättre, men antalet element som finns i alla tre mängderna måste läggas till för att få rätt svar. Se figur.

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

Allmänna fallet

Den k:te delsumman av typen $\sum _{i_1,i_2,\dots ,i_k:i_1<i_2<\dots <i_k}|A_{i_1}\cap A_{i_2}\cap \dots \cap A_{i_k}|$ har $(\genfrac{}{}{0ex}{}{n}{k})$ element (antalet sätt att välja ut k stycken index från totalt n möjligheter).

Exempel

Problem

Hur många permutationer av alfabetets 29 bokstäver innehåller inte något av mönstren FISK, SKAL eller LAX?

Lösning

Inför följande mängder:

U = {alla permutationer av alfabetet}

A = {alla permutationer som innehåller "FISK"}

B = {alla permutationer som innehåller "SKAL"}

C = {alla permutationer som innehåller "LAX"}

Vi söker $|U|-|A\cup B\cup C|$.

$|U|=29!$ (totala antalet permutationer av 29 bokstäver)

$|A|=26!$ (antalet permutationer av "FISK" och 25 andra symboler)

$|B|=26!$ (antalet permutationer av "SKAL" och 25 andra symboler)

$|C|=27!$ (antalet permutationer av "LAX" och 26 andra symboler)

$|A\cap B|=24!$ (antalet permutationer av "FISKAL" och 23 andra symboler)

$|A\cap C|=24!$ (antalet permutationer av "FISK", "LAX" och 22 andra symboler)

$|B\cap C|=0$ (finns inga permutationer som uppfyller båda mönstren)

$|A\cap B\cap C|=0$ (finns heller inte här några möjligheter)

Svaret blir alltså $29!-27!-2\cdot 26!+2\cdot 24!$.

Referenser

• Lars-Christer Böiers, Diskret matematik, Studentlitteratur 2003. Mall:ISBN

Se även

• Permutation
• Kombinatorik