Inklusions-eksklusionsprincip i kombinatorik: Beregning af sætstørrelse med lethed

Inklusions-udelukkelsesprincippet er en teknik, der bruges i kombinatorik til at beregne størrelsen af et s
t ved at opdele det i mindre delm
ngder og t
lle deres sk
ringspunkt. Det er baseret på ideen om, at hvis vi har to m
ngder, A og B, og vi vil t
lle de elementer, der er i begge m
ngder, kan vi gøre det ved at tr
kke de elementer, der kun er i A fra det samlede antal elementer i A, og tilføj derefter de elementer, der kun er i B.

Mere formelt, lad A og B v
re to s
t, og lad |A| v
re antallet af elementer i A. Så siger inklusion-udelukkelsesprincippet, at:

|A ∪ B| = |A| + |B| - |A ∩ B|

where |A ∪ B| er antallet af elementer i foreningen af A og B, og |A ∩ B| er antallet af elementer, der er i både A og B.

Idéen bag denne formel er, at vi kan beregne størrelsen af foreningen af to m
ngder ved først at t
lle antallet af elementer i hvert s
t separat, og derefter tr
kke de elementer ud, der er kun i et af s
ttene (dvs. elementerne i krydset). Dette giver os det samlede antal elementer i foreningen, som er summen af antallet af elementer i hver m
ngde minus antallet af elementer, der kun er i et af m
ngderne. Lad os f.eks. sige, at vi har to m
ngder: A = {1, 2, 3} og B = {4, 5, 6}. For at beregne størrelsen af deres forening ved hj
lp af inklusion-udelukkelsesprincippet t
ller vi først antallet af elementer i hvert s
t separat:

|A| = 3
|B| = 3

Dern
st beregner vi antallet af elementer, der er i begge m
ngder ved at t
lle deres sk
ringspunkt:

|A ∩ B| = 2 (da 1 og 2 er i begge m
ngder)

Nu kan vi bruge inklusions-udelukkelsesprincippet til at beregne størrelsen af foreningen:

|A ∪ B| = |A| + |B| - |A ∩ B|
= 3 + 3 - 2
= 6

Så, størrelsen af foreningen af A og B er 6.

Inklusions-udelukkelsesprincippet har mange anvendelser i kombinatorik, såsom at t
lle antallet af permutationer, kombinationer og løsninger til ligninger. Det er et kraftfuldt v
rktøj til at løse t
lleproblemer og kan bruges til at forenkle komplekse beregninger.