Xem mã nguồn của Nguyên lý bao hàm-loại trừ

{{Short description|Kỹ thuật đếm trong tổ hợp}}
[[Tập_tin:Венов_дијаграм.svg|nhỏ|[[Biểu đồ Venn]] cho thấy hợp của ''A'' và ''B'']]

Trong [[tổ hợp]], một nhánh của [[toán học]], '''nguyên lý bao hàm-loại trừ''' (hay '''nguyên lý bao hàm và loại trừ''' hoặc '''nguyên lý bù trừ''') là kỹ thuật đếm tổng quát cho phương phát tìm số các phần tử của [[Hợp (lý thuyết tập hợp)|hợp]] của hai [[tập hữu hạn]] sau:

: <math> |A \cup B| = |A| + |B| - |A \cap B| </math>

trong đó ''A'' và ''B'' là hai tập hữu hạn và |''S'' | là số [[Lực lượng (toán học)|lực lượng]] của tập hợp ''S'' (có thể coi là số phần tử trong tập hợp nếu tập hợp đó [[Tập hữu hạn|hữu hạn]]). Công thức trên nói rằng khi cộng kích thước của hai tập hợp với nhau, giá trị cho có thể quá lớn bởi có thể sẽ có một số phần tử bị đếm hai lần. Các phần tử bị đếm hai lần nằm trong phần [[Giao (lý thuyết tập hợp)|giao]] của hai tập hợp đó và do đó để tìm ra đúng giá trị, ta trừ đi kích thước của phần giao.

Nguyên lý bao hàm-loại trừ là dạng tổng quát của trường hợp chỉ xét hai tập hợp, nên để bắt đầu ví dụ, ta xét công thức cho ba tập hợp ''A'', ''B'' và ''C'':

: <math>|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|</math>

Ta có thể kiểm chứng công thức này bằng cách đếm số lần mỗi vùng trong [[biểu đồ Venn]] nằm trong vế phải của công thức.

[[Tập_tin:Inclusion-exclusion.svg|nhỏ|Minh hoạ nguyên lý bao hàm-loại trừ bằng biểu đồ Venn cho ba tập hợp]]

Tổng quát hoá các ví dụ này sẽ dẫn tới nguyên lý bao hàm-loại trừ. Để tìm lực lượng của hợp của {{mvar|n}} tập hợp:

# Thêm lực lượng của các tập hợp.
# Trừ lực lượng của các phần giao của 2 tập hợp.
# Thêm lực lượng của các phần giao của 3 tập hợp.
# Trừ lực lượng của các phần giao của 4 tập hợp.
# Thêm lực lượng của các phần giao của 5 tập hợp..
# Tiếp tục cho đến khi xét hết phần giao của n tập hợp. Bước cuối sẽ là thêm vào nếu {{mvar|n}} lẻ và trừ đi nếu {{mvar|n}}<nowiki> chẵn}}.</nowiki>

Tên bao hàm-loại trừ lấy từ ý tưởng ta thêm các ''bao hàm'', rồi sau đó ''loại trừ'' các phần thừa.
Khái niệm này được gắn tên với [[Abraham de Moivre]] (1718),<ref name="Roberts 2009 loc=pg. 405">{{harvnb|Roberts|Tesman|2009|loc=pg. 405}}</ref> mặc dù nó ban đầu xuất hiện trong giấy của [[Daniel da Silva (mathematician)|Daniel da Silva]] (1854)<ref>{{harvnb|Mazur|2010|loc=pg. 94}}</ref> và sau đó trong bài viết của [[J. J. Sylvester]] (1883).<ref name="van Lint 1992 loc=pg. 77">{{harvnb|van Lint|Wilson|1992|loc=pg. 77}}</ref> Đôi khi, công thức này được gọi là công thức Da Silva hay công thức Sylvester, do quá trình xuất bản. Nguyên lý này cũng được coi là một ví dụ về một [[Lý thuyết sàng|phương pháp sàng]] được dùng nhiều trong [[lý thuyết số]] và đôi khi cũng được gọi là ''công thức sàng'' trong bối cảnh đó.<ref name="van Lint 1992 loc=pg. 77"/>

Bởi các xác suất hữu hạn được đếm rồi tính tương ứng với lực lượng của [[không gian xác suất]], công thức cho nguyên lý bao hàm-loại trừ vẫn hợp lệ khi ta thay lực lượng của các tập hữu hạn bằng các xác suất hữu hạn. Tổng quát hơn, cả hai phiên bản này đều có đặt nằm dưới [[lý thuyết độ đo]].

Trong ngữ cảnh rất trừu tượng, nguyên lý bao hàm-loại trừ có thể biểu diễn bằng phép tính nghịch đảo của một ma trận nào đó.<ref>{{harvnb|Stanley|1986|loc=pg. 64}}</ref> Nghịch đảo này có cấu trúc đặc biệt, nên nguyên lý này là một trong những kỹ thuật đếm cực kỳ hữu dụng trong tổ hợp và các nhánh toán học có liên quan. Theo lời của [[Gian-Carlo Rota]]:<ref>{{citation|last=Rota|first=Gian-Carlo|title=On the foundations of combinatorial theory I. Theory of Möbius functions|journal=Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete|volume=2|issue=4|pages=340–368|year=1964|doi=10.1007/BF00531932|s2cid=121334025}}</ref>

<blockquote>"Một trong những nguyên lý hữu dụng nhất khi liệt kê trong xác suất rời rạc và lý thuyết tổ hợp là nguyên lý bao hàm-loại trừ trứ danh. Nếu áp dụng đúng cách, nguyên lý này có thể trả lời cho rất nhiều bài toán tổ hợp."</blockquote>

== Công thức ==
Trong công thức tổng quát của nó, nguyên lý bao hàm-loại trừ phát biểu rằng với {{mvar|n}} tập hợp hữu hạn {{math|''A''<sub>1</sub>, …, ''A<sub>n</sub>''}}, ta có định thức sau:

{{NumBlk|:|<math>\left|\bigcup_{i=1}^n A_i\right| = \sum_{i=1}^n |A_i| - \sum_{1 \leqslant i < j \leqslant n} |A_i\cap A_j| + \sum_{1 \leqslant i < j < k \leqslant n} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{n+1} \left|A_1\cap\cdots\cap A_n\right|.</math>|{{EquationRef|1}}}}

[[Tập_tin:Inclusion-exclusion-3sets.png|nhỏ|Mỗi phần tử trong công thức bao hàm-loại trừ dần dần sửa giá trị đếm cho đến khi mỗi vùng trong [[biểu đồ Venn]] duy nhất một lần.]]

Công thức trên có thể viết gọn thành

: <math>\left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^n (-1)^{k+1} \left( \sum_{1 \leqslant i_1 < \cdots < i_k \leqslant n} | A_{i_1} \cap \cdots \cap A_{i_k} | \right)</math>

hoặc

: <math>\left| \bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\neq J\subseteq\{1,\ldots,n\}}(-1)^{|J|+1} \left |\bigcap_{j\in J} A_j\right|.</math>

Nói bằng từ, để đếm số phần tử của hợp hữu hạn các tập hợp hữu hạn, trước hết lấy tổng các lực lượng của các tập hợp đó, rồi trừ đi lực lượng của tập các phần tử xuất hiện ít nhất trong hai tập hợp, sau đó thêm lại số phần tử xuất hiện trong ít nhất ba tập hợp và tiếp tục như thế. Quá trình luôn dừng là bởi không có phần tử nào xuất hiện nhiều hơn số tập hợp đang xét. (Ví dụ chẳng hạn, nếu <math>n = 4,</math> thì không có phần tử nào xuất hiện trong nhiều hơn <math>4</math> tập hợp)

Trong ứng dụng, ta thường dùng nguyên lý này dưới dạng sử dụng phần bù. Tức là, gọi {{mvar|S}} là [[Tập phổ quát|tập phổ dụng]] hữu hạn chứa tất cả các tập {{math|''A<sub>i</sub>''}} và ta gọi <math>\bar{A_i}</math> là phần bù của {{math|''A<sub>i</sub>''}} trong {{mvar|S}}, theo [[luật De Morgan]], ta có

: <math>\left|\bigcap_{i=1}^n \bar{A_i}\right| = \left|S - \bigcup_{i=1}^n A_i \right| =|S| - \sum_{i=1}^n |A_i| + \sum_{1 \leqslant i < j \leqslant n} |A_i\cap A_j| - \cdots + (-1)^n |A_1\cap\cdots\cap A_n|.</math>

Một phiên bản khác của công thức trên được phát biểu như sau: gọi {{math|''P''<sub>1</sub>, ..., ''P<sub>n</sub>''}} là danh sách các tính chất mà mỗi phần tử thuộc tập hợp {{mvar|S}} có thể có hoặc không có, khi đó nguyên lý bao hàm-loại hàm cho phép đếm số các phần tử thuộc {{mvar|S}} và không có tính chất nào trong các tính chất trên bằng cách đặt {{math|''A<sub>i</sub>''}} là tập con của tập các phần tử thuộc {{mvar|S}} và có tính chất {{math|''P<sub>i</sub>''}} và sử dụng nguyên lý trên trong dạng phần bù. Phiên bản này bắt nguồn từ [[J. J. Sylvester]].<ref name="Roberts 2009 loc=pg. 405" />

== Các ví dụ ==

=== Đếm số nguyên ===
Đây là ví dụ đơn giản trong áp dụng nguyên lý bao hàm-loại trừ, xét câu hỏi sau:<ref>{{harvnb|Mazur|2010|loc=pp. 83–4, 88}}</ref>

: Có bao nhiêu số nguyên trong tập {1, ..., 100} không chia hết cho 2, 3 hoặc 5?

Gọi ''S'' = {1,...,100} và ''P''<sub>1</sub> là tính chất số nguyên chia hết cho 2, ''P''<sub>2</sub> là tính chất số nguyên chia hết cho 3 và ''P''<sub>3</sub> là tính chất số nguyên chia hết cho 5. Gọi ''A''<sub>i</sub> là tập con của ''S'' chứa các phần tử có tính chất ''P''<sub>i</sub>, ta đếm được rằng: |''A''<sub>1</sub>| = 50, |''A''<sub>2</sub>| = 33, và |''A''<sub>3</sub>| = 20. Có 16 số nguyên chia hết cho 6, 10 số chia hết cho 10, và 6 số chia hết cho 15. Và cuối cùng, chỉ có 3 số chia hết cho 30, nên số các số nguyên không chia hết cho bất kỳ 2, 3 hoặc 5 được tính bằng:

: 100 − (50 + 33 + 20) + (16 + 10 + 6) − 3 = 26.

=== Đếm số mất thứ tự ===
Một câu hỏi phức tạp hơn trên được phát biểu như sau.

Giả sử có bộ ''n'' lá bài được đánh số từ 1 đến&nbsp;''n''.  Ta gọi lá số ''m'' nằm đúng vị trí nếu nó là lá thứ ''m'' trong bộ bài. Hỏi có bao nhiêu cách, (ký hiệu là ''W''), để xáo bộ bài sao cho trong bộ có ít nhất 1 lá nằm đúng vị trí?

Ta bắt đầu bằng cách định nghĩa ''A''<sub>''m''</sub>, là số các thứ tự bài mà trong đó lá thứ ''m'' nằm đúng vị trí. Khi đó, số các thứ tự ''W'', với ''ít nhất'' một lá nằm đúng vị trí được tính bởi

: <math>W = \left|\bigcup_{m=1}^n A_m\right|.</math>

Áp dụng nguyên lý bao hàm-loại trừ,

: <math>W = \sum_{m_1=1}^n |A_{m_1}| - \sum_{1 \leqslant m_1 < m_2 \leqslant n} |A_{m_1} \cap A_{m_2}| +\cdots + (-1)^{p-1} \sum_{1 \leqslant m_1 < \cdots < m_p \leqslant n} | A_{m_1} \cap \cdots \cap A_{m_p}| + \cdots</math>

Mỗi giá trị <math>A_{m_1} \cap \cdots \cap A_{m_p}</math> biểu diễn tập các phép xáo trong đó có ít nhất ''p'' giá trị ''m''<sub>1</sub>,&nbsp;...,&nbsp;''m<sub>p</sub>'' đang nằm đúng vị trí.  Lưu ý rằng số các xáo trộn với ít nhất ''p'' giá trị nằm đúng chỉ phụ thuộc vào ''p'', chứ không trên giá trị cụ thể của <math>m</math>.  Ví dụ chẳng hạn, số các phép xáo có vị trí thứ 1, thứ ba và thứ 17 nằm đúng bằng với số các phép xáo có vị trí thứ 2, thứ 5 và thứ 14 nằm đúng.  Ta chỉ quan tâm rằng trong ''n'' lá đó và trong trường hợp xét ba lá, có 3 vị trí được chọn là vị trí đúng.  Do đó có <math display="inline">{n \choose p}</math> phần tử bằng nhau trong tổng thứ ''p'' (xem [[Tổ hợp (toán học)|tổ hợp]]).

: <math>W = {n \choose 1} |A_1| - {n \choose 2} |A_1 \cap A_2| + \cdots + (-1)^{p-1} {n \choose p} |A_1 \cap \cdots \cap A_p| + \cdots</math>

<math>|A_1 \cap \cdots \cap A_p|</math> là số các thứ tự có ''p'' phần tử nằm đúng vị trí, và bằng với số xếp thứ tự với ''n''&nbsp;−&nbsp;''p'' phần tử còn lại, hay (''n''&nbsp;−&nbsp;''p'')!.Do đó cuối cùng ta được:

: <math>\begin{align}
W &= {n \choose 1} (n-1)!  - {n \choose 2} (n-2)!  + \cdots + (-1)^{p-1} {n \choose p} (n-p)! + \cdots\\
&= \sum_{p=1}^n (-1)^{p-1} {n \choose p} (n-p)!  \\
&= \sum_{p=1}^n (-1)^{p-1} \frac{n!}{p!(n-p)!} (n-p)! \\
&= \sum_{p=1}^n (-1)^{p-1} \frac{n!}{p!}
\end{align}</math>

Hoán vị mà không có ''lá nào'' nằm đúng vị trí được gọi là ''[[mất thứ tự]]''. Lấy ''n''! là số các hoán vị, xác suất ''Q'' rằng một phép xáo ngẫu nhiên sẽ sinh ra xáo trộn được tính bởi

: <math>Q = 1 - \frac{W}{n!} = \sum_{p=0}^n \frac{(-1)^p}{p!}, </math>

đây là dạng rút gọn về ''n''&nbsp;+&nbsp;1 phần tử của [[Chuỗi Taylor|khai triển Taylor]] của ''e''<sup>−1</sup>. Do đó xác suất đoán một thứ tự cho một bộ bài đã được xáo và sai mọi lá rơi vào khoảng ''e''<sup>−1</sup> hay 37%.

== Trường hợp đặc biệt ==

Trường hợp xảy ra trong ví dụ xáo trộn xảy ra nhiều lúc nên nhận được chú ý đáng kể.<ref>{{harvnb|Brualdi|2010|loc=pp. 167–8}}</ref> Cụ thể, trường hợp đặc biệt xảy ra khi kích thước của các tập giao xuất hiện trong công thức cho nguyên lý bao hàm-loại trừ chỉ dựa vào số tập hợp trong phần giao chứ không quan tâm tới tập nào xuất hiện trong đó. Nói bằng công thức, tức là:

: <math>A_J:=\bigcap_{j\in J} A_j</math>

có cùng số lực lượng, tức ''α<sub>k</sub>'' = |''A<sub>J</sub>''|, với mọi tập con ''k'' phần tử ''J'' của {1,&nbsp;...,&nbsp;''n''}, thì

: <math>\left |\bigcup_{i=1}^n A_i\right|  =\sum_{k=1}^n (-1)^{k-1}\binom nk \alpha_k.</math>

Hoặc viết dưới dạng phần bù, trong đó tập phổ dụng ''S'' có lực lượng ''α''<sub>0</sub>,

: <math>\left |S \smallsetminus \bigcup_{i=1}^n A_i\right|  =\sum_{k=0}^n (-1)^{k}\binom nk \alpha_k.</math>

== Tổng quát hoá công thức ==

Cho [[Họ tập hợp|họ các tập con (cho phép lặp lại)]] ''A''<sub>1</sub>, ''A''<sub>2</sub>, ..., ''A''<sub>n</sub> của tập phổ dụng ''S'', nguyên lý bao hàm-loại trừ tính số các phần tử thuộc ''S'' mà không nằm trong bất kỳ tập con nào trong họ này. Dạng tổng quát của khái này sẽ tính số các phần thuộc ''S'' và thuộc duy nhất ''m'' tập con.

Gọi ''N'' = <nowiki>[</nowiki>''n''<nowiki>]</nowiki> = {1,2,...,''n''}. Nếu ta định nghĩa <math>A_{\emptyset} = S</math>, thì nguyên lý bao hàm-loại trừ có thể viết lại như sau sử dụng ký hiệu trong đoạn trước: số các phần tử thuộc ''S'' nhưng không thuộc bất kỳ ''A''<sub>i</sub> là:

: <math> \sum_{J \subseteq [n]} (-1)^{|J|} |A_J|.</math>

Nếu ''I'' là tập con cố định của tập chỉ số ''N'', thì số phần tử thuộc ''A''<sub>i</sub> với mọi ''i'' thuộc ''I'' và không phần tử khác thuộc về là:<ref>{{harvnb|Cameron|1994|loc=pg. 78}}</ref>

: <math> \sum_{I \subseteq J} (-1)^{|J| - |I|} |A_J|.</math>

Định nghĩa các tập sau

: <math>B_k = A_{I \cup \{ k \}} \text{ với } k \in N \smallsetminus I.</math>

Để tính số các phần tử không thuộc bất kỳ ''B''<sub>k</sub> nào, thì theo nguyên lý bao hàm-loại trừ (với <math>B_\emptyset = A_I</math>), bằng với

: <math>\sum_{K \subseteq N \smallsetminus I} (-1)^{|K|}|B_K|.</math>

Tương ứng ''K'' ↔ ''J'' = ''I'' ∪ ''K'' giữa các tập con của ''N''&nbsp;\&nbsp;''I'' và các tập con của ''N'' có chứa ''I'' là song ánh và nếu ''J'' và ''K'' tương ứng với nhau dưới ánh xạ này thì ''B''<sub>K</sub> = ''A''<sub>J</sub>, cho thấy kết quả hợp lệ.

== Trong xác suất ==

Trong [[xác suất]], cho các biến cố ''A''<sub>1</sub>, ..., ''A''<sub>''n''</sub> trong [[không gian xác suất]] <math>(\Omega,\mathcal{F},\mathbb{P})</math>, nguyên lý bao hàm-loại trừ cho trường hợp ''n''&nbsp;=&nbsp;2 là

: <math>\mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2),</math>

và cho trường hợp ''n''&nbsp;=&nbsp;3:

: <math>\mathbb{P}(A_1\cup A_2\cup A_3)=\mathbb{P}(A_1)+\mathbb{P}(A_2)+\mathbb{P}(A_3)-\mathbb{P}(A_1\cap A_2)-\mathbb{P}(A_1\cap A_3)-\mathbb{P}(A_2\cap A_3)+\mathbb{P}(A_1\cap A_2\cap A_3)</math>

và trong tổng quát

: <math>\mathbb{P}\left(\bigcup_{i=1}^n A_i\right)=\sum_{i=1}^n \mathbb{P}(A_i) -\sum_{i<j}\mathbb{P}(A_i\cap A_j)+\sum_{i<j<k}\mathbb{P}(A_i\cap A_j\cap A_k) + \cdots +(-1)^{n-1} \sum_{i<...<n}\mathbb{P}\left(\bigcap_{i=1}^n A_i\right),</math>

có thể viết gọn lại thành

: <math>\mathbb{P}\left(\bigcup_{i=1}^n A_i\right)=\sum_{k=1}^n \left((-1)^{k-1}\sum_{I\subseteq\{1,\ldots,n\}\atop |I|=k} \mathbb{P}(A_I)\right),</math>

trong đó tổng cuối chạy trên tất cả tập con ''I'' của 1, ..., ''n'' và chứa chính xác ''k'' phần tử, và

: <math>A_I:=\bigcap_{i\in I} A_i</math>

là giao của tất cả các ''A<sub>i</sub>'' với chỉ số thuộc ''I''.

Theo các [[Bất đẳng thức Boole#Bất đẳng thức Bonferroni|bất đẳng thức Bonferroni]], tổng của các phần tử đầu tiên thay phiên là cận trên và cận dưới cho vế trái. Ta có thể dùng ý này để tính xấp xỉ khi công thức đầy đủ quá dài để tính.

Đối với [[không gian độ đo]] (''S'',Σ,''μ'') và các tập con [[đo được]] ''A''<sub>1</sub>, ..., ''A''<sub>''n''</sub> với độ đo hữu hạn, các định thức trên vẫn đúng khi độ đo xác suất <math>\mathbb{P}</math> được thay bằng độ đo ''μ''.

=== Trường hợp đặc biệt ===

Nếu, trong phiên bản xác suất của nguyên lý bao hàm-loại trừ, xác suất của giao các ''A''<sub>''I''</sub> chỉ dựa trên số lực lượng của ''I'', nghĩa là với mọi ''k'' thuộc {1,&nbsp;...,&nbsp;''n''} tồn tại ''a<sub>k</sub>'' sao cho

: <math>a_k=\mathbb{P}(A_I) \text{ với mọi } I\subset\{1,\ldots,n\} \text{ và } |I|=k,</math>

thì công thức trên giản hoá thành

: <math>\mathbb{P}\left(\bigcup_{i=1}^n A_i\right) =\sum_{k=1}^n (-1)^{k-1}\binom n k a_k </math>

,sử dụng suy luận tổ hợp với [[hệ số nhị thức]] <math display="inline">\binom nk</math>. Ví dụ chẳng hạn, nếu các biến cố <math>A_i</math> đều [[Độc lập và phân phối đều|độc lập và phân phối đều với nhau]], thì <math>\mathbb{P}(A_i) = p</math> với mọi ''i'', và ta có <math>a_k = p^k</math>, và khi đó công thức ngay trên giản hoá tiếp thành

: <math>\mathbb{P}\left(\bigcup_{i=1}^n A_i\right) = 1 - (1-p)^n. </math>

(Kết quả này cũng có thể thu được bằng xét phần giao của các phần bù của các biến cố <math>A_i</math>.)

Tồn tại dạng giản hoá tương tự cho trường hợp không gian độ đo {{math|(''S'', Σ, ''μ'')}} và các tập con đo được ''A''<sub>1</sub>, ..., ''A''<sub>''n''</sub> với độ đo hữu hạn.

== Các công thức khác ==

Nguyên lý đôi khi được phát biểu dưới dạng sau<ref>{{harvnb|Graham|Grötschel|Lovász|1995|loc=pg. 1049}}</ref> : nếu

: <math>g(A)=\sum_{S \subseteq A}f(S)</math>

thì
{{NumBlk|:|<math>f(A)=\sum_{S \subseteq A}(-1)^{|A|-|S|}g(S) </math>|{{EquationRef|⁎⁎}}}}

Phiên bản tổ hợp và phiên bản xác suất của nguyên lý bao hàm-loại trừ đều lấy từ ({{EquationNote|⁎⁎}}).
{{math proof|Đặt <math>\underline{m} = \{1,2,\ldots,m\}</math>, <math>f(\underline{m}) = 0</math>, và

:<math>f(S)=\left|\bigcap_{i \in \underline{m} \smallsetminus S} A_i \smallsetminus \bigcup_{i \in S} A_i\right| \text{ và } f(S) = \mathbb{P} \left(\bigcap_{i \in \underline{m} \smallsetminus S} A_i \smallsetminus \bigcup_{i \in S} A_i\right)</math>

tương ứng với mọi [[tập hợp (toán học)|tập hợp]] <math>S</math> với <math>S \subsetneq \underline{m}</math>. Thì ta thu được

:<math>g(A)=\left|\bigcap_{i \in \underline{m} \smallsetminus A} A_i\right|, \quad g(\underline{m}) = \left|\bigcup_{i \in \underline{m}} A_i \right| \text{ và } g(A) = \mathbb{P} \left( \bigcap_{i \in \underline{m} \smallsetminus A} A_i \right),~~ g(\underline{m}) = \mathbb{P} \left(\bigcup_{i \in \underline{m}} A_i\right)</math>

tương ứng với tất cả tập <math>A</math> thoả mãn <math>A \subsetneq \underline{m}</math>. Điều này đúng là bởi các [[phần tử (toán học)|phần tử]] <math>a</math> của <math>\cap_{i \in \underline{m} \smallsetminus A} A_i</math> có thể nằm trong các <math>A_i</math> khác (các <math>A_i</math> với <math>i \in A</math>), và công thức {{nowrap|<math>\cap \smallsetminus \cup</math>}} chạy qua tất cả mở rộng khả thi của các tập hợp <math>\{A_i \mid i \in \underline{m} \smallsetminus A\}</math> cùng với các <math>A_i</math> khác, đếm <math>a</math> chỉ với các tập khớp với điều kiện "là phần tử của" của <math>a</math>, khi <math>S</math> chạy qua tất cả [[tập con]] của <math>A</math> (như trong định nghĩa của <math>g(A)</math>).

Bởi <math>f(\underline{m}) = 0</math>, ta thu được từ ({{EquationNote|⁎⁎}}) với <math>A = \underline{m}</math> rằng

:<math>\sum_{\underline{m} \supseteq T \supsetneq \varnothing}(-1)^{|T|-1} g(\underline{m} \smallsetminus T) = \sum_{\varnothing \subseteq S \subsetneq \underline{m}}(-1)^{m-|S|-1} g(S) = g(\underline{m})</math>

và sau khi đổi vế, thì sẽ thu được bản tổ hợp và bản xác suất của nguyên lý bao hàm-loại trừ.}}

Nếu ta coi <math>n</math> là tập các ước nguyên tố của nó, thì ({{EquationNote|⁎⁎}}) là dạng tổng quát của [[công thức biến đổi ngược Möbius]] cho các [[số tự nhiên]] [[số square-free|square-free]] (là các số không chia hết cho bình phương của bất kỳ số nguyên tố nào). Do vậy, ({{EquationNote|⁎⁎}}) được xem là công thức biến đổi ngược Möbius cho [[đại số liên thuộc]] của [[tập sắp thứ tự riêng phần]] tất cả tập con của ''A''.

Đối với dạng tổng quát của bản đầy đủ của công thức biến đổi ngược Möbius, ({{EquationNote|⁎⁎}}) phải được tổng quát hoá bằng cách xét các [[đa tập]] (cho phép có phần tử trùng nhau trong tập hợp). Khi dùng đa tập thay vì tập hợp, Công thức ({{EquationNote|⁎⁎}}) trở trình

{{NumBlk|:|<math>f(A) = \sum_{S\subseteq A}\mu(A - S) g(S) </math>|{{EquationRef|⁎⁎⁎}}}}

trong đó <math>A - S</math> là đa tập thoả mãn <math>(A - S) \uplus S = A</math>, và

* ''μ''(''S'') =  1 nếu ''S'' là tập hợp (tức đa tập không có cặp phần tử trùng nhau) có số lực lượng chẵn
* ''μ''(''S'') =  −1 nếu ''S'' là tập hợp có số lực lượng lẻ.
* ''μ''(''S'') =  0 if ''S'' là đa tập (tức ''S'' có cặp phần tử trùng nhau).

Quan sát rằng <math>\mu(A - S)</math> là <math>(-1)^{|A|-|S|}</math> của ({{EquationNote|⁎⁎}}) trong trường hợp <math>A - S</math> là tập hợp.

{{Math proof|title=Chứng minh ({{EquationNote|⁎⁎⁎}})|Thay
<math display="block">g(S)=\sum_{T\subseteq S}f(T)</math>
vào vế phải của ({{EquationNote|⁎⁎⁎}}). Để ý rằng <math>f(A)</math> xuất hiện một lần ở cả hai bên của {{EquationNote|⁎⁎⁎}}). Do đó ta phải chứng minh với mọi <math>T</math> thoả mãn <math>T\subsetneq A</math>, các phần tử <math>f(T)</math> sẽ tự khử nhau trong vế phải của ({{EquationNote|⁎⁎⁎}}). Để làm vậy, cố định <math>T</math> sao cho <math>T\subsetneq A</math> và lấy một phần tử <math>a \in A</math> bất kỳ sao cho <math>a \notin T</math>.

Quan sát rằng <math>A - S</math> phải là tập hợp với mỗi xuất hiện [[số dương|dương]] hay [[số âm|âm]] của <math>f(T)</math> trong phải của ({{EquationNote|⁎⁎⁎}}) và được chọn theo đa tập <math>S</math> thoả mãn <math>T \subseteq S \subseteq A</math>. Mỗi lần xuất hiện của <math>f(T)</math> trên vế phải ({{EquationNote|⁎⁎⁎}}) thu được bằng lấy <math>S</math> sao cho <math>A - S</math> là tập hợp chứa phần tử <math>a</math> sẽ triệt tiêu với giá trị thu được bằng lấy tập <math>S</math> tương ứng thoả mãn <math>A - S</math> là tập hợp không chứa phần tử <math>a</math>. Từ đây suy ra kết quả cần tìm}}

== Ứng dụng ==

Nguyên lý bao hàm-loại trừ được sử dụng rộng rãi nên chỉ có một vài được nhắc ở dưới đây.
<!--
=== Đếm số xáo trộn ===

{{main|Xáo trộn}}

Một trong những ứng dụng nổi bật của nguyên lý bao hàm-loại trừ là giải bài toán tổ hợp đếm số [[xáo trộn]] của một tập hữu hạn. ''Xáo trộn'' (derangement) of a set ''A'' is a [[bijection]] from ''A'' into itself that has no fixed points. Via the inclusion–exclusion principle one can show that if the cardinality of ''A'' is ''n'', then the number of derangements is [''n''!&nbsp;/&nbsp;''e''] where [''x''] denotes the [[Nearest integer function|nearest integer]] to ''x''; a detailed proof is available [[Random permutation statistics#Number of permutations that are derangements|here]] and also see [[Nguyên lý bao hàm-loại trừ#Examples|the examples section]] above.

The first occurrence of the problem of counting the number of derangements is in an early book on games of chance: ''Essai d'analyse sur les jeux de hazard'' by P. R. de Montmort (1678 – 1719) and was known as either "Montmort's problem" or by the name he gave it, "''problème des rencontres''."<ref>{{harvnb|van Lint|Wilson|1992|loc=pp. 77-8}}</ref> The problem is also known as the ''hatcheck problem.''

The number of derangements is also known as the [[subfactorial]] of ''n'', written !''n''. It follows that if all bijections are assigned the same probability then the probability that a random bijection is a derangement quickly approaches 1/''e'' as ''n'' grows.
-->

=== Đếm số phần giao ===
Nguyên lý bao hàm-loại trừ khi kết hợp với [[luật De Morgan]], có thể dùng để đếm số lực lượng của phần giao của các tập hợp. Gọi <math>\overline{A_k}</math> là [[phần bù (lý thuyết tập hợp)|phần bù]] của ''A<sub>k</sub>'' tương ứng với tập phổ dụng ''A'' nào đó sao cho <math>A_k \subseteq A</math> với mỗi ''k''. Khi đó ta có

: <math>\bigcap_{i=1}^n A_i = \overline{\bigcup_{i=1}^n \overline{A_i}}</math>

Do đó chuyển bài toán từ đếm phần giao sang đếm phần hợp.

=== Tô màu đồ thị ===
Nguyên lý bao hàm-loại trừ lập thành cơ sở của các thuật toán giải các bài phân hoạch đồ thị thuộc lớp NP-hard, ví dụ chẳng hạn như [[tô màu đồ thị]].<ref name="bhk">{{harvnb|Björklund|Husfeldt|Koivisto|2009}}</ref>

Một ứng dụng nổi bật của nguyên lý là phương pháp xây [[đa thức xắc số]].<ref>{{harvnb|Gross|2008|loc=pp. 211–13}}</ref>

=== So khớp hoàn hảo trong đồ thị hai phía ===
Số các [[so khớp hoàn hảo]] của một [[đồ thị hai phía]] có thể tính bằng nguyên lý này.<ref>{{harvnb|Gross|2008|loc=pp. 208–10}}</ref>

=== Đếm số toàn ánh ===
Câu hỏi đặt ra là cho hai tập con ''A'' và ''B'', có bao nhiêu [[Toàn ánh|hàm toàn ánh]] đi từ ''A'' đến ''B''? [[Không mất tính tổng quát]], ta có thể lấy ''A'' = {1, ..., ''k''} và ''B'' = {1, ..., ''n''}, bởi ta chỉ quan tâm đến lực lượng của mỗi tập hợp. Gọi ''S'' là tập các [[Hàm số|hàm]] từ ''A'' đến ''B'', và định nghĩa với mỗi ''i'' thuộc ''B'', tính chất ''P<sub>i</sub>'' :"hàm bỏ qua giá trị ''i'' thuộc ''B''" (''i'' không nằm trong [[Ảnh (toán học)|ảnh]] của hàm số), nguyên lý bao hàm-loại trừ sẽ đếm số toàn ánh giữa ''A'' và ''B'' như sau:<ref>{{harvnb|Mazur|2008|loc=pp.84-5, 90}}</ref>

: <math>\sum_{j=0}^{n} \binom{n}{j} (-1)^j (n-j)^k.</math>

=== Đếm các hoán vị cấm vị trí ===
[[Hoán vị]] của tập hợp ''S'' = {1, ..., ''n''} trong đó mỗi phần tử thuộc ''S'' có thể bị cấm ngồi vị trí nào đó (ở đây là hoán vị được coi là cách sắp xếp thứ tự các phần tử thuộc ''S'') được ta tạm gọi là ''hoán vị cấm vị trí''. Ví dụ chẳng hạn, cho ''S'' = {1,2,3,4}, các hoán vị thoả mãn hai điều kiện cấm: 1 không được nằm tại vị trí 1 hoặc 3, và 2 không nằm trong vị trí 4 là: 2134, 2143, 3124, 4123, 2341, 2431, 3241, 3421, 4231 và 4321. Đặt ''A<sub>i</sub>'' là tập các vị trí mà ''i'' không được phép ngồi vào, và tính chất ''P''<sub>''i''</sub> là tính chất đặt ''i'' vào vị trí ''A<sub>i</sub>'', nguyên lý bao hàm-loại trừ có thể dùng để đếm số các hoán vị thoả mãn tất cả điều kiện cấm.<ref>{{harvnb|Brualdi|2010|loc=pp. 177–81}}</ref>

Trong ví dụ trên, có 12 = 2(3!) hoán vị thoả mãn tính chất ''P''<sub>1</sub>, 6 = 3! hoán vị thoả mãn tính chất ''P''<sub>2</sub> và không có hoán vị nào cho ''P''<sub>3</sub> hoặc ''P''<sub>4</sub> bởi không có điều kiện cấm cho hai giá trị đó. Số các hoán vị thoả mãn các điều kiện cấm cho trước là:

: 4! − (12 + 6 + 0 + 0) + (4) = 24 − 18 + 4 = 10.

Số 4 ở cuối bước tính toán là số các hoán vị thoả mãn đồng thời hai tính chất ''P''<sub>1</sub> và ''P''<sub>2</sub>.

<!--
=== Số Stirling thuộc loại hai ===
{{main|Số Stirling thuộc loại hai}}

[[Số Stirling thuộc loại hai]], ''S''(''n'',''k'') đếm số [[Phân hoạch tập hợp|phân hoạch]] của tập ''n'' phần tử thành ''k'' tập con khác rỗng. Công thức cụ thể để tìm số có thể tìm bằng cách áp dụng nguyên lý bao hàm-loại trừ cho một bài toán có quan hệ rất gần sau: bài toán đếm số phân hoạch của tập ''n'' phần tử thành ''k'' tập con khác rỗng An explicit formula for them can be obtained by applying the principle of inclusion–exclusion to a very closely related problem, namely, counting the number of partitions of an ''n''-set into ''k'' non-empty but distinguishable boxes ([[Ordered set|ordered]] non-empty subsets). Using the universal set consisting of all partitions of the ''n''-set into ''k'' (possibly empty) distinguishable boxes, ''A''<sub>1</sub>, ''A''<sub>2</sub>, …, ''A<sub>k</sub>'', and the properties ''P<sub>i</sub>'' meaning that the partition has box ''A<sub>i</sub>'' empty, the principle of inclusion–exclusion gives an answer for the related result. Dividing by ''k''! to remove the artificial ordering gives the Stirling number of the second kind:<ref>{{harvnb|Brualdi|2010|loc=pp. 282&ndash;7}}</ref>

: <math>S(n,k) = \frac{1}{k!}\sum_{t=0}^k (-1)^t \binom k t (k-t)^n.</math>
-->
=== Đa thức quân xe ===
{{main|Đa thức quân xe}}

Đa thức quân xe là [[đa thức sinh|hàm sinh]] số cách đặt các [[Xe (cờ vua)|quân xe]] không tân công lẫn nhau trên ''bàn cờ B'' trông như tập con của các ô vuông của [[bảng kẻ ô]]; nghĩa là, bất kỳ hai con xe không được phép đặt cùng hàng hay cùng cột và bàn cờ ''B'' là tập con bất kỳ của các ô vuông của một bàn cờ hình chữ nhật có ''n'' hàng và ''m'' cột; ta có thể gọi nó là tập các ô được phép đặt quân lên. [[Hệ số]] ''r<sub>k</sub>''(''B'') của ''x<sup>k</sup>'' trong đa thức quân xe ''R<sub>B</sub>''(''x'') là số cách đặt ''k'' quân xe trong đó không có cái nào trong đó tấn công cái còn lại và có thể xếp trong bàn cờ ''B''. Cho bất kỳ bàn ''B'', có bàn bù <math>B'</math> chứa các ô vuông cùa bàn hình chữ nhật và không nằm trong ''B''. Cái bàn bù này cũng có đa thức quân xe <math>R_{B'}(x)</math> cùng với các hệ số <math>r_k(B').</math>

Đôi khi để tiện cho tính toán, ta tính hệ số cao nhất trong đa thức quân xe bằng các hệ số của đa thức quân xe của bàn bù.Không mất tính tổng quát, ta có thể giả sử ''n'' ≤ ''m'', do đó hệ số này là ''r<sub>n</sub>''(''B''). Số cách đặt ''n'' quân xe không tấn công lẫn nhau trên bàn kẻ ô đầy đủ ''n'' × ''m'' (chưa quan tâm tới việc liệu các quân có đúng đặt trong bàn''B'') được tính theo [[giai thừa giảm]] sau:

: <math>(m)_n = m(m-1)(m-2) \cdots (m-n+1).</math>

Gọi ''P''<sub>i</sub> là tính chất đặt ''n'' quân xe không tấn công nhau trên bàn đầy đủ có quân ở cột ''i'' và không nằm trong ô thuộc bàn ''B'', thì theo nguyên lý bao hàm-loại trừ, ta có công thức:<ref>{{harvnb|Roberts|Tesman|2009|loc=pp.419–20}}</ref>

: <math> r_n(B) = \sum_{t=0}^n (-1)^t (m-t)_{n-t} r_t(B'). </math>

=== Hàm phi Euler ===
{{main|Hàm phi Euler}}

Hàm phi Euler hay gọi ngắn lại đi là hàm phi, ''φ''(''n'') là [[hàm số học]] đếm số các số nguyên nhỏ hơn hoặc bằng ''n'' và [[nguyên tố cùng nhau]] với ''n''. Nghĩa là, nếu ''n'' là [[số nguyên dương]], thì φ(''n'') là số các số nguyên ''k'' thuộc đoạn 1 ≤ ''k'' ≤ ''n'' không có ước chung với ''n'' nào khác ngoài 1. Nguyên lý bao hàm -loại trừ có thể dùng để tìm ra công thức cho φ(''n''). Gọi ''S'' là tập {1, ..., ''n''} và định nghĩa tính chất ''P<sub>i</sub>'' là số thuộc ''S'' chia hết cho số nguyên tố ''p<sub>i</sub>'', với 1 ≤ ''i'' ≤ ''r'',trong đó [[phân tích thừa số nguyên tố]] của

: <math>n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}.</math>

thì,<ref>{{harvnb|van Lint|Wilson|1992|loc=pg. 73}}</ref>

: <math>\varphi(n) = n - \sum_{i=1}^r \frac{n}{p_i} + \sum_{1 \leqslant i < j \leqslant r} \frac{n}{p_i p_j} - \cdots = n \prod_{i=1}^r \left (1 - \frac{1}{p_i} \right ).</math>

== Nguyên lý bao hàm-loại trừ bị pha loãng ==
{{See also|Bất đẳng thức Bonferroni}}

Trong nhiều trường hợp nguyên lý có thể đưa công thức chính xác (chẳng hạn như đếm [[số nguyên tố]] khi sử dụng [[sàng Eratosthenes]]), công thức suy ra được đôi khi không hữu dụng bởi số các phần tử của nó quá nhiều. Và, kể cả khi mỗi số hạng trong đó có thể được ước lượng chính xác, thì tổng các sai số có thể khiến cho công thức bao hàm-loại trừ không áp dụng trực tiếp được. Trong [[lý thuyết số]], vấn đề này được [[Viggo Brun]] nhắc tới. Sau một khởi đầu chậm, các ý tưởng của ông dần được thu nhận bởi người khác, và từ đó một lượng lớn [[lý thuyết sàng|phương pháp sàng]] được phát triển dựa trên đó. Các phương pháp này có thể dùng để thử tìm cận trêm cho các tập "đã được sàng", thay vì phải tìm công thức chính xác.

Gọi ''A''<sub>1</sub>, ..., ''A''<sub>''n''</sub> là các tập hợp tuỳ ý và ''p''<sub>1</sub>, ..., ''p''<sub>''n''</sub> là các số thực thuộc đoạn [0, 1]. Khi đó, với mỗi số nguyên chẵn ''k'' thuộc {0, ..., ''n''}, các [[hàm chỉ thị]] đều thoả mãn bất đẳng thức sau:<ref>{{harv|Fernández|Fröhlich|Alan D.|1992|loc=Proposition&nbsp;12.6}}</ref>

: <math>1_{A_1\cup\cdots\cup A_n} \ge \sum_{j=1}^k (-1)^{j-1}\sum_{1\le i_1<\cdots<i_j\le n} p_{i_1} \dots p_{i_j} \, 1_{A_{i_1} \cap \cdots \cap A_{i_j}}.</math>

== Chứng minh công thức chính ==

Chọn một phần từ nằm trong hợp tất cả các tập và gọi <math>A_1, A_2, \dots, A_t (t > 0)</math> là các tập chứa nó. Bởi phần tử được đếm 1 lần theo vế trái của phương trình ({{EquationNote|1}}), nên ta cần chứng minh nó cũng được đếm duy nhất 1 lần theo vế phải. Trong vế phải, các phần cộng giá trị không diễn ra khi các tập con có chứa phần tử được chọn, tức là tất cả tập được chọn đều từ <math>A_1, A_2, \dots, A_t</math>. Phần cộng đều bằng một cho mỗi tập hợp này (cộng hoặc trừ dựa trên số hạng) và do đó chỉ cần dựa trên số tập con được dùng. Khi đó ta có

: <math>\begin{align}
|\{A_i \mid 1 \leqslant i \leqslant t\}| &- |\{A_i \cap A_j \mid 1 \leqslant i < j \leqslant t\}| + \cdots + (-1)^{t+1}|\{A_1 \cap A_2 \cap \cdots \cap A_t\}| = \binom{t}{1} - \binom{t}{2} + \cdots + (-1)^{t+1}\binom{t}{t}.
\end{align}</math>

Theo [[định lý nhị thức]],

: <math> 0 = (1-1)^t= \binom{t}{0} - \binom{t}{1} + \binom{t}{2} - \cdots + (-1)^t\binom{t}{t}.</math>

Sử dụng ý <math>\binom{t}{0} = 1</math> là đổi chỗ các số hạng đi, ta được

: <math>1 = \binom{t}{1} - \binom{t}{2} + \cdots + (-1)^{t+1}\binom{t}{t},</math>

và do vậ, phần tử được chọn được đếm duy nhất một lần trong vế phải của phương trình ({{EquationNote|1}}).

=== Chứng minh bằng đại số ===
Chứng minh bằng đại số theo các [[hàm chỉ thị]] (hay còn gọi là hàm đặc trưng). Hàm chỉ thị của tập con ''S'' của tập ''X'' là hàm

: <math>\begin{align}
&\mathbf{1}_S: X \to \{0,1\} \\
&\mathbf{1}_S(x) = \begin{cases} 1 & x \in S\\ 0 & x \notin S \end{cases}
\end{align}</math>

Nếu <math>A</math> và <math>B</math> là hai tập con của <math>X</math>, thì

: <math>\mathbf{1}_A \cdot\mathbf{1}_B = \mathbf{1}_{A\cap B}.</math>

Gọi ''A'' là hợp <math display="inline">\bigcup_{i=1}^n A_i</math> của các tập hợp ''A''<sub>1</sub>, ..., ''A<sub>n</sub>''. Để chứng minh nguyên lý bao hàm-loại trừ trong tổng quát, trước hết ta cần kiểm tra định thức

{{NumBlk|:|<math>\mathbf{1}_A  =\sum_{k=1}^n (-1)^{k-1} \sum_{I\subset\{1,\ldots,n\} \atop|I| = k} \mathbf{1}_{A_I}</math>|{{EquationRef|⁎}}}}

cho hàm chỉ thị, trong đó:

: <math>A_I = \bigcap_{i\in I} A_i.</math>

Hàm sau

: <math>\left (\mathbf{1}_A-\mathbf{1}_{A_1} \right )\left (\mathbf{1}_A-\mathbf{1}_{A_2} \right )\cdots \left (\mathbf{1}_A-\mathbf{1}_{A_n} \right ),</math>

bằng không là bởi: nếu ''x'' không thuộc ''A'', thì tất cả các nhân tử đều là 0&#x2009;−&#x2009;0 = 0; và ngược lại, nếu ''x'' có thuộc một số ''A<sub>m</sub>'', thì nhân tử thứ ''m'' tương ứng là 1&#x2009;−&#x2009;1&#x2009;=&#x2009;0.Bằng cách mở rộng tích ở vế trái, suy ra phương trình ({{EquationNote|⁎}}).

Để chứng minh nguyên lý bao hàm-loại trừ cho lực lượng của tập hợp , ta lấy tổng phương trình ({{EquationNote|⁎}}) trên tất cả các ''x'' thuộc hợp của ''A''<sub>1</sub>, ..., ''A<sub>n</sub>''. Để từ đây lấy ra phiên bản xác suất, cho [[giá trị kỳ vọng]] vào ({{EquationNote|⁎}}). Và tổng quát hơn, [[Tích phân Lebesgue|lấy tích phân]] phương trình ({{EquationNote|⁎}}) tương ứng với to&nbsp;''μ''. Luôn sử dụng tính tuyến tính khi dẫn xuất ra các phiên bản này.

== Xem thêm ==

* {{annotated link|Bất đẳng thức Boole}}
* {{annotated link|Các nguyên lý tổ hợp}}
* {{annotated link|Định thức lớn nhất-nhỏ nhất}}
* {{annotated link|Bài toán vòng cổ}}
* {{annotated link|Nguyên lý ngăn kéo Dirichlet}}
* {{annotated link|Công thức Schuette–Nesbitt}}

== Chú thích ==
{{tham khảo|30em}}

== Tham khảo ==

* {{Citation|last1=Allenby|first1=R.B.J.T.|title=How to Count: An Introduction to Combinatorics|url=http://www.crcpress.com/product/isbn/9781420082609|pages=51–60|year=2010|series=Discrete Mathematics and Its Applications|edition=2|publisher=CRC Press|isbn=9781420082609|last2=Slomson|first2=Alan}}
* {{Citation|last1=Björklund|first1=A.|title=Set partitioning via inclusion–exclusion|journal=[[SIAM Journal on Computing]]|volume=39|issue=2|pages=546–563|year=2009|doi=10.1137/070683933|last2=Husfeldt|first2=T.|last3=Koivisto|first3=M.}}
* {{Citation|last=Brualdi|first=Richard A.|title=Introductory Combinatorics|year=2010|edition=5th|publisher=Prentice–Hall|isbn=9780136020400}}
* {{Citation|last=Cameron|first=Peter J.|title=Combinatorics: Topics, Techniques, Algorithms|year=1994|publisher=Cambridge University Press|isbn=0-521-45761-0}}
* {{Citation|last1=Fernández|first1=Roberto|title=Random Walks, Critical Phenomena, and Triviality in Quantum Field Theory|pages=xviii+444|year=1992|series=Texts an Monographs in Physics|place=Berlin|publisher=[[Springer-Verlag]]|isbn=3-540-54358-9|mr=1219313|zbl=0761.60061|last2=Fröhlich|first2=Jürg|last3=Alan D.|first3=Sokal|author2-link=Jürg Fröhlich|author3-link=Alan Sokal}}
* {{Citation|last1=Graham|first1=R.L.|title=Hand Book of Combinatorics (volume-2)|year=1995|publisher=MIT Press – North Holland|isbn=9780262071710|last2=Grötschel|first2=M.|last3=Lovász|first3=L.|author2-link=Martin Grötschel}}
* {{citation|last=Gross|first=Jonathan L.|title=Combinatorial Methods with Computer Applications|year=2008|publisher=Chapman&Hall/CRC|isbn=9781584887430}}
* {{springer|title=Inclusion-and-exclusion principle|id=p/i050430}}
* {{citation|last=Mazur|first=David R.|title=Combinatorics A Guided Tour|year=2010|publisher=The Mathematical Association of America|isbn=9780883857625}}
* {{citation|last1=Roberts|first1=Fred S.|title=Applied Combinatorics|year=2009|edition=2nd|publisher=CRC Press|isbn=9781420099829|last2=Tesman|first2=Barry}}
* {{citation|last=Stanley|first=Richard P.|title=Enumerative Combinatorics Volume I|year=1986|publisher=Wadsworth & Brooks/Cole|isbn=0534065465}}
* {{citation|last1=van Lint|first1=J.H.|title=A Course in Combinatorics|year=1992|publisher=Cambridge University Press|isbn=0521422604|last2=Wilson|first2=R.M.}}

{{PlanetMath attribution|id=2803|title=principle of inclusion–exclusion}}

{{DEFAULTSORT:Inclusion-exclusion principle}}
[[Thể loại:Tổ hợp liệt kê]]
[[Thể loại:Lý thuyết xác suất]]
<!---->
[[Thể loại:Nguyên lý toán học]]