Principen om inklusion/exklusion

Från Wikipedia
Hoppa till: navigering, sök

I kombinatoriken ger principen 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[redigera | redigera wikitext]

Inklusion/exklusion med tre mängder

n=2[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

Problem[redigera | redigera wikitext]

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

Lösning[redigera | redigera wikitext]

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| = 28! \quad (totala antalet permutationer av 28 bokstäver)
|A| = 25!\quad (antalet permutationer av "FISK" och 24 andra symboler)
|B| = 25!\quad (antalet permutationer av "SKAL" och 24 andra symboler)
|C| = 26!\quad (antalet permutationer av "LAX" och 25 andra symboler)
|A\cap B| = 23!\quad (antalet permutationer av "FISKAL" och 22 andra symboler)
|A\cap C| = 23!\quad (antalet permutationer av "FISK", "LAX" och 21 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å 28! - 26! - 2\cdot 25!  + 2\cdot 23! \qquad.

Referenser[redigera | redigera wikitext]

Se även[redigera | redigera wikitext]