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. 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 är ändliga mängder så gäller att:

där är antalet element i mängden .

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.

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.

Allmänna fallet[redigera | redigera wikitext]

Den k:te delsumman av typen har 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 29 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 .

(totala antalet permutationer av 29 bokstäver)
(antalet permutationer av "FISK" och 25 andra symboler)
(antalet permutationer av "SKAL" och 25 andra symboler)
(antalet permutationer av "LAX" och 26 andra symboler)
(antalet permutationer av "FISKAL" och 23 andra symboler)
(antalet permutationer av "FISK", "LAX" och 22 andra symboler)
(finns inga permutationer som uppfyller båda mönstren)
(finns heller inte här några möjligheter)

Svaret blir alltså .

Referenser[redigera | redigera wikitext]

Se även[redigera | redigera wikitext]