Visa källa för Principen om inklusion/exklusion

I [[kombinatorik]]en ger '''principen om inklusion/exklusion''' ett sätt att räkna antalet element i en [[Union (matematik)|union]] av flera [[mängd]]er. 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|exempel]] nedan.

Pricipen säger att om <math>A_1 \ldots A_n</math> är [[ändlig]]a [[mängd]]er så gäller att:

:<math>\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|</math><math>+\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|</math>
där <math>|A_n|\qquad</math> är antalet element i mängden <math>A_n\qquad</math>.

== Specialfall ==
[[Fil:Inclusion-exclusion.png|thumb|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.
:<math>| A \cup B | = |A| + |B| - | A \cap B | </math>

===n=3===
Har man tre mängder blir [[Kemisk formel|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''.
:<math>\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|</math>

== Allmänna fallet ==
Den ''k'':te delsumman av typen <math>\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|</math> har <math>n \choose k</math> element (antalet sätt att välja ut ''k'' stycken index från totalt ''n'' möjligheter).

== Exempel ==
=== Problem ===
Hur många [[permutation]]er av [[Svenska alfabetet|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 <math>|U| - |A\cup B\cup C|</math>.
:<math>|U| = 29! \quad</math> (totala antalet permutationer av 29 bokstäver)

:<math>|A| = 26!\quad</math> (antalet permutationer av "'''FISK'''" och 25 andra symboler)
:<math>|B| = 26!\quad</math> (antalet permutationer av "'''SKAL'''" och 25 andra symboler)
:<math>|C| = 27!\quad</math> (antalet permutationer av "'''LAX'''" och 26 andra symboler)

:<math>|A\cap B| = 24!\quad</math> (antalet permutationer av "'''FISKAL'''" och 23 andra symboler)
:<math>|A\cap C| = 24!\quad</math> (antalet permutationer av "'''FISK'''", "'''LAX'''" och 22 andra symboler)
:<math>|B\cap C| = 0\quad</math> (finns inga permutationer som uppfyller båda mönstren)

:<math>|A\cap B\cap C| = 0\quad</math> (finns heller inte här några möjligheter)

Svaret blir alltså <math>29! - 27! - 2\cdot 26!  + 2\cdot 24! \qquad</math>.

== Referenser ==
* Lars-Christer Böiers, ''Diskret matematik'', Studentlitteratur 2003. {{ISBN|91-44-03102-5}}

== Se även ==
* [[Permutation]]
* [[Kombinatorik]]
{{DEFAULTSORT:Principen om inklusion exklusion}}<!-- ingen accent -->

[[Kategori:Kombinatorik]]