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}\ldots 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}\left|A_{i}\cap A_{j}\right|$$+\sum _{i,j,k\,:\,i<j<k}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \cdots \ \pm \left|A_{1}\cap \cdots \cap A_{n}\right|$

där $|A_{n}|\qquad$ är antalet element i mängden $A_{n}\qquad$.

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.

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

Allmänna fallet

Den k:te delsumman av typen $\sum _{i_{1},i_{2},\ldots ,i_{k}\,:\,i_{1}<i_{2}<\ldots <i_{k}}\left|A_{i_{1}}\cap A_{i_{2}}\cap \ldots \cap A_{i_{k}}\right|$ har $n \choose 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!\quad$ (totala antalet permutationer av 29 bokstäver)

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

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

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

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

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

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

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

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

Referenser

• Lars-Christer Böiers, Diskret matematik, Studentlitteratur 2003. ISBN 91-44-03102-5

Se även

• Permutation
• Kombinatorik