Formel för inkludering-uteslutning

Inklusions-exkluderingsformeln (eller inkluderings-exkluderingsprincipen ) är en kombinatorisk formel som låter dig bestämma styrkan av unionen av ett ändligt antal ändliga mängder , som i det allmänna fallet kan skära varandra. I sannolikhetsteorin är en analog till principen om inkludering och uteslutning känd som Poincaré -formeln [1] .

Till exempel, i fallet med två uppsättningar, är inkluderings-exkluderingsformeln: $A,B$

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

Totalt beaktas skärningselementen två gånger, och för att kompensera för detta subtraherar vi från formelns högra sida. Giltigheten av detta resonemang kan ses från Euler-Venn-diagrammet för två uppsättningar, som visas i figuren till höger. $|A|+|B|$ $A\cap B$ $|A\capB|$

På samma sätt, när det gäller uppsättningar, består processen att hitta antalet element i föreningen i att inkludera allt, sedan exkludera överskottet, sedan inkludera det felaktigt uteslutna, och så vidare, det vill säga växelvis inkludera och exkludera. Det är här namnet på formeln kommer ifrån. $n>2$ $A_{1}\cup A_{2}\cup \ldots \cup A_{n}$

Formulering

Inklusions-exkluderingsformeln kan formuleras i olika former.

När det gäller set

Låt vara ändliga mängder . Formeln för inkludering och uteslutning säger: $A_{1},A_{2},\ldots ,A_{n}$

${\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggl |}=\summa _{i}|A_{i}|-\summa _{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}|.$

Vid får vi formeln för två uppsättningar ovan. $n=2$

När det gäller egenskaper

Principen om inkludering och uteslutning ges ofta i följande alternativa formulering [2] . Låt en ändlig mängd som består av element ges, och låt det finnas en mängd egenskaper . Varje element i uppsättningen kan ha någon av dessa egenskaper eller inte. Beteckna med antalet element som har egenskaper (och kanske några andra). Vi anger också antalet element som inte har någon av egenskaperna . Sedan sker formeln: $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-\summa _{i}N(a_{i})+\summa _{i< j}N(a_{i}a_{j})-\sum _{i<j<k}N(a_{i}a_{j}a_{k})+\ldots +(-1)^{n }N(a_{1}\ldots a_{n}).$

Formuleringen av inklusions-exkluderingsprincipen i termer av mängder är likvärdig med formuleringen i termer av egenskaper. Faktum är att om mängder är delmängder av någon uppsättning , då, i kraft av de Morgans regler (en rad över en mängd är ett tillägg i en mängd ), kan inkluderings-exkluderingsformeln skrivas om enligt följande: $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|-\summa _{i}|A_{i}|+ \sum _{i<j}|A_{i}\cap A_{j}|-\summa _{i<j<k}|A_{i}\cap A_{j}\cap A_{k}|+ \ldots +(-1)^{n}|A_{1}\cap A_{2}\cap \ldots \cap A_{n}|.$

Om vi nu istället för " ett element tillhör en mängd " säger "ett element har en egenskap ", så får vi formuleringen av principen om inkludering-uteslutning i termer av egenskaper, och vice versa. $x$ $A_{i}$ $x$ $a_{i}$

Beteckna med antalet element som har exakt egenskaperna från uppsättningen . Sedan kan inkluderings-exkluderingsformeln skrivas om i följande form: $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}).$

Bevis

Det finns flera bevis för inkluderings-exkluderingsformeln.

Bevis genom induktion

Inklusions-exkluderingsformeln kan bevisas genom induktion [1] [3] .

För inkluderings-exkluderingsformeln är trivial: $n=1$

$N({\överlinje {a)))=NN(a).$

Låt formeln vara sann för , låt oss bevisa det för . $n=m$ $n=m+1$

Låt varje element i uppsättningen ha eller inte ha någon av egenskaperna . Låt oss tillämpa inkluderings-exkluderingsformeln för egenskaper : $U$ ${\displaystyle a_{1},\ldots ,a_{m},a_{m+1))$ ${\displaystyle a_{1},\ldots ,a_{m))$

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

Nu tillämpar vi formeln för egenskaper på den uppsättning objekt för vilka egenskapen är uppfylld : $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})-\summa _{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}).$

Slutligen tillämpar vi formeln för en enskild egenskap på en samling objekt som inte har egenskaper : $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 }).$

Genom att kombinera ovanstående tre formler får vi inkluderings-exkluderingsformeln för egenskaper . Q.E.D. ■ $m+1$ $a_{1},\ldots ,a_{m+1}$

Kombinatoriskt bevis

Betrakta ett godtyckligt element och beräkna hur många gånger det beaktas i den högra delen av inklusions-exkluderingsformeln [2] . $e\in U$

Om elementet inte har någon av egenskaperna räknas det exakt 1 gång på höger sida av formeln (i medlemmen ). $e$ $a_{i}$ $N$

Låt ett element ha exakt egenskaperna, säg . Det ger 1 i de summeringar för vilka det finns en delmängd och 0 för resten. Antalet sådana delmängder är per definition antalet kombinationer . Därför är elementets bidrag till höger sida $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}.$

När antalet kombinationer är lika med noll. Den återstående summan, i kraft av binomialsatsen, är lika med $s>r$

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

Således tar den högra sidan av inkluderings-exkluderingsformeln hänsyn till varje element som inte har de angivna egenskaperna exakt en gång, och varje element som har minst en av egenskaperna - noll gånger. Därför är det lika med antalet element som inte har någon av egenskaperna , det vill säga . Q.E.D. ■ $a_{i}$ $N({\overline {a}}_{1}\ldots {\overline {a}}_{n})$

Bevis via indikatorfunktioner

Låt vara godtyckliga ( inte nödvändigtvis ändliga) uppsättningar som är delmängder av någon uppsättning , och låt vara indikatorfunktioner (eller motsvarande egenskaper hos ). $A_{i}$ $U$ $\mathbf {1} _{A_{i}}$ $A_{i}$ $a_{i}$

Indikatorfunktionen för deras komplement är ${\displaystyle {\overline {A_{i)))))$

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

och indikatorfunktionen för skärningspunkten mellan komplement:

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

Genom att expandera parentesen på höger sida och återigen använda det faktum att indikatorfunktionen för skärningspunkten av uppsättningar är lika med produkten av deras indikatorfunktioner, får vi:

$\mathbf {1} _{\bigcap _{i}{\overline {A_{i}}}}=1-\summa _{i}\mathbf {1} _{A_{i}}+\summa _{ 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}}.$

Detta förhållande är en form av principen om inkludering och uteslutning. Det uttrycker en logisk identitet [1] och är sant för godtyckliga uppsättningar . När det gäller ändliga mängder (och följaktligen under antagandet att mängden är ändlig ), summera detta förhållande över allt och använda det faktum att för en godtycklig delmängd är dess makt lika med $A_{i}$ $A_{i}$ $U$ $x\i U$ $A\subset U$

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

vi får en formulering av inkluderings-exkluderingsprincipen i termer av kardinaliteter av mängder (eller i termer av egenskaper). ■

Topologiska bevis

Vi utrustar uppsättningarna med en diskret topologi. I det här fallet gäller identiteten för , och för . I fallet med två uppsättningar och , kan vi använda Mayer-Vietoris exakta sekvens , som, med hänsyn till försvinnandet av högre kohomologi, kommer att se ut som: $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})\ till H^{0}(A_{1}\cap A_{2})\till 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}|,$

I fallet med fler än två uppsättningar, för att bevisa inklusions-exkluderingsformeln, istället för den exakta Mayer-Vietoris-sekvensen, måste man skriva någon spektralsekvens (nämligen Leray-spektralsekvensen för att kartlägga projektionen från en disjunkt union till deras fackförening), och även beräkna raden av kohomologigrupper . ■ $A_{i}$

Applikation

Upploppsproblemet

Ett klassiskt exempel på att använda inklusions-exkluderingsformeln är störningsproblemet [2] . Det krävs för att hitta antalet permutationer i uppsättningen så att för alla . Sådana permutationer kallas upplopp . $(p_{1},p_{2},\ldots,p_{n})$ $\{1,2,\ldots ,n\}$ $p_{i}\neq i$ $i$

Låt vara mängden av alla permutationer och låt permutationsegenskapen uttryckas av likheten . Då är antalet störningar . Det är lätt att se att det är antalet permutationer som lämnar elementen på plats , och därmed innehåller summan samma termer. Inklusions-exkluderingsformeln ger ett uttryck för antalet störningar: $U$ $sid$ $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}$ $\summa N(a_{i_{1}},a_{i_{2}},\ldots ,a_{i_{s}})$ ${\tbinom {n}{s))$ $D_{n}$

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

Detta förhållande kan konverteras till formuläret

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

Det är lätt att se att uttrycket inom parentes är en delsumma av serien . Således, med god noggrannhet, är antalet störningar en bråkdel av det totala antalet permutationer: $\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}=e^{-1}$ $1/e$ $P_{n}=n!$

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

Beräkning av Euler-funktionen

Ett annat exempel på att tillämpa inklusions-exkluderingsformeln är att hitta ett explicit uttryck för Euler-funktionen [4] , som uttrycker antalet tal från , coprime med . $\varphi (n)$ $\{1,2,\ldots ,n\}$ $n$

Låt den kanoniska uppdelningen av ett tal till primtalsfaktorer ha formen $n$

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

Ett tal är coprime med om och endast om ingen av primtalsdivisorerna delar sig . Om nu egenskapen betyder att den delar sig så är antalet samprimtal med . $m\in \{1,\ldots n\}$ $n$ $pi}$ $m$ $a_{i}$ $pi}$ $m$ $n$ $N({\overline {a}}_{1},\ldots,{\overline {a}}_{k})$

Antalet tal som har egenskaper är , eftersom . $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$

Genom inkluderings-exkluderingsformeln finner vi

$\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}.$

Denna formel konverteras till formen:

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

Variationer och generaliseringar

Inklusions-exkluderingsprincipen för sannolikheter

Låt vara ett sannolikhetsutrymme . Då är formeln [1] [3] [5] giltig för godtyckliga händelser $(\Omega ,{\mathfrak {F)),{\mathcal {P)))$ $A_{1},A_{2},\ldots ,A_{n}$

{\mathcal {P}}{\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\summa _{i}{\mathcal {P}}(A_{ i})-\summa _{i<j}{\mathcal {P}}(A_{i}\cap A_{j})+\summa _{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}\höger).

Denna formel uttrycker principen om inkludering och uteslutning för sannolikheter . Den kan erhållas från principen om inkludering och uteslutning i form av indikatorfunktioner:

$\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}}.$

Låta vara händelser av sannolikhetsutrymmet , dvs. Låt oss ta den matematiska förväntan av båda delarna av detta förhållande, och genom att använda linjäriteten hos den matematiska förväntan och jämlikhet för en godtycklig händelse får vi inkluderings-exkluderingsformeln för sannolikheter. $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}}$

Inklusions-exkluderingsprincipen i måttutrymmen

Låt vara ett mellanslag med mått . Sedan gäller för godtyckliga mätbara uppsättningar av ändliga mått inkluderings-exkluderingsformeln: $(X,{\mathfrak {S}),\mu )$ $A_{i}$ $\mu (A_{i})<\infty$

$\mu {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\summa _{i}\mu (A_{i})-\summa _{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}\right).$

Uppenbarligen är inklusions-exkluderingsprincipen för sannolikheter och för kardinaliteter av finita mängder specialfall av denna formel. I det första fallet är måttet naturligtvis ett sannolikhetsmått i motsvarande sannolikhetsutrymme : . I det andra fallet tas uppsättningens kardinalitet som ett mått : . $\mu (A)={\mathcal {P}}(A)$ $\mu (A)=|A|$

Inklusions-uteslutningsprincipen för måttutrymmen kan också härledas, som för ovanstående specialfall, från identiteten för indikatorfunktioner:

Låt vara mätbara uppsättningar av utrymmet , dvs. Vi integrerar båda delarna av denna likhet med avseende på måttet , använder linjäriteten hos integralen och relationen och erhåller inkluderings-exkluderingsformeln för måttet. $A_{i}$ $(X,{\mathfrak {S}),\mu )$ $A_{i}\in {\mathfrak {S))$ $\mu$ $\mu (A)=\int _{X}\mathbf {1} _{A}(x)\,d\mu$

Identitet för toppar och dalar

Inklusions-exkluderingsformeln kan betraktas som ett specialfall av identiteten av maxima och minima :

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

Denna relation är giltig för godtyckliga tal . I ett särskilt fall, när vi får en av formerna för inkludering-uteslutningsprincipen. Faktum är att om vi sätter , var är ett godtyckligt element från , så får vi förhållandet för indikatorfunktioner för mängder: $a_{i}$ $a_{i}\in \{0,1\}$ $a_{i}=\mathbf {1} _{A_{i}}(x)$ $x$ $U$

$\mathbf {1} _{\bigcup _{i}A_{i}}(x)=\summa _{i}\mathbf {1} _{A_{i}}(x)-\summa _{i< j}\mathbf {1} _{A_{i}\cap A_{j}}(x)+\summa _{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 inversion

Låt vara en ändlig mängd, och låt vara en godtycklig funktion som definieras på en uppsättning delmängder och tar reella värden. Vi definierar funktionen på följande sätt: $S$ $f\colon 2^{S}\to \mathbb {R}$ $S$ $g\colon 2^{S}\to \mathbb {R}$

$g(Y)=\summa _{X\uppsättning Y}f(X).$

Då gäller följande inversionsformel [6] [7] :

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

Detta påstående är ett specialfall av den allmänna Möbius-inversionsformeln för incidensalgebra av mängden av alla delmängder av en mängd som delvis är ordnad av inklusionsrelationen . $2^{S}$ $S$ $\delmängd$

Låt oss visa hur denna formel antyder principen om inkludering och uteslutning för ändliga mängder. Låt en familj av delmängder av en finit mängd ges , beteckna mängden index . För varje uppsättning index definierar vi som antalet element som endast ingår i de uppsättningar för vilka . Matematiskt kan detta skrivas som: $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)) }\höger)\höger|.$

Sedan funktionen som definieras av formeln $g\colon 2^{S}\to \mathbb {R}$

g(Y)=\summa _{X\uppsättning Y}f(X),

ger antalet element, som var och en ingår i alla uppsättningar , och kanske i andra. Det är $A_{i}$ $i\in X$

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

Observera vidare att det är antalet element som inte har någon av egenskaperna: $f(\varnothing )$

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

Med hänsyn till de anmärkningar som gjorts, skriver vi Möbius-inversionsformeln:

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

Detta är exakt inkluderings-exkluderingsformeln för ändliga mängder, bara den grupperar inte termer som är relaterade till samma värden . $|X|$

Historik

Inklusions-uteslutningsformeln publicerades först av den portugisiske matematikern Daniel da Silva 1854 [1] . Men redan 1713 använde Nicholas Bernoulli denna metod för att lösa Montmort , känt som mötesproblemet ( franska: Le problème des rencontres ) [8] , av vilket störningsproblemet är ett specialfall . Dessutom är inkluderings-exkluderingsformeln associerad med namnen på den franske matematikern Abraham de Moivre och den engelske matematikern Joseph Sylvester [9] .

Se även

Grassmann formel
Booles

Anteckningar

↑ 1 2 3 4 5 Riordan J. Introduction to Combinatorial Analysis = An Introduction to Combinatorial Analysis. - M . : Förlag för utländsk litteratur, 1963. - S. 63-66. — 289 sid.
↑ 1 2 3 Hall M. Combinatorial Theory. - M . : "Mir", 1970. - S. 18 -20. — 424 sid.
↑ 1 2 Rybnikov K. A. Introduktion till kombinatorisk analys. - 2:a uppl. - M . : Publishing House of Moscow State University, 1985. - S. 69-73. — 309 sid.
↑ Rybnikov K. A. Introduktion till kombinatorisk analys. - 2:a uppl. - M. : Publishing House of Moscow State University, 1985. - S. 266. - 309 sid.
↑ Borovkov, A. A. Sannolikhetsteori. - 2:a uppl. - M . : "Nauka", 1986. - S. 24. - 431 sid.
↑ Hall M. Combinatorial Theory. - M . : "Mir", 1970. - S. 30 -31. — 424 sid.
↑ Stanley R. Enumerative Combinatorics = Enumerative Combinatorics. - M . : "Mir", 1990. - S. 103-107. — 440 s.
↑ Weisstein, Eric W. Derangement på Wolfram MathWorld -webbplatsen .
↑ Rybnikov K. A. Introduktion till kombinatorisk analys. - 2:a uppl. - M. : Publishing House of Moscow State University, 1985. - S. 264. - 309 sid.

Litteratur

Riordan J. Introduction to Combinatorial Analysis = An Introduction to Combinatorial Analysis. - M . : Publishing House of Foreign Literature, 1963. - 289 sid.
Rybnikov K. A. Introduktion till kombinatorisk analys. - 2:a uppl. - M. : Moscow State Universitys förlag, 1985. - 309 s.
Stanley R. Enumerative Combinatorics = Enumerative Combinatorics. — M .: Mir, 1990. — 440 sid.
Hall M. Kombinatorisk teori. - M . : Mir, 1970. - 424 sid.
I. Yaglom. Plåster på kaftanen // Kvant . - 1974. - Nr 2 . - S. 13-21 .

Länkar

Weisstein, Eric W. Inclusion-Exclusion Principle (engelska) på Wolfram MathWorlds webbplats .