Principen om inklusion/exklusion
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 är ändliga mängder så gäller att:
där är antalet element i mängden
.
Innehåll |
[redigera] Specialfall
[redigera] 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.
[redigera] 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.
[redigera] Allmänna fallet
Den k:te delsumman av typen har
element (antalet sätt att välja ut k stycken index från totalt n möjligheter).
[redigera] Exempel
[redigera] Problem
Hur många permutationer av alfabetets 28 bokstäver innehåller inte något av mönstren FISK, SKAL eller LAX?
[redigera] Lösning
Inför följande mängder:
- U = {alla permutationer}
- 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 28 bokstäver)
(antalet permutationer av "FISK" och 24 andra symboler)
(antalet permutationer av "SKAL" och 24 andra symboler)
(antalet permutationer av "LAX" och 25 andra symboler)
(antalet permutationer av "FISKAL" och 22 andra symboler)
(antalet permutationer av "FISK", "LAX" och 21 andra symboler)
(finns inga permutationer som uppfyller båda mönstren)
(finns heller inte här några möjligheter)
Svaret blir alltså .
[redigera] Referenser
- Lars-Christer Böiers, Diskret matematik, Studentlitteratur 2003. ISBN 91-44-03102-5