Sisällön ja poissulkemisen periaate kombinatoriikassa: Sarjan koon laskeminen helposti

Inkluusio-poissulkemisperiaate on tekniikka, jota käytetään kombinatoriikassa joukon koon laskemiseen jakamalla se pienempiin osajoukkoon ja laskemalla niiden leikkauspisteet. Se perustuu ajatukseen, että jos meillä on kaksi joukkoa, A ja B, ja haluamme laskea elementit, jotka ovat molemmissa joukoissa, voimme tehdä sen vähentämällä alkiot, jotka ovat vain A:ssa joukon alkioiden kokonaismäärästä. A, ja sitten lisäämällä takaisin ne alkiot, jotka ovat vain B:ssä.

Muaalisesti, olkoon A ja B kaksi joukkoa, ja olkoon |A| on A:n elementtien lukumäärä. Sitten sisällyttäminen-poissulkemisperiaate sanoo, että:

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

missä |A ∪ B| on elementtien lukumäärä A:n ja B:n liitossa ja |A ∩ B| on sekä A:ssa että B:ssä olevien alkioiden määrä.

Tämän kaavan ideana on, että voimme laskea kahden joukon liiton koon laskemalla ensin kunkin joukon elementtien lukumäärän erikseen ja vähentämällä sitten alkiot, jotka ovat vain yhdessä joukosta (eli leikkauspisteen elementit). Tämä antaa meille liiton elementtien kokonaismäärän, joka on kunkin joukon alkioiden lukumäärän summa vähennettynä niiden alkioiden lukumäärällä, jotka ovat vain yhdessä joukosta.

Oletetaan esimerkiksi, että meillä on kaksi joukkoa: A = {1, 2, 3} ja B = {4, 5, 6}. Laskeaksemme niiden liiton koon sisällyttäminen-poissulkemisperiaatteella laskemme ensin kunkin joukon elementtien lukumäärän erikseen:

|A| = 3
|B| = 3

Seuraavaksi lasketaan molemmissa joukoissa olevien alkioiden lukumäärä laskemalla niiden leikkauspisteet:

|A ∩ B| = 2 (koska 1 ja 2 ovat molemmissa joukoissa)

Voimme nyt käyttää inkluusio-poissulkemisperiaatetta liiton koon laskemiseen:

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

Eli A:n ja B:n liiton koko on 6.

Inkluusio-poissulkemisperiaatteella on monia sovelluksia kombinatoriikassa, kuten permutaatioiden, yhdistelmien ja ratkaisujen laskeminen yhtälöihin. Se on tehokas työkalu laskentaongelmien ratkaisemiseen ja sitä voidaan käyttää monimutkaisten laskelmien yksinkertaistamiseen.