Formula de includere-excludere

Formula de includere-excludere (sau principiul de includere-excludere ) este o formulă combinatorie care vă permite să determinați puterea uniunii unui număr finit de mulțimi finite , care, în cazul general, se pot intersecta între ele. În teoria probabilității, un analog al principiului de includere-excludere este cunoscut sub numele de formula Poincaré [1] .

De exemplu, în cazul a două seturi, formula de includere-excludere este: $A,B$

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

În total , elementele de intersecție sunt luate în considerare de două ori, iar pentru a compensa acest lucru, scădem din partea dreaptă a formulei. Valabilitatea acestui raționament poate fi văzută din diagrama Euler-Venn pentru două mulțimi, prezentată în figura din dreapta. $|A|+|B|$ $A\cap B$ $|A\capB|$

La fel, în cazul mulţimilor, procesul de aflare a numărului de elemente ale unirii constă în a include totul, apoi excluderea excesului, apoi includerea excludelor în mod eronat, şi aşa mai departe, adică alternativ includerea şi excluderea. De aici provine numele formulei. $n>2$ $A_{1}\cup A_{2}\cup \ldots \cup A_{n}$

Formulare

Formula de includere-excludere poate fi formulată în diferite forme.

În ceea ce privește seturile

Fie mulțimi finite . Formula de includere-excludere spune: $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}|.$

La , obținem formula pentru două mulțimi date mai sus. $n=2$

În ceea ce privește proprietățile

Principiul includerii-excluderii este adesea dat în următoarea formulare alternativă [2] . Să fie dată o mulțime finită constând din elemente și să fie o mulțime de proprietăți . Fiecare element al setului poate avea sau nu oricare dintre aceste proprietăți. Indicați prin numărul de elemente care au proprietăți (și, poate, unele altele). De asemenea, notăm numărul de elemente care nu au nicio proprietate . Apoi are loc formula: $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})-\sum _{i<j<k}N(a_{i}a_{j}a_{k})+\ldots +(-1)^{n }N(a_{1}\ldots a_{n}).$

Formularea principiului de includere-excludere în termeni de mulțimi este echivalentă cu formularea în termeni de proprietăți. Într-adevăr, dacă mulțimile sunt submulțimi ale unei mulțimi , atunci, în virtutea regulilor lui de Morgan (o linie peste o mulțime este o adăugare într-o mulțime ), formula de includere-excludere poate fi rescrisă după cum urmează: $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}|.$

Dacă acum în loc de „ un element aparține unei mulțimi ” spunem „un element are o proprietate ”, atunci obținem formularea principiului includerii-excluderii în termeni de proprietăți și invers. $X$ $A_{i}$ $X$ $a_{i}$

Notează prin numărul de elemente care au exact proprietățile din mulțime . Apoi formula de includere-excludere poate fi rescrisă în următoarea formă: $N(r)$ $r$ $a_1, \ldots , a_n$

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

Dovada

Există mai multe dovezi ale formulei de includere-excludere.

Dovada prin inducție

Formula de includere-excludere poate fi demonstrată prin inducție [1] [3] .

Pentru , formula de includere-excludere este trivială: $n=1$

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

Fie ca formula să fie adevărată pentru , haideți să o demonstrăm pentru . $n=m$ $n=m+1$

Fie ca fiecare element al multimii poate avea sau nu oricare dintre proprietati . Să aplicăm formula de includere-excludere pentru proprietăți : $U$ $a_{1},\ldots ,a_{m},a_{m+1)$ $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}).$

Acum aplicăm formula proprietăților setului de obiecte pentru care proprietatea este satisfăcută : $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}).$

În cele din urmă, aplicăm formula pentru o singură proprietate unei colecții de obiecte care nu au proprietăți : $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 }).$

Combinând cele trei formule de mai sus, obținem formula de includere-excludere pentru proprietăți . Q.E.D. ■ $m+1$ $a_{1},\ldots ,a_{m+1}$

Dovada combinatorie

Luați în considerare un element arbitrar și calculați de câte ori este luat în considerare în partea dreaptă a formulei de includere-excludere [2] . $e\in U$

Dacă elementul nu are niciuna dintre proprietăți , atunci este numărat exact o dată în partea dreaptă a formulei (în membru ). $e$ $a_{i}$ $N$

Fie ca un element să aibă exact proprietățile, să zicem . Oferă 1 în acele sume pentru care există o submulțime și 0 pentru restul. Numărul de astfel de submulțimi este, prin definiție, numărul de combinații . Prin urmare, contribuția elementului în partea dreaptă este $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 \alegeți 1}+{r \alegeți 2}-\ldots +(-1)^{r}{r \alegeți r}.$

Când numărul de combinații este egal cu zero. Suma rămasă, în virtutea teoremei binomului, este egală cu $s>r$

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

Astfel, partea dreaptă a formulei de includere-excludere ia în considerare fiecare element care nu are proprietățile specificate exact o dată și fiecare element care are cel puțin una dintre proprietăți - de zero ori. Prin urmare, este egal cu numărul de elemente care nu au niciuna dintre proprietățile , adică . Q.E.D. ■ $a_{i}$ $N({\overline {a}}_{1}\ldots {\overline {a}}_{n})$

Dovada prin funcții indicator

Fie mulțimi arbitrare ( nu neapărat finite) care sunt submulțimi ale unei mulțimi și fie funcții indicator (sau, în mod echivalent, proprietăți ale lui ). $A_{i}$ $U$ $\mathbf {1} _{A_{i}}$ $A_{i}$ $a_{i}$

Funcția de indicator a complementelor lor este ${\overline {A_{i)})$

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

și funcția indicator a intersecției complementelor:

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

Expandând parantezele din partea dreaptă și folosind din nou faptul că funcția indicator a intersecției mulțimilor este egală cu produsul funcțiilor lor indicator, obținem:

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

Această relație este o formă a principiului de includere-excludere. Exprimă o identitate logică [1] și este adevărată pentru mulțimi arbitrare . În cazul mulțimilor finite (și, în consecință, în ipoteza că mulțimea este finită ), însumând acest raport peste tot și folosind faptul că pentru o submulțime arbitrară puterea sa este egală cu $A_{i}$ $A_{i}$ $U$ $x\în U$ $A\subset U$

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

obţinem o formulare a principiului de includere-excludere în termeni de cardinalităţi ale mulţimilor (sau în termeni de proprietăţi). ■

Dovada topologică

Înzestrăm mulțimile cu o topologie discretă. În acest caz, pentru , și pentru , identitatea este valabilă .În cazul a două mulțimi și , putem folosi șirul exact Mayer-Vietoris , care, ținând cont de dispariția coomologiei superioare, va arăta ca: $A_{i}$ $H^{k}(A_{i})=0$ $k>0$ $k=0$ $\dim H^{0}(A_{i})=|A_{i}|.$ $A_{1}$ $A_{2}$ $0\la H^{0}(A_{1}\cup A_{2})\la H^{0}(A_{1})\oplus H^{0}(A_{2})\ la H^{0}(A_{1}\cap A_{2})\la 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}|,$

În cazul a mai mult de două mulțimi, pentru a demonstra formula de includere-excludere, în loc de secvența exactă Mayer-Vietoris, trebuie să scrieți o secvență spectrală (și anume , secvența spectrală Leray pentru maparea proiecției dintr-o uniune disjunctă ). la unirea lor) și, de asemenea, calculați rangurile grupurilor de coomologie. ■ $A_{i}$

Aplicație

Problema revoltei

Un exemplu clasic de utilizare a formulei de includere-excludere este problema tulburării [2] . Este necesar să se găsească numărul de permutări ale mulțimii astfel încât pentru toate . Astfel de permutări sunt numite revolte . $(p_{1},p_{2},\ldots,p_{n})$ $\{1,2,\ldots ,n\}$ $p_{i}\neq i$ $i$

Fie mulțimea tuturor permutărilor și fie proprietatea permutării să fie exprimată prin egalitate . Atunci numărul perturbărilor este de . Este ușor de observat că este numărul de permutări care lasă elementele pe loc și astfel suma conține aceiași termeni. Formula de includere-excludere oferă o expresie pentru numărul de perturbări: $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 \alegeți 1}(n-1)!+{n \alegeți 2}(n-2)!-\ldots +(-1)^{n}{n \alegeți n }0!.$

Acest raport poate fi convertit în formă

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

Este ușor de observat că expresia dintre paranteze este o sumă parțială a seriei . Astfel, cu o precizie bună, numărul de perturbații este o fracțiune din numărul total de permutări: $\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}=e^{-1}$ $1/e$ $P_{n}=n!$

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

Calculul funcției Euler

Un alt exemplu de aplicare a formulei de includere-excludere este găsirea unei expresii explicite pentru funcția Euler [4] , care exprimă numărul de numere din , coprime cu . $\varphi (n)$ $\{1,2,\ldots ,n\}$ $n$

Fie descompunerea canonică a unui număr în factori primi să aibă forma $n$

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

Un număr este coprim cu dacă și numai dacă niciunul dintre divizorii primi nu împarte . Dacă acum proprietatea înseamnă că împarte , atunci numărul de numere coprime cu este . $m\in \{1,\ldots n\)$ $n$ $p_{i}$ $m$ $a_{i}$ $p_{i}$ $m$ $n$ $N({\overline {a}}_{1},\ldots ,{\overline {a}}_{k})$

Numărul de numere care au proprietăți este , deoarece . $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$

Prin formula de includere-excludere, găsim

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

Această formulă este convertită în forma:

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

Variații și generalizări

Principiul includerii-excluderii pentru probabilități

Fie un spațiu de probabilitate . Atunci formula [1] [3] [5] este valabilă pentru evenimente arbitrare $(\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}\dreapta).

Această formulă exprimă principiul includerii-excluderii pentru probabilități . Poate fi obținut din principiul includerii-excluderii sub formă de funcții indicator:

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

Fie evenimente din spațiul de probabilitate , adică . Să luăm așteptarea matematică a ambelor părți ale acestui raport și, folosind liniaritatea așteptării matematice și egalitatea pentru un eveniment arbitrar , obținem formula de includere-excludere pentru probabilități. $A_{i}$ $(\Omega ,{\mathfrak {F)),{\mathcal {P)))$ $A_{i}\în {\mathfrak {F}}$ ${\mathcal {M}}$ ${\mathcal {P}}(A)={\mathcal {M}}(\mathbf {1} _{A})$ $A\in {\mathfrak {F}}$

Principiul includerii-excluderii în spațiile de măsură

Fie un spațiu cu măsură . Atunci, pentru seturi măsurabile arbitrare de măsură finită , formula de includere-excludere este valabilă: $(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}\right).$

Evident, principiul includerii-excluderii pentru probabilități și pentru cardinalități ale mulțimilor finite sunt cazuri speciale ale acestei formule. În primul caz, măsura este, desigur, o măsură de probabilitate în spațiul de probabilitate corespunzător : . În cel de-al doilea caz, cardinalitatea mulțimii este luată ca măsură : . $\mu (A)={\mathcal {P}}(A)$ $\mu (A)=|A|$

Principiul de includere-excludere pentru spațiile de măsură poate fi derivat, ca și pentru cazurile speciale de mai sus, din identitatea pentru funcțiile indicator:

Fie seturi măsurabile ale spațiului , adică . Integram ambele părți ale acestei egalități în raport cu măsura , folosim liniaritatea integralei și relația , și obținem formula de includere-excludere pentru măsură. $A_{i}$ $(X,{\mathfrak {S}),\mu )$ $A_{i}\in {\mathfrak {S}}$ $\mu$ $\mu (A)=\int _{X}\mathbf {1} _{A}(x)\,d\mu$

Identitatea înaltelor și scăzutelor

Formula de includere-excludere poate fi considerată un caz special al identităţii maximelor şi minimelor :

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

Această relație este valabilă pentru numere arbitrare . Într-un caz particular, când obținem una dintre formele principiului de includere-excludere. Într-adevăr, dacă punem , unde este un element arbitrar din , atunci obținem relația pentru funcțiile indicator ale mulțimilor: $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).$

inversiunea Möbius

Fie o mulțime finită și fie o funcție arbitrară definită pe o mulțime de submulțimi și luând valori reale. Definim functia astfel: $S$ $f\colon 2^{S}\la \mathbb {R}$ $S$ $g\colon 2^{S}\la \mathbb {R}$

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

Atunci următoarea formulă de inversare este valabilă [6] [7] :

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

Această afirmație este un caz special al formulei generale de inversare a lui Möbius pentru algebra de incidență a mulțimii tuturor submulțimii unei mulțimi parțial ordonate de relația de incluziune . $2^{S}$ $S$ $\subset$

Să arătăm cum această formulă implică principiul includerii-excluderii pentru mulțimi finite. Fie dată o familie de submulţimi ale unei mulţimi finite , notăm mulţimea de indici . Pentru fiecare set de indici definim ca fiind numarul de elemente incluse numai in acele multimi pentru care . Din punct de vedere matematic, aceasta poate fi scrisă astfel: $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)) }\dreapta)\dreapta|.$

Apoi funcția definită de formulă $g\colon 2^{S}\la \mathbb {R}$

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

oferă numărul de elemente, fiecare dintre acestea fiind inclus în toate seturile și , poate, în altele. Acesta este $A_{i}$ $i\in X$

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

Mai rețineți că este numărul de elemente care nu au niciuna dintre proprietăți: $f(\varnothing )$

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

Ținând cont de observațiile făcute, scriem formula de inversare a lui Möbius:

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

Aceasta este exact formula de includere-excludere pentru mulțimi finite, doar că nu grupează termeni legați de aceleași valori . $|X|$

Istorie

Formula de includere-excludere a fost publicată pentru prima dată de matematicianul portughez Daniel da Silva în 1854 [1] . Dar încă din 1713, Nicholas Bernoulli a folosit această metodă pentru a rezolva problema Montmort , cunoscută sub numele de problema întâlnirii ( franceză: Le problème des rencontres ) [8] , din care problema tulburării este un caz special . De asemenea, formula de includere-excludere este asociată cu numele matematicianului francez Abraham de Moivre și matematicianul englez Joseph Sylvester [9] .

Vezi și

Formula Grassmann
Boole

Note

↑ 1 2 3 4 5 Riordan J. Introduction to Combinatorial Analysis = An Introduction to Combinatorial Analysis. - M . : Editura de literatură străină, 1963. - S. 63-66. — 289 p.
↑ 1 2 3 Hall M. Teoria combinatorie . - M . : „Mir”, 1970. - S. 18 -20. — 424 p.
↑ 1 2 Rybnikov K. A. Introducere în analiza combinatorie. - Ed. a II-a. - M . : Editura Universității de Stat din Moscova, 1985. - S. 69-73. — 309 p.
↑ Rybnikov K. A. Introducere în analiza combinatorie. - Ed. a II-a. - M. : Editura Universității de Stat din Moscova, 1985. - S. 266. - 309 p.
↑ Borovkov, A. A. Teoria probabilității. - Ed. a II-a. - M . : „Nauka”, 1986. - S. 24. - 431 p.
↑ Hall M. Teoria combinatorie . - M . : „Mir”, 1970. - S. 30 -31. — 424 p.
↑ Stanley R. Enumerative Combinatorics = Enumerative Combinatorics. - M . : „Mir”, 1990. - S. 103-107. — 440 s.
^ Weisstein, Eric W. Derangement pe site- ul Wolfram MathWorld .
↑ Rybnikov K. A. Introducere în analiza combinatorie. - Ed. a II-a. - M. : Editura Universității de Stat din Moscova, 1985. - S. 264. - 309 p.

Literatură

Riordan J. Introduction to Combinatorial Analysis = An Introduction to Combinatorial Analysis. - M . : Editura de Literatură Străină, 1963. - 289 p.
Rybnikov K. A. Introducere în analiza combinatorie. - Ed. a II-a. - M. : Editura Universității de Stat din Moscova, 1985. - 309 p.
Stanley R. Enumerative Combinatorics = Enumerative Combinatorics. — M .: Mir, 1990. — 440 p.
Hall M. Teoria combinatorie . - M . : Mir, 1970. - 424 p.
I. Yaglom. Petice pe caftan // Kvant . - 1974. - Nr 2 . - S. 13-21 .

Link -uri

Weisstein, Eric W. Principiul de includere-excludere (engleză) pe site-ul web Wolfram MathWorld .