Principen om inklusion/exklusion

Från Rilpedia

Texten från svenska Wikipedia

I kombinatoriken ger pricipen om inklusion/exklusion ett sätt att räkna antalet element i en union av flera mängder. Pricipen ä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).