Sisällytys-poissulkemiskaava

Inkluusio-poissulkemiskaava (tai inkluusio-poissulkemisperiaate ) on kombinatorinen kaava, jonka avulla voit määrittää äärellisen määrän äärellisten joukkojen liiton teho , jotka yleensä voivat leikata toistensa kanssa. Todennäköisyysteoriassa inkluusio-poissulkemisperiaatteen analogi tunnetaan Poincarén kaavana [1] .

Esimerkiksi kahden joukon tapauksessa sisällyttämisen ja poissulkemisen kaava on: $A, B$

$|A\cup B|=|A|+|B|-|A\cap B|.$

Yhteensä leikkauselementit otetaan huomioon kahdesti, ja tämän kompensoimiseksi vähennämme kaavan oikealta puolelta. Tämän päättelyn pätevyys voidaan nähdä Euler-Venn-kaaviosta kahdelle joukolle, joka on esitetty oikealla olevassa kuvassa. $|A|+|B|$ $A\kansi B$ $|A\capB|$

Samalla tavalla joukkojen tapauksessa liiton elementtien lukumäärän löytäminen koostuu kaiken sisällyttämisestä, sitten ylimääräisen poissulkemisesta, sitten virheellisesti poissuljetun sisällyttämisestä ja niin edelleen, toisin sanoen vuorotellen sisällyttämisestä ja poissulkemisesta. Tästä kaavan nimi tulee. $n>2$ $A_{1}\kuppi A_{2}\kuppi \ldots \cup A_{n}$

Sanamuoto

Inkluusio-poissulkemiskaava voidaan formuloida eri muodoissa.

Sarjojen suhteen

Olkoon äärellisiä joukkoja . Sisällytys-poissulkemiskaava sanoo: $A_{1},A_{2},\ldots ,A_{n}$

${\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggl |}=\sum _{i}|A_{i}|-\sum _{i<j}|A_ {i}\cap A_{j}|+\sum _{i<j<k}|A_{i}\cap A_{j}\cap A_{k}|-\ldots +(-1)^{n -1}|A_{1}\cap A_{2}\cap \ldots \cap A_{n}|.$

Osoitteessa , saamme kaavan kahdelle edellä esitetylle joukolle. $n = 2$

Ominaisuuksien suhteen

Sisällytys-poissulkemisperiaate esitetään usein seuraavassa vaihtoehtoisessa muotoilussa [2] . Olkoon alkioista koostuva äärellinen joukko annettu ja olkoon joukko ominaisuuksia . Jokaisella joukon elementillä voi olla tai ei ole mitään näistä ominaisuuksista. Merkitään niiden elementtien lukumäärällä, joilla on ominaisuuksia (ja ehkä joitain muita). Merkitään myös niiden elementtien lukumäärä, joilla ei ole mitään ominaisuuksia . Sitten kaava tapahtuu: $U$ $N$ $a_1, \ldots , a_n$ $U$ $N(a_{i_{1))\ldots a_{i_{s)))$ $a_{i_{1}},\ldots ,a_{i_{s}}$ $N({\overline {a}}_{i_{1}}\ldots {\overline {a}}_{i_{s}})$ $a_{i_{1}},\ldots ,a_{i_{s}}$

$N({\overline {a}}_{1}\ldots {\overline {a}}_{n})=N-\sum _{i}N(a_{i})+\sum _{i< j}N(a_{i}a_{j})-\summa _{i<j<k}N(a_{i}a_{j}a_{k})+\lpisteet +(-1)^{n }N(a_{1}\ldots a_{n}).$

Sisällytys-poissulkemisperiaatteen muotoilu joukoissa vastaa formulaatiota ominaisuuksien suhteen. Itse asiassa, jos joukot ovat jonkin joukon osajoukkoja , niin de Morganin sääntöjen nojalla (joukon yli oleva rivi on lisäys joukossa ), sisällyttäminen-poissulkemiskaava voidaan kirjoittaa uudelleen seuraavasti: $A_{i}$ $U$ $|\bigcup \nolimits _{i}A_{i}|=|U|-|\bigcap \nolimits _{i}{\overline {A_{i}}}|$ $U$

${\biggl |}\bigcap _{i=1}^{n}{\overline {A_{i))}{\biggl |}=|U|-\sum _{i}|A_{i}|+ \sum _{i<j}|A_{i}\cap A_{j}|-\sum _{i<j<k}|A_{i}\cap A_{j}\cap A_{k}|+ \ldots +(-1)^{n}|A_{1}\cap A_{2}\cap \ldots \cap A_{n}|.$

Jos nyt " elementti kuuluu joukkoon " sijasta sanotaan "elementillä on ominaisuus ", niin saadaan ominaisuuksien mukaanotto-poissulkemisperiaatteen muotoilu ja päinvastoin. $x$ $A_{i}$ $x$ $a_{i}$

Merkitään niiden elementtien lukumäärällä, joilla on täsmälleen joukon ominaisuudet . Sitten sisällyttäminen-poissulkemiskaava voidaan kirjoittaa uudelleen seuraavaan muotoon: $N(r)$ $r$ $a_1, \ldots , a_n$

$N(0)=\summa _{k=0}^{n}(-1)^{k}\summa _{i_{1}<\ldots <i_{k}}N(i_{1},\ ldots ,i_{k}).$

Todiste

Sisällytä-poissulkemiskaavasta on useita todisteita.

Todistus induktiolla

Inkluusio-poissulkemiskaava voidaan todistaa induktiolla [1] [3] .

Sisällytyksen ja poissulkemisen kaava on triviaali: $n = 1$

$N({\overline {a)))=NN(a).$

Olkoon kaava totta , todistetaan se . $n=m$ ${\näyttötyyli n=m+1}$

Olkoon jokaisella joukon elementillä jokin ominaisuuksista tai ei . Sovelletaan sisällyttäminen-poissulkemiskaavaa ominaisuuksiin : $U$ ${\displaystyle a_{1},\ldots ,a_{m},a_{m+1))$ ${\displaystyle a_{1},\ldots ,a_{m))$

$N({\overline {a}}_{1}\ldots {\overline {a}}_{m})=N-\sum _{i\leq m}N(a_{i})+\sum _ {i<j\leq m}N(a_{i}a_{j})+\ldots +(-1)^{m}N(a_{1}\ldots a_{m}).$

Nyt sovelletaan ominaisuuksien kaavaa objektijoukkoon , jolle ominaisuus täyttyy : $a_{1},\ldots ,a_{m}$ $N(a_{m+1})$ $a_{m+1}$

$N({\overline {a}}_{1}\ldots {\overline {a}}_{m}a_{m+1})=N(a_{m+1})-\sum _{i\ leq m}N(a_{i}a_{m+1})+\sum _{i<j\leq m}N(a_{i}a_{j}a_{m+1})+\ldots +( -1)^{m}N(a_{1}\ldots a_{m}a_{m+1}).$

Lopuksi käytämme yhden ominaisuuden kaavaa kokoelmaan objekteja, joilla ei ole ominaisuuksia : $a_{m+1}$ $N({\overline {a}}_{1}\ldots {\overline {a}}_{m})$ $a_{1},\ldots ,a_{m}$

$N({\overline {a}}_{1}\ldots {\overline {a}}_{m}{\overline {a}}_{m+1})=N({\overline {a}} _{1}\ldots {\overline {a}}_{m})-N({\overline {a}}_{1}\ldots {\overline {a}}_{m}a_{m+1 }).$

Yhdistämällä yllä olevat kolme kaavaa saadaan ominaisuuksien sisällyttäminen-poissulkemiskaava . Q.E.D. ■ $m+1$ $a_{1},\ldots ,a_{m+1}$

Kombinatorinen todiste

Tarkastellaan mielivaltaista elementtiä ja lasketaan, kuinka monta kertaa se otetaan huomioon sisällyttäminen-poissulkemiskaavan oikeanpuoleisessa osassa [2] . $e\in U$

Jos elementillä ei ole mitään ominaisuuksista , se lasketaan tasan 1 kerran kaavan oikealla puolella (jäsenessä ). $e$ $a_{i}$ $N$

Olkoon elementillä täsmälleen samat ominaisuudet, esimerkiksi . Se antaa 1 niissä summads , joille on osajoukko , ja 0 loput. Tällaisten osajoukkojen määrä on määritelmän mukaan yhdistelmien lukumäärä . Siksi elementin panos oikealle puolelle on $e$ $r$ $a_{j_{1}},\ldots ,a_{j_{r}}$ $\sum \nolimits _{i_{1}<\ldots <i_{s}}N(a_{i_{1}},\ldots ,a_{i_{s}})$ $\{i_{1},\ldots ,i_{s}\}$ $\{j_{1},\ldots ,j_{r}\}$ ${\tbinom {r}{s))$ $e$

$1-{r \choose 1}+{r \choose 2}-\ldots +(-1)^{r}{r \choose r}.$

Kun yhdistelmien lukumäärä on nolla. Jäljelle jäävä summa on binomilauseen mukaan yhtä suuri kuin $s>r$

$\sum _{s=0}^{r}(-1)^{s}{r \choose s}={\bigg (}1+(-1){\bigg )}^{r}=0.$

Siten sisällyttäminen-poissulkemiskaavan oikea puoli ottaa huomioon jokaisen elementin, jolla ei ole määritettyjä ominaisuuksia tarkalleen kerran, ja jokaisen elementin, jolla on vähintään yksi ominaisuuksista - nolla kertaa. Siksi se on yhtä suuri kuin niiden elementtien lukumäärä, joilla ei ole mitään ominaisuuksia , eli . Q.E.D. ■ $a_{i}$ $N({\overline {a}}_{1}\ldots {\overline {a}}_{n})$

Todistus ilmaisintoimintojen kautta

Antaa olla mielivaltaisia ( ei välttämättä äärellisiä) joukkoja, jotka ovat joidenkin joukon osajoukkoja , ja anna olla indikaattorifunktioita (tai vastaavasti ominaisuuksia ). $A_{i}$ $U$ $\mathbf {1} _{A_{i}}$ $A_{i}$ $a_{i}$

Niiden komplementtien indikaattoritoiminto on ${\displaystyle {\overline {A_{i))))$

$\mathbf {1} _{\overline {A_{i}}}=1-\mathbf {1} _{A_{i}},$

ja komplementtien leikkauspisteen indikaattorifunktio :

$\mathbf {1} _{\cap _{i}{\overline {A_{i}}}}=\prod _{i}(1-\mathbf {1} _{A_{i}}).$

Laajennamalla oikeanpuoleisia sulkuja ja käyttämällä jälleen kerran sitä tosiasiaa, että joukkojen leikkauspisteen indikaattorifunktio on yhtä suuri kuin niiden indikaattoritoimintojen tulo, saamme:

$\mathbf {1} _{\bigcap _{i}{\overline {A_{i}}}}=1-\sum _{i}\mathbf {1} _{A_{i}}+\sum _{ i<j}\mathbf {1} _{A_{i}\cap A_{j}}-\sum _{i<j<k}\mathbf {1} _{A_{i}\cap A_{j} \cap A_{k}}+\ldots +(-1)^{n}\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}.$

Tämä suhde on yksi sisällyttäminen-poissulkemisperiaatteen muoto. Se ilmaisee loogisen identiteetin [1] ja pätee mielivaltaisille joukoille . Äärillisten joukkojen tapauksessa (ja vastaavasti olettaen, että joukko on äärellinen ) laskemalla tämä suhde yhteen ja käyttämällä sitä tosiasiaa, että mielivaltaiselle osajoukolle sen teho on yhtä suuri kuin $A_{i}$ $A_{i}$ $U$ $x\in U$ $A\subset U$

|A|=\summa _{x\in U}\mathbf {1} _{A}(x),

saamme inkluusio-poissulkemisperiaatteen muotoilun joukkojen kardinaalisuuden (tai ominaisuuksien) suhteen. ■

Topologinen todiste

Varustamme joukot erillisellä topologialla. Tässä tapauksessa for , ja for , identiteetti pätee Kahden joukon ja tapauksessa voidaan käyttää Mayer-Vietoriksen tarkkaa sekvenssiä , joka, kun otetaan huomioon korkeamman kohemologian katoaminen, näyttää tältä: poikkeukset. $A_{i}$ $H^{k}(A_{i})=0$ $k>0$ $k = 0$ $\dim H^{0}(A_{i})=|A_{i}|.$ $A_{1}$ $A_{2}$ $0\to H^{0}(A_{1}\cup A_{2})\to H^{0}(A_{1})\oplus H^{0}(A_{2})\ H^{0}(A_{1}\cap A_{2})\to 0.$ $\dim H^{0}(A_{1})\oplus H^{0}(A_{2})=\dim H^{0}(A_{1}\cup A_{2})+ \dim H^{0}(A_{1}\cap A_{2}),$ $|A_{1}|+|A_{2}|=|A_{1}\cup A_{2}|+|A_{1}\cap A_{2}|,$

Enemmän kuin kahden joukon tapauksessa inkluusio-poissulkemiskaavan todistamiseksi tarkan Mayer-Vietoris-sekvenssin sijasta on kirjoitettava jokin spektrisekvenssi (eli Leray-spektrisekvenssi projektion kartoittamiseksi hajaliitosta liittoonsa) ja laske myös kohomologiaryhmien rivit . ■ $A_{i}$

Sovellus

Mellakkaongelma

Klassinen esimerkki inkluusio-poissulkemiskaavan käytöstä on häiriöongelma [2] . On löydettävä joukon permutaatioiden määrä siten , että kaikille . Tällaisia permutaatioita kutsutaan mellakoiksi . $(p_{1},p_{2},\ldots ,p_{n})$ $\{1,2,\ldots ,n\}$ $p_{i}\neq i$ $i$

Olkoon kaikkien permutaatioiden joukko ja olkoon permutaatioominaisuus ilmaistava tasa-arvolla . Silloin häiriöiden määrä on . On helppo nähdä, että se on permutaatioiden lukumäärä, jotka jättävät elementit paikoilleen , ja näin ollen summa sisältää samat ehdot. Inkluusio-poissulkemiskaava antaa lausekkeen häiriöiden lukumäärälle: $U$ $s$ $a_{i}$ $p_{i}=i$ $N({\overline {a}}_{1},{\overline {a}}_{2},\ldots ,{\overline {a}}_{n})$ $N(a_{i_{1}},\ldots ,a_{i_{s}})=(ns)!$ $i_{1},\ldots,i_{s}$ $\sum N(a_{i_{1}},a_{i_{2}},\ldots ,a_{i_{s}})$ ${\tbinom {n}{s))$ $D_{n}$

$D_{n}=n!-{n \choose 1}(n-1)!+{n \choose 2}(n-2)!-\ldots +(-1)^{n}{n \choose n }0!.$

Tämä suhde voidaan muuntaa muotoon

$D_{n}=n!\left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-\ldots +{\frac {(-1)^{n }}{n!}}\oikea).$

On helppo nähdä, että suluissa oleva lauseke on sarjan osasumma . Siten hyvällä tarkkuudella häiriöiden määrä on murto-osa permutaatioiden kokonaismäärästä: $\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}=e^{-1}$ $1/e$ $P_{n}=n!$

$D_{n}/P_{n}\noin 1/e.$

Euler-funktion laskenta

Toinen esimerkki inkluusio-poissulkemiskaavan soveltamisesta on eksplisiittisen lausekkeen löytäminen Euler-funktiolle [4] , joka ilmaisee numeroiden lukumäärän kohteesta , koprime kanssa . $\varphi (n)$ $\{1,2,\ldots ,n\}$ $n$

Olkoon luvun kanonisella hajotelmalla alkutekijöiksi muoto $n$

$n=p_{1}^{s_{1}}p_{2}^{s_{2}}\ldots p_{k}^{s_{k}}.$

Luku on koprimi, jos ja vain jos mikään alkuluku ei jakaa . Jos nyt ominaisuus tarkoittaa, että se jakaa , niin koprime-lukujen määrä on . ${\displaystyle m\in \{1,\ldots n\))$ $n$ $p_{i}$ $m$ $a_{i}$ $p_{i}$ $m$ $n$ $N({\overline {a}}_{1},\ldots ,{\overline {a}}_{k})$

Ominaisuuksia sisältävien numeroiden määrä on , koska . $N(a_{i_{1}},\ldots ,a_{i_{s}})$ $a_{i_{1}},\ldots ,a_{i_{s}}$ $n/p_{i_{1}}\ldots p_{i_{s}}$ $p_{i_{1}}|m,\ldots ,p_{i_{s}}|m\Leftrightarrow p_{i_{1}}\ldots p_{i_{s}}|m$

Sisällytys-poissulkemiskaavalla löydämme

$\varphi (n)=n-\sum _{i}n/p_{i}+\sum _{i,j}n/p_{i}p_{j}-\ldots +(-1)^{k }n/p_{1}\ldots p_{k}.$

Tämä kaava muunnetaan muotoon:

$\varphi (n)=n\prod _{i=1}^{k}\left(1-{\frac {1}{p_{i}}}\oikea).$

Muunnelmia ja yleistyksiä

Todennäköisyyksien sisällyttäminen-poissulkemisperiaate

Antaa olla todennäköisyysavaruus . Tällöin kaava [1] [3] [5] pätee mielivaltaisille tapahtumille $(\Omega ,{\mathfrak {F)),{\mathcal {P)))$ $A_{1},A_{2},\ldots ,A_{n}$

{\mathcal {P}}{\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{i}{\mathcal {P}}(A_{ i})-\sum _{i<j}{\mathcal {P}}(A_{i}\cap A_{j})+\sum _{i<j<k}{\mathcal {P}}( A_{i}\cap A_{j}\cap A_{k})+\ldots +(-1)^{n-1}\,{\mathcal {P}}\left(\bigcap _{i=1 }^{n}A_{i}\oikea).

Tämä kaava ilmaisee todennäköisyyksien sisällyttämis-poissulkemisperiaatteen . Se voidaan saada inkluusio-poissulkemisperiaatteesta indikaattorifunktioiden muodossa:

$\mathbf {1} _{\bigcup _{i}A_{i}}=\sum _{i}\mathbf {1} _{A_{i}}-\sum _{i<j}\mathbf {1 } _{A_{i}\cap A_{j}}+\sum _{i<j<k}\mathbf {1} _{A_{i}\cap A_{j}\cap A_{k}}+ \ldots +(-1)^{n-1}\,\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}.$

Olkoon todennäköisyysavaruuden tapahtumia , eli . Otetaan tämän suhteen molempien osien matemaattinen odotus ja käyttämällä matemaattisen odotuksen lineaarisuutta ja yhtäläisyyttä mielivaltaiselle tapahtumalle , saadaan todennäköisyyksien sisällyttäminen-poissulkemiskaava. $A_{i}$ $(\Omega ,{\mathfrak {F)),{\mathcal {P)))$ $A_{i}\in {\mathfrak {F}}$ ${\mathcal {M}}$ ${\mathcal {P}}(A)={\mathcal {M}}(\mathbf {1} _{A})$ $A\in {\mathfrak {F}}$

Inkluusio-poissulkemisperiaate mittaavaruudessa

Antaa olla tila toimenpiteellä . Sitten mielivaltaisille mitattavissa oleville äärellisen suuren joukoille inkluusio-poissulkemiskaava pätee: $(X,{\mathfrak {S}),\mu )$ $A_{i}$ $\mu (A_{i})<\infty$

$\mu {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{i}\mu (A_{i})-\sum _{i< j}\mu (A_{i}\cap A_{j})+\sum _{i<j<k}\mu (A_{i}\cap A_{j}\cap A_{k})+\ldots +(-1)^{n-1}\,\mu \left(\bigcap _{i=1}^{n}A_{i}\oikea).$

Ilmeisesti sisällyttäminen-poissulkemisperiaate todennäköisyyksien ja äärellisten joukkojen kardinaliteettien osalta ovat tämän kaavan erikoistapauksia. Ensimmäisessä tapauksessa mitta on luonnollisesti todennäköisyysmitta vastaavassa todennäköisyysavaruudessa : . Toisessa tapauksessa joukon kardinaalisuus otetaan mittana : . $\mu (A)={\mathcal {P}}(A)$ $\mu (A)=|A|$

Mittatilojen sisällyttäminen-poissulkemisperiaate voidaan myös johtaa, kuten yllä olevissa erikoistapauksissa, indikaattoritoimintojen identiteetistä:

Olkoon avaruuden mitattavia joukkoja , eli . Integroimme tämän yhtälön molemmat osat suhteessa suureen , käytämme integraalin ja suhteen lineaarisuutta ja hankimme suurelle sisällyttäminen-poissulkemiskaavan. $A_{i}$ $(X,{\mathfrak {S}),\mu )$ $A_{i}\in {\mathfrak {S))$ $\mu$ $\mu (A)=\int _{X}\mathbf {1} _{A}(x)\,d\mu$

Ylä- ja alamäet

Sisällytys-poissulkemiskaavaa voidaan pitää erikoistapauksena maksimien ja minimien identtisyydestä :

\max(a_{1},\ldots ,a_{n})=\sum _{i}a_{i}-\sum _{i<j}\min(a_{i},a_{j})+ \ldots +(-1)^{n-1}\,\min(a_{1},\ldots ,a_{n}).

Tämä suhde pätee mielivaltaisille luvuille . Tietyssä tapauksessa, kun saamme yhden sisällyttäminen-poissulkemisperiaatteen muodoista. Todellakin, jos laitamme , jossa on mielivaltainen alkio kohdasta , niin saadaan relaatio joukkojen indikaattorifunktioille: $a_{i}$ $a_{i}\in \{0,1\}$ $a_{i}=\mathbf {1} _{A_{i}}(x)$ $x$ $U$

$\mathbf {1} _{\bigcup _{i}A_{i}}(x)=\sum _{i}\mathbf {1} _{A_{i}}(x)-\sum _{i< j}\mathbf {1} _{A_{i}\cap A_{j}}(x)+\sum _{i<j<k}\mathbf {1} _{A_{i}\cap A_{j }\cap A_{k}}(x)+\ldots +(-1)^{n-1}\,\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}( x).$

Möbius inversio

Antaa olla äärellinen joukko, ja antaa olla mielivaltainen funktio, joka on määritelty osajoukkojen joukolle ja ottaa todellisia arvoja. Määrittelemme funktion seuraavasti: $S$ $f\colon 2^{S}\to \mathbb {R}$ $S$ $g\colon 2^{S}\to \mathbb {R}$

$g(Y)=\summa _{X\supset Y}f(X).$

Sitten seuraava inversiokaava pätee [6] [7] :

f(Y)=\summa _{X\supset Y}(-1)^{|X|-|Y|}\,g(X).

Tämä lauseke on yleisen Möbiuksen inversiokaavan erikoistapaus insidenssialgebralle joukon kaikkien osajoukkojen joukolle, joka on osittain järjestetty inkluusiorelaatiolla . $2^{S}$ $S$ $\osajoukko$

Osoittakaamme, kuinka tämä kaava sisältää inkluusio-poissulkemisperiaatteen äärellisille joukoille. Olkoon äärellisen joukon osajoukkojen perhe annettu , merkitse indeksien joukkoa . Jokaiselle indeksijoukolle määritämme elementtien lukumäärän, jotka sisältyvät vain niihin ryhmiin , joille . Matemaattisesti tämä voidaan kirjoittaa näin: $A_{1},\ldots ,A_{n}$ $U$ $S=\{1,\ldots ,n\}$ $X\subset S$ $f(X)$ $A_{i}$ $i\in X$

$f(X)=\left|\left(\bigcap _{i\in X}A_{i}\right)\cap \left(\bigcap _{j\notin X}{\overline {A_{j)) }\oikea)\oikea|.$

Sitten kaavan määrittelemä funktio $g\colon 2^{S}\to \mathbb {R}$

g(Y)=\summa _{X\supset Y}f(X),

antaa elementtien lukumäärän, joista jokainen sisältyy kaikkiin ryhmiin ja ehkä muihinkin joukkoihin. Tuo on $A_{i}$ $i\in X$

g(X)=\left|\bigcap _{i\in X}A_{i}\oikea|.

Huomaa lisäksi, että se on niiden elementtien lukumäärä, joilla ei ole mitään ominaisuuksia: $f(\varnothing )$

f(\varnothing )=\left|\bigcap _{i}{\overline {A_{i))}\oikea|.

Ottaen huomioon tehdyt huomautukset, kirjoitamme Möbiuksen inversiokaavan:

\left|\bigcap _{i}{\overline {A_{i}}}\right|=\sum _{X}(-1)^{|X|}\,\left|\bigcap _{i\ kohdassa X}A_{i}\right|.

Tämä on täsmälleen sisällyttäminen-poissulkemiskaava äärellisille joukoille, mutta se ei ryhmittele samoihin arvoihin liittyviä termejä . $|X|$

Historia

Inkluusio-poissulkemiskaavan julkaisi ensimmäisen kerran portugalilainen matemaatikko Daniel da Silva vuonna 1854 [1] . Mutta jo vuonna 1713 Nicholas Bernoulli käytti tätä menetelmää Montmortin ongelman ratkaisemiseen , joka tunnetaan kokousongelmana ( ranska: Le problème des rencontres ) [8] , josta häiriöongelma on erikoistapaus . Myös inkluusio-poissulkemiskaava liittyy ranskalaisen matemaatikon Abraham de Moivren nimiin ja englantilainen matemaatikko Joseph Sylvester [9] .

Katso myös

Grassmannin kaava
Boolen

Muistiinpanot

↑ 1 2 3 4 5 Riordan J. Johdatus kombinatoriseen analyysiin = An Introduction to Combinatorial Analysis. - M . : Ulkomaisen kirjallisuuden kustantamo, 1963. - S. 63-66. — 289 s.
↑ 1 2 3 Hall M. Kombinatorinen teoria. - M . : "Mir", 1970. - S. 18-20 . — 424 s.
↑ 1 2 Rybnikov K. A. Johdatus kombinatoriseen analyysiin. - 2. painos - M . : Moskovan valtionyliopiston kustantamo, 1985. - S. 69-73. — 309 s.
↑ Rybnikov K. A. Johdatus kombinatoriseen analyysiin. - 2. painos - M .: Moskovan valtionyliopiston kustantamo, 1985. - S. 266. - 309 s.
↑ Borovkov, A. A. Todennäköisyysteoria. - 2. painos - M . : "Nauka", 1986. - S. 24. - 431 s.
↑ Hall M. Kombinatorinen teoria. - M . : "Mir", 1970. - S. 30 -31. — 424 s.
↑ Stanley R. Enumerative Combinatorics = Enumerative Combinatorics. - M .: "Mir", 1990. - S. 103-107. - 440 s.
↑ Weisstein , Eric W. Derangement Wolfram MathWorld -verkkosivustolla .
↑ Rybnikov K. A. Johdatus kombinatoriseen analyysiin. - 2. painos - M .: Moskovan valtionyliopiston kustantamo, 1985. - S. 264. - 309 s.

Kirjallisuus

Riordan J. Johdatus kombinatoriseen analyysiin = An Introduction to Combinatorial Analysis. - M . : Ulkomaisen kirjallisuuden kustantaja, 1963. - 289 s.
Rybnikov K. A. Johdatus kombinatoriseen analyysiin. - 2. painos - M. : Moskovan valtionyliopiston kustantamo, 1985. - 309 s.
Stanley R. Enumerative Combinatorics = Enumerative Combinatorics. - M .: Mir, 1990. - 440 s.
Hall M. Kombinatorinen teoria. - M . : Mir, 1970. - 424 s.
I. Yaglom. Laikkuja kaftaanissa // Kvant . - 1974. - Nro 2 . - S. 13-21 .

Linkit

Weisstein, Eric W. Inclusion-Exclusion Principle (englanniksi) Wolfram MathWorld -verkkosivustolla .