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 của hai tập hữu hạn sau:

: $|A\; \backslash cup\; B|\; =\; |A|\; +\; |B|\; -\; |A\; \backslash cap\; B|$

trong đó A và B là hai tập hữu hạn và |S | là số 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 đó 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 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:

: $|A\; \backslash cup\; B\; \backslash cup\; C|\; =\; |A|\; +\; |B|\; +\; |C|\; -\; |A\; \backslash cap\; B|\; -\; |A\; \backslash cap\; C|\; -\; |B\; \backslash cap\; C|\; +\; |A\; \backslash cap\; B\; \backslash cap\; C|$

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.

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 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 lẻ và trừ đi nếu chẵn.

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), mặc dù nó ban đầu xuất hiện trong giấy của Daniel da Silva (1854) và sau đó trong bài viết của J. J. Sylvester (1883). Đô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 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 đó. 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:

"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."

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 tập hợp hữu hạn , ta có định thức sau:

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

: $\backslash left|\backslash bigcup\_\{i=1\}^n\; A$i\right| = \sum{k=1}^n (-1)^{k+1} \left( \sum_{1 \leqslant i_1 < \cdots < ik \leqslant n} | A{i1} \cap \cdots \cap A{i_k} | \right)

hoặc

: $\backslash left|\; \backslash bigcup\_\{i=1\}^n\; A$i\right| = \sum{\emptyset\neq J\subseteq{1,\ldots,n(-1)^ |A_J|.

Nếu I là tập con cố định của tập chỉ số N, thì số phần tử thuộc A_i với mọi i thuộc I và không phần tử khác thuộc về là:

: $\backslash sum\_\{I\; \backslash subseteq\; J\}\; (-1)^\; |A\_J|.$

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

: $B$k = A{I \cup { k \ \text{ với } k \in N \smallsetminus I.

Để tính số các phần tử không thuộc bất kỳ B_k nào, thì theo nguyên lý bao hàm-loại trừ (với $B\_\backslash emptyset\; =\; A\_I$), bằng với

: $\backslash sum\_\{K\; \backslash subseteq\; N\; \backslash smallsetminus\; I\}\; (-1)^|B\_K|.$

Tương ứng K ↔ J = I ∪ K giữa các tập con của N \ 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_K = A_J, 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₁, ..., A_n trong không gian xác suất $(\backslash Omega,\backslash mathcal\{F\},\backslash mathbb\{P\})$, nguyên lý bao hàm-loại trừ cho trường hợp n = 2 là

: $\backslash mathbb\{P\}(A\_1\backslash cup\; A\_2)=\backslash mathbb\{P\}(A\_1)+\backslash mathbb\{P\}(A\_2)-\backslash mathbb\{P\}(A\_1\backslash cap\; A\_2),$

và cho trường hợp n = 3:

: $\backslash mathbb\{P\}(A\_1\backslash cup\; A\_2\backslash cup\; A\_3)=\backslash mathbb\{P\}(A\_1)+\backslash mathbb\{P\}(A\_2)+\backslash mathbb\{P\}(A\_3)-\backslash mathbb\{P\}(A\_1\backslash cap\; A\_2)-\backslash mathbb\{P\}(A\_1\backslash cap\; A\_3)-\backslash mathbb\{P\}(A\_2\backslash cap\; A\_3)+\backslash mathbb\{P\}(A\_1\backslash cap\; A\_2\backslash cap\; A\_3)$

và trong tổng quát

: $\backslash mathbb\{P\}\backslash left(\backslash bigcup\_\{i=1\}^n\; A$i\right)=\sum{i=1}^n \mathbb{P}(Ai) -\sum{i<j}\mathbb{P}(A_i\cap Aj)+\sum{i<j<k}\mathbb{P}(A_i\cap A_j\cap Ak) + \cdots +(-1)^{n-1} \sum{i<...<n}\mathbb{P}\left(\bigcap_{i=1}^n A_i\right),

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

: $\backslash mathbb\{P\}\backslash left(\backslash 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),

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à

: $A$I:=\bigcap{i\in I} A_i

là giao của tất cả các A_i với chỉ số thuộc I.

Theo các 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₁, ..., A_n với độ đo hữu hạn, các định thức trên vẫn đúng khi độ đo xác suất $\backslash mathbb\{P\}$ đượ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_I chỉ dựa trên số lực lượng của I, nghĩa là với mọi k thuộc {1, ..., n} tồn tại a_k sao cho

: $a\_k=\backslash mathbb\{P\}(A\_I)\; \backslash text\{\; với\; mọi\; \}\; I\backslash subset\{1,\backslash ldots,n\}\; \backslash text\{\; và\; \}\; |I|=k,$

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

: $\backslash mathbb\{P\}\backslash left(\backslash bigcup\_\{i=1\}^n\; A$i\right) =\sum{k=1}^n (-1)^{k-1}\binom n k a_k

,sử dụng suy luận tổ hợp với hệ số nhị thức $\backslash binom\; nk$. Ví dụ chẳng hạn, nếu các biến cố $A\_i$ đều độc lập và phân phối đều với nhau, thì $\backslash mathbb\{P\}(A\_i)\; =\; p$ với mọi i, và ta có $a\_k\; =\; p^k$, và khi đó công thức ngay trên giản hoá tiếp thành

: $\backslash mathbb\{P\}\backslash left(\backslash bigcup\_\{i=1\}^n\; A\_i\backslash right)\; =\; 1\; -\; (1-p)^n.$

(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ố $A\_i$.)

Tồn tại dạng giản hoá tương tự cho trường hợp không gian độ đo và các tập con đo được A₁, ..., A_n 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 : nếu

: $g(A)=\backslash sum\_\{S\; \backslash subseteq\; A\}f(S)$

thì

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ừ (). Ai \right| \text{ và } g(A) = \mathbb{P} \left( \bigcap{i \in \underline{m} \smallsetminus A} Ai \right),~~ g(\underline{m}) = \mathbb{P} \left(\bigcup{i \in \underline{m A_i\right)

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

Bởi $f(\backslash underline\{m\})\; =\; 0$, ta thu được từ () với $A\; =\; \backslash underline\{m\}$ rằng

:$\backslash sum\_\{\backslash underline\{m\}\; \backslash supseteq\; T\; \backslash supsetneq\; \backslash varnothing\}(-1)^$ của () trong trường hợp $A\; -\; S$ là tập hợp.

Ứ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ố 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 $\backslash overline\{A\_k\}$ là phần bù của A_k tương ứng với tập phổ dụng A nào đó sao cho $A\_k\; \backslash subseteq\; A$ với mỗi k. Khi đó ta có

: $\backslash bigcap\_\{i=1\}^n\; A$i = \overline{\bigcup{i=1}^n \overline{A_i

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ị.

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ố.

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.

Đếm số toàn ánh

Câu hỏi đặt ra là cho hai tập con A và B, có bao nhiêu 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 từ A đến B, và định nghĩa với mỗi i thuộc B, tính chất P_i :"hàm bỏ qua giá trị i thuộc B" (i không nằm trong ả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:

: $\backslash sum\_\{j=0\}^\{n\}\; \backslash binom\{n\}\{j\}\; (-1)^j\; (n-j)^k.$

Đế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_i là tập các vị trí mà i không được phép ngồi vào, và tính chất P_i là tính chất đặt i vào vị trí A_i, 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.

Trong ví dụ trên, có 12 = 2(3!) hoán vị thoả mãn tính chất P₁, 6 = 3! hoán vị thoả mãn tính chất P₂ và không có hoán vị nào cho P₃ hoặc P₄ 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₁ và P₂.

Đa thức quân xe

Đa thức quân xe là hàm sinh số cách đặt các 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_k(B) của x^k trong đa thức quân xe R_B(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ù $B\text{'}$ 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 $R\_\{B\text{'}\}(x)$ cùng với các hệ số $r\_k(B\text{'}).$

Đô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_n(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ànB) được tính theo giai thừa giảm sau:

: $(m)\_n\; =\; m(m-1)(m-2)\; \backslash cdots\; (m-n+1).$

Gọi P_i 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:

: $r$n(B) = \sum{t=0}^n (-1)^t (m-t)_{n-t} r_t(B').

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_i là số thuộc S chia hết cho số nguyên tố p_i, với 1 ≤ i ≤ r,trong đó phân tích thừa số nguyên tố của

: $n\; =\; p\_1^\{a\_1\}\; p\_2^\{a\_2\}\; \backslash cdots\; p\_r^\{a\_r\}.$

thì,

: $\backslash varphi(n)\; =\; n\; -\; \backslash sum\_\{i=1\}^r\; \backslash frac\{n\}\{p$i} + \sum{1 \leqslant i < j \leqslant r} \frac{n}{p_i pj} - \cdots = n \prod{i=1}^r \left (1 - \frac{1}{p_i} \right ).

Nguyên lý bao hàm-loại trừ bị pha loãng

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 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₁, ..., A_n là các tập hợp tuỳ ý và p₁, ..., p_n 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:

: $1\_\{A\_1\backslash cup\backslash cdots\backslash cup\; A$n} \ge \sum{j=1}^k (-1)^{j-1}\sum_{1\le i_1<\cdots<ij\le n} p{i1} \dots p{ij} \, 1{A_{i1} \cap \cdots \cap A{i_j.

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 $A\_1,\; A\_2,\; \backslash dots,\; A\_t\; (t\; >\; 0)$ 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 (), 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ừ $A\_1,\; A\_2,\; \backslash dots,\; A\_t$. 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ó

:

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

: $0\; =\; (1-1)^t=\; \backslash binom\{t\}\{0\}\; -\; \backslash binom\{t\}\{1\}\; +\; \backslash binom\{t\}\{2\}\; -\; \backslash cdots\; +\; (-1)^t\backslash binom\{t\}\{t\}.$

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

: $1\; =\; \backslash binom\{t\}\{1\}\; -\; \backslash binom\{t\}\{2\}\; +\; \backslash cdots\; +\; (-1)^\{t+1\}\backslash binom\{t\}\{t\},$

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 ().

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

:

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

: $\backslash mathbf\{1\}\_A\; \backslash cdot\backslash mathbf\{1\}$B = \mathbf{1}{A\cap B}.

Gọi A là hợp $\backslash bigcup\_\{i=1\}^n\; A\_i$ của các tập hợp A₁, ..., A_n. Để 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

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

: $A$I = \bigcap{i\in I} A_i.

Hàm sau

: $\backslash left\; (\backslash 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 ),

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 − 0 = 0; và ngược lại, nếu x có thuộc một số A_m, thì nhân tử thứ m tương ứng là 1 − 1 = 0.Bằng cách mở rộng tích ở vế trái, suy ra phương trình ().

Để 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 () trên tất cả các x thuộc hợp của A₁, ..., A_n. Để từ đây lấy ra phiên bản xác suất, cho giá trị kỳ vọng vào (). Và tổng quát hơn, lấy tích phân phương trình () tương ứng với to μ. 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.