Vzorec zahrnutí-vyloučení

Vzorec inkluze-vyloučení (nebo princip inkluze-vyloučení ) je kombinatorický vzorec, který umožňuje určit mocninu sjednocení konečného počtu konečných množin , které se v obecném případě mohou vzájemně prolínat . V teorii pravděpodobnosti, analogie zahrnutí-princip vyloučení je známý jako Poincaré rovnice [1] .

Například v případě dvou sad je vzorec pro zahrnutí-vyloučení: $A,B$

$|A\pohár B|=|A|+|B|-|A\čepice B|.$

Celkem se prvky průniku berou v úvahu dvakrát a abychom to kompenzovali, odečteme z pravé strany vzorce. Platnost této úvahy je patrná z Euler-Vennova diagramu pro dvě množiny, znázorněného na obrázku vpravo. $|A|+|B|$ $A\cap B$ $|A\capB|$

Stejně tak v případě množin proces zjišťování počtu prvků svazku spočívá v zahrnutí všeho, pak vyloučení přebytku, pak zahrnutí chybně vyloučeného a tak dále, tedy střídavě zařazovat a vylučovat. Odtud pochází název vzorce. $n>2$ $A_{1}\pohár A_{2}\pohár \ldots \pohár A_{n}$

Formulace

Vzorec zahrnutí-vyloučení může být formulován v různých formách.

Z hlediska množin

Nechť jsou konečné množiny . Vzorec zahrnutí-vyloučení uvádí: $A_{1},A_{2},\ldots ,A_{n}$

${\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggl |}=\součet _{i}|A_{i}|-\součet _{i<j}|A_ {i}\cap A_{j}|+\součet _{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}|.$

V , získáme vzorec pro dvě výše uvedené množiny. $n=2$

Z hlediska vlastností

Princip inkluze-vyloučení je často uveden v následující alternativní formulaci [2] . Nechť je dána konečná množina skládající se z prvků a nechť je množina vlastností . Každý prvek sady může nebo nemusí mít některou z těchto vlastností. Označte počtem prvků, které mají vlastnosti (a možná i některé další). Označujeme také počet prvků, které nemají žádnou z vlastností . Poté se odehraje vzorec: $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})+\součet _{i< j}N(a_{i}a_{j})-\součet _{i<j<k}N(a_{i}a_{j}a_{k})+\ldots +(-1)^{n }N(a_{1}\ldots a_{n}).$

Formulace principu inkluze-vyloučení z hlediska množin je ekvivalentní formulaci z hlediska vlastností. Pokud jsou množiny podmnožinami nějaké množiny , pak na základě de Morganových pravidel (čára nad množinou je sčítání v množině ) lze vzorec pro zahrnutí a vyloučení přepsat takto: $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}|+ \součet _{i<j}|A_{i}\cap A_{j}|-\součet _{i<j<k}|A_{i}\cap A_{j}\cap A_{k}|+ \ldots +(-1)^{n}|A_{1}\cap A_{2}\cap \ldots \cap A_{n}|.$

Pokud nyní místo „ prvek patří do množiny “ řekneme „prvek má vlastnost “, pak dostaneme formulaci principu inkluze-vyloučení z hlediska vlastností a naopak. $X$ $A_{i}$ $X$ $a_{i}$

Označte počtem prvků, které mají přesně vlastnosti z množiny . Potom lze vzorec zahrnutí-vyloučení přepsat do následujícího tvaru: $N(r)$ $r$ $a_1, \ldots , a_n$

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

Důkaz

Existuje několik důkazů vzorce zahrnutí-vyloučení.

Důkaz indukcí

Vzorec inkluze-vyloučení lze dokázat indukcí [1] [3] .

Pro , vzorec zahrnutí-vyloučení je triviální: $n=1$

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

Nechť vzorec platí pro , dokažme to pro . $n=m$ $n=m+1$

Nechť každý prvek množiny může nebo nemusí mít některou z vlastností . Použijme vzorec zahrnutí-vyloučení pro vlastnosti : $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})+\součet _ {i<j\leq m}N(a_{i}a_{j})+\ldots +(-1)^{m}N(a_{1}\ldots a_{m}).$

Nyní použijeme vzorec pro vlastnosti na množinu objektů, pro které je vlastnost splněna : $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})-\součet _{i\ leq m}N(a_{i}a_{m+1})+\součet _{i<j\leq m}N(a_{i}a_{j}a_{m+1})+\ldots +( -1)^{m}N(a_{1}\ldots a_{m}a_{m+1}).$

Nakonec použijeme vzorec pro jednu vlastnost na kolekci objektů, které nemají vlastnosti : $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 }).$

Kombinací výše uvedených tří vzorců získáme vzorec zahrnutí-vyloučení pro vlastnosti . Q.E.D. ■ $m+1$ $a_{1},\ldots ,a_{m+1}$

Kombinační důkaz

Zvažte libovolný prvek a spočítejte, kolikrát je zohledněn v pravé části vzorce zahrnutí-vyloučení [2] . $e\in U$

Pokud prvek nemá žádnou z vlastností , pak se na pravé straně vzorce (v členu ) započítá přesně 1krát . $E$ $a_{i}$ $N$

Nechť prvek má přesně ty vlastnosti, řekněme . Dává 1 v těch sčítancích, pro které existuje podmnožina , a 0 pro zbytek. Počet takových podmnožin je podle definice počet kombinací . Proto je příspěvek prvku na pravou stranu $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}.$

Když je počet kombinací roven nule. Zbývající součet se na základě binomické věty rovná $s>r$

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

Pravá strana vzorce zahrnutí-vyloučení tedy bere v úvahu každý prvek, který nemá zadané vlastnosti přesně jednou, a každý prvek, který má alespoň jednu z vlastností – nulakrát. Proto se rovná počtu prvků, které nemají žádnou z vlastností , tedy . Q.E.D. ■ $a_{i}$ $N({\overline {a}}_{1}\ldots {\overline {a}}_{n})$

Důkaz pomocí indikátorových funkcí

Nechť jsou libovolné ( ne nutně konečné) množiny, které jsou podmnožinami nějaké množiny , a nechť jsou indikátorové funkce (nebo ekvivalentně vlastnosti ). $A_{i}$ $U$ $\mathbf {1} _{A_{i}}$ $A_{i}$ $a_{i}$

Indikátorová funkce jejich doplňků je ${\displaystyle {\overline {A_{i))))$

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

a indikační funkce průniku doplňků:

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

Rozbalením závorek na pravé straně a opět použitím skutečnosti, že indikátorová funkce průniku množin je rovna součinu jejich indikátorových funkcí, dostaneme:

$\mathbf {1} _{\bigcap _{i}{\overline {A_{i}}}}=1-\součet _{i}\mathbf {1} _{A_{i}}+\součet _{ i<j}\mathbf {1} _{A_{i}\cap A_{j}}-\součet _{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}}.$

Tento vztah je formou principu inkluze-vyloučení. Vyjadřuje logickou identitu [1] a platí pro libovolné množiny . V případě konečných množin (a tedy za předpokladu, že množina je konečná ), sečtením tohoto poměru přes všechny a použitím skutečnosti, že pro libovolnou podmnožinu je její mocnost rovna $A_{i}$ $A_{i}$ $U$ $x\v U$ $A\subset U$

|A|=\součet _{x\v U}\mathbf {1} _{A}(x),

získáme formulaci principu inkluze-vyloučení z hlediska kardinalit množin (nebo z hlediska vlastností). ■

Topologický důkaz

Množiny vybavíme diskrétní topologií. V tomto případě pro , a pro platí identita , V případě dvou množin a , můžeme použít Mayer-Vietorisovu přesnou posloupnost , která s uvážením zániku vyšší kohomologie bude vypadat takto: výjimky. $A_{i}$ $H^{k}(A_{i})=0$ $k>0$ $k=0$ $\dim H^{0}(A_{i})=|A_{i}|.$ $A_{1}$ $A_{2}$ $0\do H^{0}(A_{1}\pohár A_{2})\do H^{0}(A_{1})\oplus H^{0}(A_{2})\ na H^{0}(A_{1}\cap A_{2})\na 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}|,$

V případě více než dvou množin je k prokázání vzorce inkluze-vyloučení místo přesné Mayer-Vietorisovy sekvence nutné napsat nějakou spektrální sekvenci (jmenovitě Lerayovu spektrální sekvenci pro mapování projekce z disjunktního spojení k jejich spojení) a také vypočítat řady kohomologických skupin . ■ $A_{i}$

Aplikace

Problém nepokojů

Klasickým příkladem použití vzorce inkluze-vyloučení je problém poruchy [2] . Je potřeba najít počet permutací množiny tak, aby pro všechny . Takové obměny se nazývají nepokoje . $(p_{1},p_{2},\ldots ,p_{n})$ $\{1,2,\ldots ,n\}$ $p_{i}\neq i$ $i$

Nechť je množina všech permutací a vlastnost permutace nechť je vyjádřena rovností . Potom je počet poruch . Je snadné vidět, že je to počet permutací, které ponechávají prvky na místě , a proto součet obsahuje stejné členy. Vzorec zahrnutí-vyloučení poskytuje výraz pro počet poruch: $U$ $p$ $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 \vyberte 1}(n-1)!+{n \vyberte 2}(n-2)!-\ldots +(-1)^{n}{n \vyberte n }0!.$

Tento poměr lze převést do tvaru

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

Je snadné vidět, že výraz v závorkách je částečným součtem řady . S dobrou přesností je tedy počet poruch zlomkem celkového počtu permutací: $\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}=e^{-1}$ $1/e$ $P_{n}=n!$

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

Výpočet Eulerovy funkce

Dalším příkladem použití vzorce inkluze-vyloučení je nalezení explicitního výrazu pro Eulerovu funkci [4] , která vyjadřuje počet čísel od , coprime s . $\varphi (n)$ $\{1,2,\ldots ,n\}$ $n$

Nechť kanonický rozklad čísla na prvočinitele má tvar $n$

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

Číslo je coprime s tehdy a jen tehdy, když žádný z prvočíselných dělitelů nedělí . Pokud nyní vlastnost znamená, že dělí , pak počet prvočísel s je . ${\displaystyle m\in \{1,\ldots n\))$ $n$ $p_{i}$ $m$ $a_{i}$ $p_{i}$ $m$ $n$ $N({\overline {a}}_{1},\ldots ,{\overline {a}}_{k})$

Počet čísel, která mají vlastnosti , je , protože . $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\Šipka doleva p_{i_{1}}\ldots p_{i_{s}}|m$

Vzorcem inkluze-vyloučení najdeme

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

Tento vzorec je převeden do tvaru:

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

Variace a zobecnění

Princip inkluze-vyloučení pro pravděpodobnosti

Nechť je pravděpodobnostní prostor . Pak platí vzorec [1] [3] [5] pro libovolné události $(\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})-\součet _{i<j}{\mathcal {P}}(A_{i}\cap A_{j})+\součet _{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}\vpravo).

Tento vzorec vyjadřuje princip inkluze-vyloučení pro pravděpodobnosti . Lze jej získat z principu inkluze-vyloučení ve formě indikátorových funkcí:

$\mathbf {1} _{\bigcup _{i}A_{i}}=\součet _{i}\mathbf {1} _{A_{i}}-\součet _{i<j}\mathbf {1 } _{A_{i}\cap A_{j}}+\součet _{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}}.$

Nechť jsou události pravděpodobnostního prostoru , tj . Vezměme matematické očekávání obou částí tohoto poměru a pomocí linearity matematického očekávání a rovnosti pro libovolnou událost získáme vzorec inkluze-vyloučení pro pravděpodobnosti. $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}}$

Princip inkluze-vyloučení v prostorech míry

Nechť je prostor s mírou . Pak pro libovolné měřitelné množiny konečné míry platí vzorec pro inkluzi-vyloučení: $(X, {\mathfrak {S}),\mu )$ $A_{i}$ $\mu (A_{i})<\infty$

$\mu {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{i}\mu (A_{i})-\součet _{i< j}\mu (A_{i}\cap A_{j})+\součet _{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).$

Je zřejmé, že princip inkluze-vyloučení pro pravděpodobnosti a pro kardinality konečných množin jsou speciálními případy tohoto vzorce. V prvním případě je mírou přirozeně míra pravděpodobnosti v odpovídajícím pravděpodobnostním prostoru : . Ve druhém případě je mohutnost množiny brána jako míra : . $\mu (A)={\mathcal {P}} (A)$ $\mu (A)=|A|$

Princip inkluze-vyloučení pro měrné prostory lze také odvodit, stejně jako ve výše uvedených speciálních případech, z identity pro funkce indikátoru:

Nechť jsou měřitelné množiny prostoru , tj . Integrujeme obě části této rovnosti s ohledem na míru , použijeme linearitu integrálu a vztahu a získáme vzorec inkluze-vyloučení pro míru. $A_{i}$ $(X, {\mathfrak {S}),\mu )$ $A_{i}\in {\mathfrak {S))$ $\mu$ $\mu (A)=\int _{X}\mathbf {1} _{A}(x)\,d\mu$

Identita vrcholů a pádů

Vzorec zahrnutí-vyloučení lze považovat za speciální případ identity maxim a minim :

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

Tento vztah platí pro libovolná čísla . V konkrétním případě, kdy dostaneme jednu z forem principu inkluze-vyloučení. Pokud totiž dáme , kde je libovolný prvek z , pak získáme vztah pro indikátorové funkce množin: $a_{i}$ $a_{i}\in \{0,1\}$ $a_{i}=\mathbf {1} _{A_{i}}(x)$ $X$ $U$

$\mathbf {1} _{\bigcup _{i}A_{i}}(x)=\součet _{i}\mathbf {1} _{A_{i}}(x)-\součet _{i< j}\mathbf {1} _{A_{i}\cap A_{j}}(x)+\součet _{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öbiova inverze

Nechť je konečná množina a nechť je libovolná funkce definovaná na množině podmnožin a nabývající reálných hodnot. Funkci definujeme takto: $S$ $f\colon 2^{S}\to \mathbb {R}$ $S$ $g\colon 2^{S}\to \mathbb {R}$

$g(Y)=\součet _{X\supset Y}f(X).$

Pak platí následující inverzní vzorec [6] [7] :

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

Toto tvrzení je speciálním případem obecného Möbiova inverzního vzorce pro incidenční algebru ) všech podmnožin množiny částečně uspořádané inkluzní relací . $2^{S}$ $S$ $\podmnožina$

Ukažme si, jak tento vzorec implikuje princip inkluze-vyloučení pro konečné množiny. Nechť je dána rodina podmnožin konečné množiny , označme množinu indexů . Pro každou sadu indexů definujeme jako počet prvků zahrnutých pouze v těch sadách, pro které . Matematicky to lze zapsat takto: $A_{1},\ldots ,A_{n}$ $U$ $S=\{1,\ldots ,n\}$ $X\subset S$ $f(X)$ $A_{i}$ $i\in X$

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

Pak funkce definovaná vzorcem $g\colon 2^{S}\to \mathbb {R}$

g(Y)=\součet _{X\supset Y}f(X),

udává počet prvků, z nichž každý je zahrnut ve všech množinách a možná i v jiných. To znamená $A_{i}$ $i\in X$

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

Všimněte si dále, že je to počet prvků, které nemají žádnou z vlastností: $f(\varnothing )$

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

Vezmeme-li v úvahu uvedené poznámky, napíšeme Möbiův inverzní vzorec:

\left|\bigcap _{i}{\overline {A_{i}}}\right|=\součet _{X}(-1)^{|X|}\,\left|\bigcap _{i\ v X}A_{i}\vpravo|.

Toto je přesně vzorec inkluze-vyloučení pro konečné množiny, pouze nesdružuje členy související se stejnými hodnotami . $|X|$

Historie

Vzorec inkluze-vyloučení byl poprvé publikován portugalským matematikem Danielem da Silvou v roce 1854 [1] . Ale již v roce 1713 Nicholas Bernoulli použil tuto metodu k vyřešení Montmortova problému , známého jako problém setkání ( francouzsky Le problème des rencontres ) [8] , jehož zvláštním případem je problém poruchy . Také vzorec inkluze-vyloučení je spojen se jmény francouzského matematika Abrahama de Moivre a anglický matematik Joseph Sylvester [9] .

Viz také

Grassmannův vzorec
Booleova

Poznámky

↑ 1 2 3 4 5 Riordan J. Úvod do kombinatorické analýzy = Úvod do kombinatorické analýzy. - M . : Nakladatelství zahraniční literatury, 1963. - S. 63-66. — 289 s.
↑ 1 2 3 Hala M. Kombinatorická teorie. - M .: "Mir", 1970. - S. 18 -20. — 424 s.
↑ 1 2 Rybnikov K. A. Úvod do kombinatorické analýzy. - 2. vyd. - M . : Nakladatelství Moskevské státní univerzity, 1985. - S. 69-73. — 309 s.
↑ Rybnikov K. A. Úvod do kombinatorické analýzy. - 2. vyd. - M. : Nakladatelství Moskevské státní univerzity, 1985. - S. 266. - 309 s.
↑ Borovkov, A. A. Teorie pravděpodobnosti. - 2. vyd. - M .: "Nauka", 1986. - S. 24. - 431 s.
↑ Hala M. Kombinatorická teorie. - 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 na webu Wolfram MathWorld .
↑ Rybnikov K. A. Úvod do kombinatorické analýzy. - 2. vyd. - M. : Nakladatelství Moskevské státní univerzity, 1985. - S. 264. - 309 s.

Literatura

Riordan J. Úvod do kombinatorické analýzy = An Introduction to Combinatorial Analysis. - M . : Nakladatelství zahraniční literatury, 1963. - 289 s.
Rybnikov K. A. Úvod do kombinatorické analýzy. - 2. vyd. - M. : Nakladatelství Moskevské státní univerzity, 1985. - 309 s.
Stanley R. Enumerative Combinatorics = Enumerative Combinatorics. — M .: Mir, 1990. — 440 s.
Hala M. Kombinatorická teorie. - M .: Mir, 1970. - 424 s.
I. Yaglom. Záplaty na kaftanu // Kvant . - 1974. - č. 2 . - S. 13-21 .

Odkazy

Weisstein, Eric W. Inclusion-Exclusion Principle (anglicky) na webových stránkách Wolfram MathWorld .